Card 10/ 10
Recap: Graph Traversal
A queue for distance, a stack for depth, a mark on enqueue, grey for a cycle and an outer loop for every component.
Graph traversal is two searches, breadth-first and depth-first, and the handful of things each finds on the way. This recap lists what the topic established and where, then gives the facts to keep.
| The idea | Where |
|---|---|
| A queue visits vertices in order of distance; mark each one as it joins | Breadth-First Search: Visiting a Graph by Distance From the Start |
| Marking as a vertex leaves lets it join once per edge: 499,501 entries for 1,000 vertices | Marking a Vertex Visited When It Leaves the Queue |
| A stack follows one path to its end; white, grey and black record where each vertex stands | Depth-First Search: Following One Path Until It Ends |
| A real queue in each language, and a head index in TypeScript instead of shift() | Breadth-First and Depth-First Search in Python, Java and TypeScript |
| Breadth-first search finishes distance d before d + 1, so parents give fewest-edge paths | Shortest Paths in an Unweighted Graph From Breadth-First Search |
| A grid is a graph: cells are vertices, four offsets are edges | Traversal Example: The Fewest Moves Through a Maze Grid |
| An edge to a grey vertex is a cycle; an edge to a black one is not | Detecting a Cycle in a Directed Graph With Three Colours |
| An outer loop counts components; alternating colours fail exactly on an odd cycle | Counting Components and Testing for Two Colours |
| A clash between things is an edge, and two groups is a two-colouring | Practice: Splitting Market Stalls Between Two Days |
Both searches visit every reachable vertex once and read every adjacency list once. What separates them is the order, and each question the topic answered picks the search whose order fits it.
- Either search
- O(V + E) time, O(V) extra space
- with an adjacency list
- Fewest edges, levels, nearest first
- Breadth-first search
- only when every edge costs the same
- Cycle in a directed graph
- Depth-first search, edge to a grey vertex
- Components and bipartite test
- Either search, from every unmarked vertex
- Recursion in Python
- Fails past 1,000 frames
- use an explicit stack on deep graphs
The order in which depth-first search finishes vertices has a use beyond the cycle test. Topological Sort, the next topic, turns it into an order of tasks in which every task comes after the ones it depends on.
← → move through sections and cards