Depth-First Search

Jr Codex DSA Notes

Level: Advanced Prerequisites: Chapter 2 Time to complete: ~25 minutes

Table of Contents

1. DFS: Go Deep Before Going Wide
2. Recursive DFS
3. Iterative DFS with an Explicit Stack
4. BFS vs. DFS
5. Use Case: Connected Components
6. Use Case: Cycle Detection in an Undirected Graph
7. Complexity
8. Summary & Next Steps

1. DFS: Go Deep Before Going Wide

Depth-first search (DFS) picks a neighbor, goes as deep as possible along that path, and only backtracks when it hits a dead end — the opposite exploration order from BFS's layer-by-layer approach. This is the same idea as Module 7 Chapter 2's preorder/inorder/postorder traversals, generalized beyond trees to graphs (with a visited set, same reasoning as Chapter 2).

2. Recursive DFS

DFS maps naturally onto recursion (Module 4) — the call stack itself tracks "how deep have I gone" and "where do I backtrack to."

def dfs_recursive(graph, node, visited=None, order=None):
    if visited is None:
        visited = set()
        order = []
 
    visited.add(node)
    order.append(node)
 
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited, order)
 
    return order
 
graph = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A", "D"],
    "D": ["B", "C", "E"],
    "E": ["D"],
}
 
print(dfs_recursive(graph, "A"))     # ['A', 'B', 'D', 'C', 'E']

Trace: start at A, go to B (first neighbor), from B go to D (first unvisited neighbor), from D go to C (first unvisited neighbor), C has no unvisited neighbors so backtrack to D, D's next neighbor E is unvisited, visit it. Notice how this dives all the way down one path before backtracking — the defining DFS behavior.

3. Iterative DFS with an Explicit Stack

Any recursive algorithm can be rewritten iteratively using an explicit stack (Module 5) instead of relying on the call stack — useful when recursion depth could exceed Python's recursion limit on very large graphs.

def dfs_iterative(graph, start):
    visited = {start}
    stack = [start]
    order = []
 
    while stack:
        node = stack.pop()          # LIFO — Module 5's stack
        order.append(node)
 
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                stack.append(neighbor)
 
    return order

Note: the exact visiting order can differ slightly from the recursive version depending on the order neighbors are pushed, but both correctly perform a depth-first exploration.

4. BFS vs. DFS

5. Use Case: Connected Components

A connected component is a maximal group of nodes all reachable from each other. Counting them is a direct DFS application: run DFS from any unvisited node, mark everything it reaches, then repeat from the next unvisited node.

def count_connected_components(graph, all_nodes):
    visited = set()
    components = 0
 
    for node in all_nodes:
        if node not in visited:
            dfs_recursive(graph, node, visited, [])     # reuses visited across calls
            components += 1
 
    return components

6. Use Case: Cycle Detection in an Undirected Graph

A cycle exists if, during DFS, you reach a node that's already visited and it isn't the node you just came from (in an undirected graph, every edge naturally leads back to its own parent — that's not a cycle, just the edge you arrived on).

def has_cycle(graph, all_nodes):
    visited = set()
 
    def dfs(node, parent):
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                if dfs(neighbor, node):
                    return True
            elif neighbor != parent:      # visited AND not where we came from → cycle
                return True
        return False
 
    for node in all_nodes:
        if node not in visited:
            if dfs(node, None):
                return True
    return False

7. Complexity

Time: O(V + E) — identical to BFS, every vertex and edge is examined once. Space: O(V) — the visited set, plus recursion stack depth (recursive version) or explicit stack size (iterative version), both bounded by the number of vertices.

8. Summary & Next Steps

Key Takeaways

• DFS explores as deep as possible before backtracking, implemented either recursively (Module 4) or iteratively with an explicit stack (Module 5).
• BFS uses a queue and explores layer by layer; DFS uses a stack/recursion and explores depth-first — same O(V + E) time complexity, different traversal shape and use cases.
• Connected components and cycle detection are natural DFS applications: track a global visited set across multiple DFS calls, one per undiscovered starting node.
• In undirected-graph cycle detection, seeing a visited node that isn't your immediate parent signals a cycle — visiting the parent back is expected, not a cycle.

Concept Check

1. What's the core structural difference between how BFS and DFS decide which node to visit next?
2. Why does counting connected components need a visited set that persists across multiple DFS calls?
3. In undirected cycle detection, why must you exclude the immediate parent when checking for an already-visited neighbor?

Next Chapter

→ Chapter 4: Common Graph Problems

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index