CSCI2100 · Method · Chapter 13 · Graph traversal
Depth-first search
1 steps of prerequisites below it
Depth-first search colours vertices white, gray and black, follows one path as far as possible, records discovery and finish times, and restarts from every white vertex to build a DFS forest in Θ(n + m) time.
Taught in
- 13.2 Graph representations and depth-first search · introduced
Builds on
- Adjacency matrix and adjacency lists · used in an argument or worked solution, passage 13.2
Used by
Lenses
- Gray vertices form the current path · Structural
Everything this builds on, earliest first · 1 steps
Each step comes after its own prerequisites, so reading in this order never needs something you have not met. It is a reading order for these notes, not a diagnosis of what you know.
Possible roots and a review route need your own answers on these points. None are recorded yet, so none are suggested.
Longest chain down to a starting point
Each step is used by the one above it, across courses where the notes link them. It ends at a point the notes define without another point.