Depth-first search (DFS)

Go deep first, then back up

Depth-first search (DFS) picks a neighbour and keeps going deeper until it reaches a dead end, then backtracks (goes back) to the last vertex that still has an unvisited neighbour. It is the same idea as the recursion and backtracking of Module 5 and the tree traversals of Module 7, with one addition: a visited set, because a graph can lead you back to a vertex you have already seen.

def dfs(adj, u, visited):
    visited.add(u)
    for v in adj[u]:
        if v not in visited:
            dfs(adj, v, visited)

adj = {0: [1, 2], 1: [0], 2: [0], 3: [4], 4: [3]}
seen = set()
dfs(adj, 0, seen)
print(sorted(seen))   # Output: [0, 1, 2]

The same search works with an explicit stack (a Python list with append and pop). This avoids Python's recursion limit. The visiting order is different from the recursive version, which does not matter when you only need to know what is reachable.

def dfs_iter(adj, start):
    visited = {start}
    stack = [start]
    order = []
    while stack:
        u = stack.pop()
        order.append(u)
        for v in adj[u]:
            if v not in visited:
                visited.add(v)
                stack.append(v)
    return order

print(dfs_iter({0: [1, 2], 1: [3], 2: [], 3: []}, 0))   # Output: [0, 2, 1, 3]

Like BFS, DFS looks at every vertex and every edge a constant number of times: O(V + E) time with an adjacency list, and O(V) extra space for the visited set and the stack (or the call stack).

Connected components and islands

To count the separate pieces of an undirected graph, loop over every vertex. Whenever you find one that is not visited yet, you have found a new component: add 1 to the count and run a DFS from it to mark its whole component. The "number of islands" problem is the same on a grid: each unvisited land cell starts a new island, and the DFS marks all land connected to it up, down, left and right.

Cycles in an undirected graph

In an undirected graph, the edge you just came along leads straight back to your parent, which is visited. That is not a cycle. So pass the parent into the DFS: if you meet a visited neighbour that is NOT your parent, you have found a cycle.

def has_cycle_undirected(n, edges):
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
    visited = [False] * n

    def dfs(u, parent):
        visited[u] = True
        for v in adj[u]:
            if not visited[v]:
                if dfs(v, u):
                    return True
            elif v != parent:
                return True
        return False

    return any(not visited[u] and dfs(u, -1) for u in range(n))

print(has_cycle_undirected(3, [(0, 1), (1, 2)]))          # Output: False
print(has_cycle_undirected(3, [(0, 1), (1, 2), (2, 0)]))  # Output: True

Cycles in a directed graph: three colours

In a directed graph, meeting a visited vertex is not enough. Take 0 → 1, 0 → 2, 1 → 3, 2 → 3 (a diamond). DFS reaches 3 through 1, finishes it, and later meets 3 again through 2. Vertex 3 is visited, but there is no cycle, because you cannot get from 3 back to 0.

The fix is three colours. White means not visited yet. Grey means "on the current path": the DFS has entered it and not yet finished it (it is on the recursion stack). Black means finished. An edge to a GREY vertex points back into the current path, so it closes a cycle. An edge to a black vertex is safe.

Recursion depth in Python

Every recursive call uses a frame on the call stack, and Python stops at a recursion limit, 1000 by default (sys.getrecursionlimit()). A path of 50,000 vertices, or a 300 × 300 grid that is all land, raises RecursionError with recursive DFS. sys.setrecursionlimit() can raise the limit, but going too high can crash the interpreter, and in the browser (Pyodide) the real stack may be smaller. On big inputs, use an explicit stack, or BFS when the order does not matter.

Common mistakes

• Using a plain visited set to find cycles in a directed graph, which reports a "cycle" on every diamond. Fix: three colours (white, grey, black).
• In an undirected graph, treating the edge back to the parent as a cycle. Fix: pass the parent and ignore it once.
• Running DFS only from vertex 0 and missing the other components. Fix: loop over every vertex and start a DFS from each unvisited one.
• Recursive DFS on a huge graph or grid, ending in RecursionError. Fix: an explicit stack.
• Changing the input grid (marking land as "0") without saying so. Fix: say it, or keep a separate visited set.