Depth-First Search (DFS)

Depth-first search (DFS) explores a graph by going as deep as possible along one path before coming back to try another, like exploring a cave with a torch: follow one tunnel to its end, then return to the last fork and take the next tunnel. Where BFS spreads out in waves, DFS dives.

In this lesson you will write DFS both recursively and with an explicit stack, then use it for three classic jobs: counting connected groups, flood filling regions of a grid and detecting cycles in directed graphs.

Recursive DFS

DFS is naturally recursive: visit a vertex, then run DFS from each neighbour that has not been visited yet. The call stack remembers where to come back to.

graph = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": ["B"],
    "E": ["B", "F"],
    "F": ["C", "E"],
}

def dfs(graph, vertex, visited, order):
    visited.add(vertex)
    order.append(vertex)
    for nxt in graph[vertex]:
        if nxt not in visited:
            dfs(graph, nxt, visited, order)
    return order

print("DFS from A:", dfs(graph, "A", set(), []))

DFS from A: ['A', 'B', 'D', 'E', 'F', 'C']

From A, DFS goes to B, then to D (a dead end), returns to B, goes to E, then F, and from F reaches C. BFS from A would visit A, B, C, D, E, F instead, because it takes all of A's neighbours first.

Like BFS, DFS visits every vertex once and checks every edge a constant number of times: O(V + E) time. The extra space is O(V) for the visited set plus the depth of the recursion.

Iterative DFS with a stack

Recursion in Python stops at about 1000 levels (see Recursion), and a long chain of vertices can easily be deeper than that. Replacing the call stack with your own list fixes this. Push the start; then repeatedly pop a vertex, skip it if already visited, otherwise visit it and push its neighbours.

def dfs_iterative(graph, start):
    visited, order = set(), []
    stack = [start]
    while stack:
        vertex = stack.pop()
        if vertex in visited:
            continue
        visited.add(vertex)
        order.append(vertex)
        for nxt in reversed(graph[vertex]):     # so the first neighbour is popped first
            if nxt not in visited:
                stack.append(nxt)
    return order

graph = {
    "A": ["B", "C"], "B": ["A", "D", "E"], "C": ["A", "F"],
    "D": ["B"], "E": ["B", "F"], "F": ["C", "E"],
}
print(dfs_iterative(graph, "A"))

# A chain of 5000 vertices: fine without recursion
chain = {i: [i + 1] for i in range(4999)}
chain[4999] = []
print(len(dfs_iterative(chain, 0)), "vertices visited")

['A', 'B', 'D', 'E', 'F', 'C']
5000 vertices visited

Pushing neighbours in reverse order makes the visit order match the recursive version. Notice the difference from BFS: here a vertex is marked visited when it is popped, because the same vertex may be pushed more than once before its turn comes. That is fine for DFS; the continue skips duplicates.

Connected components

A connected component is a group of vertices that can all reach each other, with no path to vertices outside the group. After heavy rain in Kerala, some roads between villages are closed. How many separate groups of villages can still reach each other, and which villages are in each? Run DFS from every village not yet visited; each run collects one component.

open_roads = [("Aluva", "Kalamassery"), ("Kalamassery", "Edappally"),
              ("Munnar", "Adimali"), ("Kumily", "Thekkady"), ("Thekkady", "Vandiperiyar")]
villages = ["Aluva", "Kalamassery", "Edappally", "Munnar", "Adimali",
            "Kumily", "Thekkady", "Vandiperiyar", "Vagamon"]

graph = {v: [] for v in villages}
for u, v in open_roads:
    graph[u].append(v)
    graph[v].append(u)

def components(graph):
    seen, groups = set(), []
    for start in graph:
        if start in seen:
            continue
        group, stack = [], [start]          # a new component begins here
        seen.add(start)
        while stack:
            v = stack.pop()
            group.append(v)
            for nxt in graph[v]:
                if nxt not in seen:
                    seen.add(nxt)
                    stack.append(nxt)
        groups.append(sorted(group))
    return groups

groups = components(graph)
print(len(groups), "separate groups")
for g in groups:
    print(g)

4 separate groups
['Aluva', 'Edappally', 'Kalamassery']
['Adimali', 'Munnar']
['Kumily', 'Thekkady', 'Vandiperiyar']
['Vagamon']

Vagamon has no open roads at all, so it forms a group of one. The outer loop touches every vertex and the inner DFS runs on each component once, so the total is still O(V + E). BFS would work equally well here; for "which things are connected?" questions, use whichever you find clearer.

Flood fill on a grid

Flood fill is DFS on a grid: start from one cell and spread to every connected cell of the same kind. It is how the paint bucket tool in an image editor works. Here it counts the lakes on a satellite map (~ is water, . is land) and measures each lake's size.

satellite = [
    "~~..~...",
    "~...~~..",
    "...~....",
    "..~~~..~",
    "......~~",
]
ROWS, COLS = len(satellite), len(satellite[0])
seen = set()

def lake_size(r, c):
    size, stack = 0, [(r, c)]
    seen.add((r, c))
    while stack:
        r, c = stack.pop()
        size += 1
        for nr, nc in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):
            if (0 <= nr < ROWS and 0 <= nc < COLS and satellite[nr][nc] == "~"
                    and (nr, nc) not in seen):
                seen.add((nr, nc))
                stack.append((nr, nc))
    return size

lakes = []
for r in range(ROWS):
    for c in range(COLS):
        if satellite[r][c] == "~" and (r, c) not in seen:
            lakes.append(lake_size(r, c))
print(len(lakes), "lakes with sizes", lakes)

4 lakes with sizes [3, 3, 4, 3]

Only up, down, left and right count as connected here, so diagonal water cells belong to different lakes. Counting "islands" or "regions" in a grid is one of the most common interview problems, and this double loop plus flood fill is the standard answer, O(rows × columns).

Detecting cycles in a directed graph

A software project has modules that import each other. If billing imports tax, tax imports rates and rates imports billing, there is a circular import, a cycle. To find cycles in a directed graph, DFS keeps three states for each vertex, often called colours:

• white: not visited yet,
• grey: visited and still on the current DFS path (its call has not finished),
• black: fully finished; everything reachable from it has been explored.

If DFS ever reaches a grey vertex, it has found an edge back to a vertex on the current path: a cycle. Reaching a black vertex is fine; that only means two paths meet.

WHITE, GREY, BLACK = 0, 1, 2

def find_cycle(graph):
    colour = {v: WHITE for v in graph}
    path = []

    def visit(v):
        colour[v] = GREY
        path.append(v)
        for nxt in graph[v]:
            if colour[nxt] == GREY:                  # back edge: a cycle
                return path[path.index(nxt):] + [nxt]
            if colour[nxt] == WHITE:
                found = visit(nxt)
                if found:
                    return found
        colour[v] = BLACK
        path.pop()
        return None

    for v in graph:
        if colour[v] == WHITE:
            found = visit(v)
            if found:
                return found
    return None

imports = {"app": ["billing", "users"], "billing": ["tax", "users"],
           "tax": ["rates"], "rates": [], "users": []}
print(find_cycle(imports))

imports["rates"].append("billing")              # someone adds a bad import
print(" -> ".join(find_cycle(imports)))

None
billing -> tax -> rates -> billing

In the first graph, users is reached twice (from app and from billing), but the second time it is already black, so it is not a cycle. A plain visited set cannot tell those two cases apart, which is why directed graphs need the grey state. For undirected graphs, a simpler rule works: a cycle exists if DFS reaches an already visited vertex that is not the parent it just came from.

Common mistakes

• Forgetting the visited set on a graph with cycles, which makes DFS loop forever.
• Using recursion on very deep graphs in Python. Use an explicit stack.
• Using a plain visited set for directed cycle detection. It reports false cycles when two paths meet; use the three colours.
• Starting DFS from only one vertex when the graph may be disconnected. Loop over all vertices.

Key points

• DFS follows one path as deep as it can, then backtracks; it runs in O(V + E).
• Write it recursively for clarity or with an explicit stack to avoid recursion limits.
• Running DFS from every unvisited vertex finds all connected components.
• Flood fill is DFS on a grid and counts regions such as lakes or islands.
• In directed graphs, reaching a grey vertex (on the current path) means a cycle.
• BFS finds shortest unweighted paths; DFS is the tool for structure: components, cycles and ordering.

def has_path(graph, start, goal):
    stack, seen = [start], {start}
    while stack:
        v = stack.pop()
        if v == goal:
            return True
        for nxt in graph[v]:
            if nxt not in seen:
                seen.add(nxt)
                stack.append(nxt)
    return False

imports = {"app": ["billing", "users"], "billing": ["tax", "users"],
           "tax": ["rates"], "rates": [], "users": []}
print(has_path(imports, "app", "rates"))
print(has_path(imports, "users", "tax"))

True
False