Graph traversal: BFS and DFS
Breadth-first and depth-first search are the two fundamental ways to explore a graph. Almost every graph algorithm builds on one of them.
Breadth-first search
BFS starts at a source vertex and explores in waves: first all vertices one edge away, then two edges away, and so on. It uses a queue: mark the source visited and enqueue it; repeatedly dequeue a vertex and enqueue each unvisited neighbour, marking it visited. With adjacency lists, BFS runs in O(n + m) time.
BFS finds shortest paths
In an unweighted graph, BFS reaches each vertex by a path with the fewest edges. Recording each vertex's parent, the vertex it was discovered from, lets you reconstruct those shortest paths by walking back from the target. BFS also computes distances, finds connected components, and tests bipartiteness by two-colouring vertices level by level.
Depth-first search
DFS goes as deep as possible along each branch before backtracking. It is naturally recursive: visit a vertex, mark it, and recursively visit each unvisited neighbour; an explicit stack gives an iterative version. It also runs in O(n + m). Recording when each vertex is first discovered and when it finishes reveals the graph's structure.
Edge classification and cycle detection
During DFS on a directed graph, an edge to a vertex that is still in progress, on the current recursion path, is a back edge, and a directed graph has a cycle exactly when DFS finds a back edge. In undirected graphs, finding an already visited vertex other than the immediate parent signals a cycle.
Topological sorting
A topological order of a DAG lists vertices so every edge points from earlier to later, such as an order for taking courses with prerequisites. One method lists vertices in reverse order of DFS finishing times. Kahn's algorithm instead repeatedly removes vertices with in-degree 0, using a queue; if vertices remain that never reach in-degree 0, the graph has a cycle.
Connected and strongly connected components
In an undirected graph, repeated BFS or DFS from unvisited vertices finds connected components, the separate pieces. In a directed graph, a strongly connected component is a maximal set in which every vertex can reach every other. Tarjan's and Kosaraju's algorithms find all strongly connected components in O(n + m) using DFS.
Choosing BFS or DFS
Use BFS for shortest paths in unweighted graphs, levels, and nearest matches. Use DFS for cycle detection, topological sorting, components, mazes, and backtracking. On huge or infinite implicit graphs, iterative deepening combines DFS's small memory with BFS's shortest-path guarantee by running depth-limited DFS with increasing limits.
Worked example
Courses with prerequisites: A before C, B before C, C before D, B before E. In-degrees: A 0, B 0, C 2, D 1, E 1. Kahn's algorithm: start with A and B. Remove A: C becomes 1. Remove B: C becomes 0, E becomes 0. Remove C: D becomes 0. Remove E, then D. One valid order is A, B, C, E, D; every prerequisite comes first.
Key takeaways
BFS explores in waves with a queue in O(n + m) and gives shortest paths, by edge count, in unweighted graphs, plus components and bipartiteness tests. DFS explores deeply by recursion or stack in O(n + m). Back edges in DFS reveal directed cycles. Topological sorts order DAGs, via reverse DFS finishing times or Kahn's in-degree algorithm, which also detects cycles. BFS or DFS finds connected components; Tarjan's and Kosaraju's algorithms find strongly connected components. Iterative deepening blends DFS memory with BFS optimality.
Flashcard
Breadth-first search with a queue
Check your understanding
You need the route with the fewest connections between two airports, where every flight counts equally. Which algorithm fits?