BFS and DFS
A graph is vertices joined by edges, and a traversal visits every vertex you can reach from a start by following edges. The only question is which discovered vertex to expand next. A queue answers longest waiting, which spreads outward layer by layer and finds shortest paths. A stack answers most recent, which dives down one path before trying another. Running a traversal from every vertex not yet reached counts the components.
Count the connected components. Scan the vertices in order. Each vertex no traversal has reached starts a new component: number it, then breadth-first search from it and give every vertex reached the same number.
Check your understanding
The player pauses before each decision in this run and asks what happens next. Here are all 3, with their answers.
Vertex 0 has not been reached by any traversal. Which component number is it?
Answer: 1. An unreached vertex is always the start of a brand new component.
Vertex 3 has not been reached by any traversal. Which component number is it?
Answer: 2. An unreached vertex is always the start of a brand new component.
Vertex 5 has not been reached by any traversal. Which component number is it?
Answer: 3. An unreached vertex is always the start of a brand new component.
How it runs, step by step
Count the connected components. Scan the vertices in order. Each vertex no traversal has reached starts a new component: number it, then breadth-first search from it and give every vertex reached the same number.
Counting connected components with one traversal per component.
Vertex 0 has no component number yet, so it starts component 1. Traverse from it.
Vertex 0 starts component 1.
From 0: 1 join component 1.
1 join component 1.
From 1: 2 join component 1.
2 join component 1.
From 2: every neighbour is already in component 1.
Vertex 2 adds nothing new.
Vertex 3 has no component number yet, so it starts component 2. Traverse from it.
Vertex 3 starts component 2.
From 3: 4 join component 2.
4 join component 2.
From 4: every neighbour is already in component 2.
Vertex 4 adds nothing new.
Vertex 5 has no component number yet, so it starts component 3. Traverse from it.
Vertex 5 starts component 3.
From 5: 6 join component 3.
6 join component 3.
From 6: 7 join component 3.
7 join component 3.
From 7: every neighbour is already in component 3.
Vertex 7 adds nothing new.
3 components. Every vertex carries its component number, and each traversal touched only its own component, so the whole scan is still O(V + E).
3 components were found.
Remember
- BFS with a queue reaches vertices in order of distance, so the first discovery of a vertex is a shortest path.
- DFS with a stack or recursion goes deep first; the order depends on how neighbours are listed.
- Mark a vertex when it is discovered, not when it is expanded, or it can be queued twice. Both cost O(V + E).
Topics covered
Related
Where this is used
RuntimesTracing garbage collectors
The mark phase in the Go runtime or the JVM is exactly this traversal: objects are vertices, references are edges, and the roots are the stack slots and globals. Whatever the traversal never reaches cannot be reached by the program either, which is the definition of garbage, so reachability is the whole test. Collectors keep an explicit work queue rather than recursing, because object graphs get deep and a collector cannot be the thing that overflows the stack.
Developer toolsDependency resolution in build and package tools
Cargo, Gradle and Bazel all walk a dependency graph depth first: a package or task is finished only once everything it depends on has finished, and that finishing order is a valid build order. Reaching a vertex that is still open on the stack is precisely a circular dependency, which is why these tools stop with a cycle error and can print the whole chain - the open stack at that moment is the cycle.
WebWeb crawler frontiers
Apache Nutch crawls breadth first by default: the frontier is a queue seeded with a few start URLs, and each round fetches one layer and feeds the links it finds into the next round, so pages arrive roughly in order of link distance from the seeds. That ordering matters because pages near a site's entry points are usually the ones worth having, and capping the number of rounds is a simple, honest way to bound a crawl that would otherwise never finish.
Social networksDegrees of connection
The 1st, 2nd and 3rd degree labels LinkedIn puts on a profile are BFS layers measured outward from you. Stopping that early is what keeps the work bounded: each layer multiplies by the average connection count, so a fourth layer would already touch a large fraction of the network. Searching from both endpoints at once and meeting in the middle is the standard way to go further, because two shallow searches touch far fewer profiles than one deep one.
Why it works this way
BFS finds shortest paths only when every edge costs the same
The first time BFS discovers a vertex it has got there using the fewest edges, but fewest edges only means shortest when every edge is worth the same. Give the edges weights, such as road distance or link latency, and a two edge route can beat a one edge route, so the first discovery is no longer the answer and you need Dijkstra. The one exception worth knowing is weights of only 0 and 1, where a deque with 0 edges pushed to the front and 1 edges to the back keeps plain BFS correct.
Why is it O(V + E) and not O(V * E)?
It reads like a nested loop, but the inner loop is bounded by one vertex's degree, not by the whole edge count. Each vertex is expanded once and its adjacency list is scanned once, so the edge work adds up to the sum of all degrees, which is E for a directed graph and 2E for an undirected one. The separate V term is there because every vertex still has to be allocated and initialised, which is what a graph of isolated vertices and no edges costs you.
Recursive DFS runs out of stack long before it runs out of time
The recursion depth of DFS is the length of the longest path it walks, not something logarithmic, so a graph shaped like a chain of 100,000 vertices wants 100,000 live frames at once. A default JVM or Android thread stack holds roughly tens of thousands of frames, so it dies with StackOverflowError on input that the O(V + E) bound calls trivial. The explicit stack above does the same work with the same shape but keeps the pending vertices on the heap, which is why traversals that run on untrusted input are usually written iteratively.
Why the iterative DFS marks on pop, and pushes neighbours reversed
BFS marks on discovery, which both stops a vertex entering the queue twice and fixes its distance at the shortest one. The stack version cannot do the same and still match recursive DFS, because a vertex can be pushed by several neighbours before any copy is popped, and the copy that should win is the most recent push, the one on top. So the seen check moves to the pop and the older copies underneath are skipped as stale. The price is that the stack can hold up to E entries rather than V. The asReversed is there because a stack hands back the most recent push first: pushing the neighbours in list order would visit them backwards, so reversing them first makes the iterative order match the recursive version a learner writes.
Read more
- Breadth-first searchWikipedia
- Depth-first searchWikipedia
- Breadth-first searchcp-algorithms
- Depth-first searchcp-algorithms
- Building RoadsCSES 1666 · cses.fi