DFS: Going Deep, and Counting Islands

The other traversal

BFS answers fewest hops, but many graph questions never mention distance at all. Can this task's dependencies be satisfied? Which users form one cluster of linked accounts? Which pixels belong to this connected region, which is the flood fill behind every paint-bucket tool?

For reachability questions the visiting order does not matter, only coverage does, and that opens the door to BFS's sibling.

Depth-first search, or DFS, is the lesson 5-3 exploration loop with exactly one change: the frontier is a stack instead of a queue.

pop() hands back the newest discovery, so rather than finishing ring 1 before ring 2, the search plunges down one path as far as it can and then backtracks to the most recent junction with unexplored exits.

The lesson 5-3 quiz warned that this destroys BFS's shortest-path guarantee, and it does. For pure reachability there is simply nothing to destroy, because the question does not ask about distance.

Everything else survives unchanged. The seen set still prevents infinite loops around cycles, every node and edge is still touched at most once, and the cost is still O(nodes + edges).

One loop, two orders

The same friend network as lesson 5-3, traversed both ways.

from collections import deque

friends = {
    "you": ["ana", "ben"],
    "ana": ["you", "cai"],
    "ben": ["you", "cai", "dee"],
    "cai": ["ana", "ben"],
    "dee": ["ben", "eli"],
    "eli": ["dee"],
}

def bfs_order(adj, start):
    frontier = deque([start])
    seen = {start}
    order = []
    while frontier:
        node = frontier.popleft()
        order.append(node)
        for neighbor in adj[node]:
            if neighbor not in seen:
                seen.add(neighbor)
                frontier.append(neighbor)
    return order

def dfs_order(adj, start):
    frontier = [start]
    seen = {start}
    order = []
    while frontier:
        node = frontier.pop()
        order.append(node)
        for neighbor in adj[node]:
            if neighbor not in seen:
                seen.add(neighbor)
                frontier.append(neighbor)
    return order

print("BFS:", bfs_order(friends, "you"))
print("DFS:", dfs_order(friends, "you"))

Output

BFS: ['you', 'ana', 'ben', 'cai', 'dee', 'eli']
DFS: ['you', 'ben', 'dee', 'eli', 'cai', 'ana']

The only difference between the two functions is popleft for the oldest against pop for the newest. Every other line is identical, which is worth dwelling on, since BFS and DFS are usually taught as separate algorithms.

BFS radiates outward ring by ring, so ana and ben both appear before cai. DFS dives from you to ben to dee to eli before ana's branch is touched at all, even though ana was discovered first.

Both visited all six people. Coverage is identical, and only the order differs, which is exactly why either one answers a reachability question.

The DFS order also shows the backtracking. After eli it has nowhere deeper to go, so it returns to the most recent junction with unexplored exits and picks up cai and ana from the stack.

The stack went into the call stack from lesson 5-1, where each recursive call pushes a frame and returning pops back to the most recent junction.

That is precisely the explicit stack's job. Entering visit(neighbor) pushes a frame, and finishing it returns to the previous node, so backtracking happens for free with no data structure written by hand.

This explains an asymmetry that otherwise looks arbitrary. DFS recurses naturally while BFS does not, because no call mechanism hands out frames oldest-first, so a queue has to be built explicitly.

It is also a real engineering limit rather than a curiosity. A path of 100,000 nodes means 100,000 stacked frames, well past Python's default recursion cap, so production DFS on large graphs often uses the explicit stack from the previous block.

Recursive DFS is still the clearer code on trees and small graphs, where the depth is bounded by design.

Counting the islands

A traversal from one start visits everything reachable from it, which is called its connected component.

Real graphs are often several disconnected clusters, and how many clusters is a question with commercial weight. Fraud teams cluster linked accounts, image tools count distinct regions, and network tools flag machines cut off from the rest.

The algorithm needs no new machinery, only an outer loop.

1. Keep one seen set for the whole graph and a counter at 0.
2. Walk over every node, skipping any that is already seen.
3. Otherwise a brand-new component has been discovered, so count it and run a traversal from that node to mark the whole component seen.

Either traversal works for step 3, since this is pure reachability, and DFS is the common pick because a plain list is all the frontier needs.

Each traversal swallows one entire cluster, which is what makes the counter increment exactly once per component rather than once per node.

The total cost is still O(nodes + edges). The outer loop touches each node once, and the traversals collectively touch each edge once, because the shared seen set stops any node being explored twice.

Counting components

One shared seen set, an outer loop over every node, and a DFS to swallow each cluster.

network = {
    "ana": ["ben"],
    "ben": ["ana"],
    "cai": ["dee", "eli"],
    "dee": ["cai"],
    "eli": ["cai"],
    "fay": [],
}

def component_count(adj):
    seen = set()
    count = 0
    for start in adj:
        if start not in seen:
            count += 1
            stack = [start]
            seen.add(start)
            while stack:
                node = stack.pop()
                for neighbor in adj[node]:
                    if neighbor not in seen:
                        seen.add(neighbor)
                        stack.append(neighbor)
    return count

print("components:", component_count(network))

Output

components: 3

The network holds three clusters, {ana, ben}, {cai, dee, eli}, and fay alone, which is the 3 in the output.

The inner DFS is dfs_order from the demo with the order list removed, because only the side effect of filling seen is wanted here.

seen must live outside the outer loop, and this is the bug to watch for. Resetting it per node would make every node look unvisited, so every node would count as its own component and the answer would be 6.

Tracing the walk gives the count directly. ana is new so count reaches 1 and ben gets marked, cai is new so count reaches 2 and dee and eli get marked, and fay is new so count reaches 3.

fay has no neighbors, so its DFS pushes fay, pops fay, and ends immediately. An isolated node is a component of size 1, which is the correct answer rather than an edge case to exclude.

Task A requires BFS, and task B works with either.

Fewest introductions is a shortest path in hops, and only ring-by-ring order proves the path found is the shortest. FIFO order is the proof from lesson 5-3, since finishing every node at distance k before starting on k+1 means first arrival is best arrival.

Task B asks only whether the two servers are connected, which has no ordering requirement at all. Any traversal that covers the reachable set answers it, so DFS's simpler machinery, a plain list or plain recursion, is the usual choice.

Both share the same seen set and the same O(nodes + edges) cost, so the discipline of the frontier is the only real difference between them.

That is the takeaway for the whole unit. Ask whether the question involves distance, and if it does not, take the traversal with the simplest bookkeeping.