Back to Welcome Page

Graphs IV: Depth-First Traversal

Master depth-first traversal techniques and their applications in graph algorithms. Learn to implement both recursive and iterative approaches to DFS and solve complex graph problems.

Learning Objectives

Core Concepts

  • Understanding depth-first search (DFS)
  • Recursive vs. iterative implementations
  • Backtracking in graph traversal
  • Time and space complexity analysis
  • DFS applications in problem-solving

Skills Development

  • Implementing recursive DFS
  • Converting recursive to iterative
  • Detecting cycles in graphs
  • Topological sorting
  • Solving graph-based puzzles

Prerequisites

Required Knowledge

  • Basic graph theory concepts
  • Understanding of recursion
  • Stack data structure
  • Graph representation methods

Recommended Preparation

  • Review recursive functions
  • Practice stack operations
  • Study graph properties
  • Understand backtracking

Video Lecture

Depth-First Traversal

Key Concepts Covered:

  • DFS algorithm fundamentals
  • Recursive implementation strategy
  • Stack-based iterative approach
  • Common applications and use cases

Code Implementation

Recursive DFS Implementation

public class Graph {
    private Map> adjacencyList = new HashMap<>();
    
    public void dfsRecursive(T start) {
        Set visited = new HashSet<>();
        dfsRecursiveHelper(start, visited);
    }
    
    private void dfsRecursiveHelper(T vertex, Set visited) {
        visited.add(vertex);
        System.out.println(vertex); // Process vertex
        
        for (T neighbor : adjacencyList.get(vertex)) {
            if (!visited.contains(neighbor)) {
                dfsRecursiveHelper(neighbor, visited);
            }
        }
    }
}

Iterative DFS Implementation

public void dfsIterative(T start) {
    Set visited = new HashSet<>();
    Stack stack = new Stack<>();
    
    stack.push(start);
    
    while (!stack.isEmpty()) {
        T current = stack.pop();
        
        if (!visited.contains(current)) {
            visited.add(current);
            System.out.println(current); // Process vertex
            
            // Add neighbors in reverse order to simulate recursive behavior
            List neighbors = adjacencyList.get(current);
            for (int i = neighbors.size() - 1; i >= 0; i--) {
                T neighbor = neighbors.get(i);
                if (!visited.contains(neighbor)) {
                    stack.push(neighbor);
                }
            }
        }
    }
}

Cycle Detection with DFS

public boolean hasCycle() {
    Set visited = new HashSet<>();
    Set recursionStack = new HashSet<>();
    
    for (T vertex : adjacencyList.keySet()) {
        if (!visited.contains(vertex)) {
            if (hasCycleHelper(vertex, visited, recursionStack)) {
                return true;
            }
        }
    }
    
    return false;
}

private boolean hasCycleHelper(T vertex, Set visited, Set recursionStack) {
    visited.add(vertex);
    recursionStack.add(vertex);
    
    for (T neighbor : adjacencyList.get(vertex)) {
        if (!visited.contains(neighbor)) {
            if (hasCycleHelper(neighbor, visited, recursionStack)) {
                return true;
            }
        } else if (recursionStack.contains(neighbor)) {
            return true; // Cycle found
        }
    }
    
    recursionStack.remove(vertex); // Backtrack
    return false;
}

Guided Practice

For additional hands-on practice and advanced exercises on depth-first traversal and graph algorithms, check out our comprehensive guided project:

Practice Exercises

Fundamental DFS Techniques

Practice fundamental DFS techniques:

Cycle Detection

Practice finding cycles in graphs:

Advanced Applications

Apply DFS to complex problems: