Depth-First Search (DFS) on a Graph
On the stack
- A
Visit order
- A
- Not reached
- Waiting
- Current
- Finished
1/20
Start at A. Depth-first follows one branch as far as it goes.
Settings
Graph
More options
Depth-First
- 1
stack = [start] - 2
while stack: - 3
node = stack.top - 4
if node has an unseen neighbour: - 5
mark it seen - 6
stack.push(it) - 7
else: - 8
stack.pop() // done here
What Each One Answers
| Algorithm | What it answers | Time | Needs |
|---|---|---|---|
| Breadth-First | Fewest hops from the start | O(V + E) | A queue |
| Depth-First | Reachability, one branch at a time | O(V + E) | A stack |
| Cycle Detection | Whether there is a cycle, and where | O(V + E) | Node colours |
| Topological Sort | A valid order to do the work in | O(V + E) | No cycles |
| Dijkstra | Cheapest path by edge weight | O(E log V) | Non-negative weights |
Scroll the table sideways for the rest of the columns.
V is the number of nodes and E the number of edges. On the graph with a cycle, topological sort gets stuck, because a cycle leaves no valid order.