Depth-first search
Depth-first search of a graph: recursive and stack versions, discovery and finish order, search tree, backtracking, cycle detection and O(n + m) cost.
- 25 cards
- 5 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- The numbers
- Understand
A few cards from the deck
Discovery order: what is it?
Show the answer
The order in which vertices are first reached, before their neighbours are explored.
It depends on the order in which neighbours are read: with alphabetical order, the first unvisited neighbour is taken and the search dives deeper.
Graph of 7 vertices, edges: A-B, A-C, B-D, B-E, C-F, E-G, F-G. Recursive depth-first search from A, neighbours in alphabetical order. What is the discovery order?
- A B D E G F C
- A B C D E F G
- A C F G E B D
- A B D E C F G
Show the answer
A B D E G F C
A, then B (first neighbour), D (dead end: back to B), E, G, then F (neighbour of G), then C. A B C D E F G is the breadth-first order, A C F G E B D that of a stack version pushing neighbours in alphabetical order, and A B D E C F G forgets that F and C are reached through G before returning to A.
The iterative version of depth-first search replaces recursion with an explicit …; breadth-first search uses a ….
Show the answer
The iterative version of depth-first search replaces recursion with an explicit stack; breadth-first search uses a queue.
A stack always takes back the last element added, just as a recursive call returns to the last open call.
Finish order: what is it?
Show the answer
The order in which vertices are finished: a vertex is finished once all its neighbours have been explored.
The source is always the last to finish. This order is used for topological sort and for finding strongly connected components.