BFS & DFS

To explore a graph from one node, you need two things: the nodes you have found but not explored yet, and a record of every node already found, so a loop in the graph can't send you round forever. Take a node from the first, look at its neighbors, add the new ones to both, and repeat until nothing is left to explore.

The only real choice is which found node to explore next. Take the oldest, with a queue, and you get breadth-first search (BFS): it spreads out evenly, one ring of distance at a time. Take the newest, with a stack (or with recursion, which uses the call stack), and you get depth-first search (DFS): it follows one route as far as it goes before backing up.

BFS starts with the start node in a queue. Each node it takes from the front gives its unseen neighbors a distance one larger than its own and sends them to the back. Since the queue is first in, first out, every node 1 hop away is taken before any node 2 hops away, and so on.

That ring order is why BFS finds shortest routes when every link counts the same: the first time it reaches a node is along a route with the fewest hops. Once links carry different weights, hop counts are no longer enough, and you need Dijkstra's algorithm.

DFS is natural to write with recursion: visiting a node means marking it, then visiting each unseen neighbor in turn. The call stack remembers the route back. Here the rooms are nodes and each key is a directed link; the question is whether room 0 reaches every room.

Room 5 was never entered: nobody holds its key. DFS reaches exactly what BFS would, in a different order. The recursion is as deep as the longest route it follows, so a graph shaped like a long chain of 100,000 nodes can overflow the call stack. Then write it with your own stack: push the start, and each round pop a node and push its unseen neighbors.

One search only reaches the nodes connected to its start. A connected component is a largest group of nodes that can all reach each other; an undirected graph splits into one or more of them. To find them all, loop over every node and start a new search from each one not yet seen: each search marks one whole component.

This problem then asks which components are complete, with every pair linked. A complete component of k nodes has k × (k − 1) ÷ 2 links, so its neighbor lists hold k × (k − 1) entries in all.

The searches never overlap, because a seen node is never explored again. So the whole loop still costs O(n + m), however many components there are.

For "can I get there?" and "how many groups?" either works, and DFS is usually shorter to write. For "how few steps?", use BFS. The next page applies both to boards of cells, where the neighbors are the cells next door.