Breadth-first and depth-first

Two ways to walk a graph, identical except for which container holds what you have not visited yet — and that one difference decides what you find first.

#The same graph, two walks

A small social graph, starting from you:

###   BFS: [you, ana, bo, cy, di, ed, fay, zoe]
###   DFS: [you, ana, di, zoe, bo, ed, cy, fay]

BFS takes everyone one step away, then everyone two steps away. ana, bo, cy — all your direct friends — before any friend-of-a-friend.

DFS commits to a path and follows it to the end: ana, then ana's friend di, then di's friend zoe, before it ever looks at bo.

Notice zoe. DFS found her fourth; BFS found her last. If the question were "find zoe", DFS won. If the question were "how far away is zoe", only BFS can answer.

#The only real difference

// BFS — a queue
Deque<String> q = new ArrayDeque<>();
q.add(start);
while (!q.isEmpty()) {
    String v = q.poll();              // oldest first
    for (String n : neighbours(v)) if (seen.add(n)) q.add(n);
}
 
// DFS — a stack
Deque<String> st = new ArrayDeque<>();
st.push(start);
while (!st.isEmpty()) {
    String v = st.pop();              // newest first
    ...
}

poll against pop. Everything else is the same, which is why they are taught together and why ArrayDeque is the right container for both — the collections course's point about it doing both ends in O(1).

DFS also has a recursive form, and that is the more common way to write it. Its stack is the call stack, which means the previous lesson's ceiling applies: recursive DFS on a graph a hundred thousand deep overflows, and the iterative version does not.

#What each one is for

BFS finds the shortest path — but only when every edge costs the same. That is the guarantee, and the condition is easy to forget. Because BFS reaches everything at distance 1 before anything at distance 2, the first time it sees a vertex is by a shortest route.

Put weights on the edges and that breaks immediately: a two-hop path can be cheaper than a one-hop path. Then you need Dijkstra, which is BFS with a PriorityQueue instead of a queue — take the cheapest frontier vertex rather than the oldest. The shape is so similar it is worth seeing as one algorithm with a different container.

DFS is for exhausting a structure, and for questions about whether a path exists rather than how long it is:

• cycle detection
• topological sort (build order, bean creation order)
• connected components
• backtracking, which is DFS over a tree of choices

#The visited set is not optional

Both loops above call seen.add(n) before enqueueing. Without it, a graph with any cycle loops forever — and seen must be checked when you enqueue, not when you dequeue, or the same vertex is added many times before it is first processed.

Worth noting that this makes the traversals O(V + E): every vertex enters the container once, and every edge is looked at once.

#Topological sort: an order that respects every arrow

A build has modules that depend on other modules; Spring has beans that depend on other beans; a migration has steps that must follow others. Each is a directed acyclic graph, and a topological order is any sequence in which every edge points forward — every dependency before the thing that needs it. Two algorithms, and the first is the one to write under pressure:

// Kahn's algorithm: peel off the nodes with nothing left to wait for
List<String> topological(Map<String, List<String>> dependsOn) {          // node -> the nodes it needs first
    Map<String, Integer> remaining = new HashMap<>();                    // how many dependencies are still unplaced
    Map<String, List<String>> dependents = new HashMap<>();              // reverse edges: who is waiting on me
    for (var e : dependsOn.entrySet()) {
        remaining.putIfAbsent(e.getKey(), 0);
        for (String dep : e.getValue()) {
            remaining.merge(e.getKey(), 1, Integer::sum);
            remaining.putIfAbsent(dep, 0);
            dependents.computeIfAbsent(dep, k -> new ArrayList<>()).add(e.getKey());
        }
    }
    Deque<String> ready = new ArrayDeque<>();
    remaining.forEach((node, count) -> { if (count == 0) ready.add(node); });
    List<String> order = new ArrayList<>();
    while (!ready.isEmpty()) {
        String node = ready.poll();
        order.add(node);
        for (String next : dependents.getOrDefault(node, List.of()))
            if (remaining.merge(next, -1, Integer::sum) == 0) ready.add(next);
    }
    if (order.size() != remaining.size()) throw new IllegalStateException("cycle among: " + remaining.keySet().stream().filter(n -> !order.contains(n)).toList());
    return order;
}

Every node starts with its in-degree; the ones at zero are ready; placing one decrements its dependents, and a dependent that reaches zero becomes ready. O(V + E), and the cycle check is free: if the order comes out shorter than the node count, whatever is left is in a cycle, and the message can name it — which is exactly what Spring's BeanCurrentlyInCreationException and Maven's "cyclic reference" do.

The second algorithm is DFS with post-order: run DFS from every unvisited node, append each node to the result after all its descendants have been finished, then reverse. It is shorter to write and detects a cycle by meeting a node that is on the current path (grey, not yet black), which is the three-colour marking from the section above. Kahn's is the one that also gives you which nodes are ready at once — the parallel build's level of independent modules — and the one where a priority queue instead of a deque yields the lexicographically smallest order when several are valid.

#Choosing

The last two rows are the practical ones. BFS holds an entire frontier in memory, which for a wide graph can be enormous. DFS holds one path, which is cheap — and can wander very deep down a branch that has no answer.