Graph Algorithms
One small directed graph, with and without a cycle. Watch breadth-first and depth-first spread differently, catch the edge that closes a cycle, and follow Dijkstra settling the cheapest route.
In the queue
- A
Visit order
Nothing yet.
- Not reached
- Waiting
- Current
- Finished
Speed
Step 1 of 20
Start at A. Breadth-first keeps a queue, so nearer nodes come out first.
Counters
- Visited
- 0/8
- In the queue
- 1
- Nodes
- 8
- Edges
- 10
Settings
Algorithm
Graph
Breadth-first
- 1
queue = [start]; seen = {start} - 2
while queue: - 3
node = queue.shift() - 4
for each neighbour: - 5
if neighbour not in seen: - 6
seen.add(neighbour) - 7
queue.push(neighbour)
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 | Does a cycle exist, 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 |
V is the node count and E the edge count. Switch the graph to Has a cycle and the topological sort will get stuck - that is the connection between the two.