Cheatsheet
Algorithms: Graph Algorithms
Traversal, ordering, shortest paths, spanning trees and connectivity on one page: which algorithm a graph question needs and what it costs.
ravnary.com/cheatsheets/algorithms-graph-algorithms · Checked against Python 3.14.
Scope
Breadth-first and depth-first search, topological sort, shortest paths, minimum spanning trees and connectivity; graph storage is on the Data Structures sheet.The rule
Traversals visit what is reachable, orderings put every edge forwards, paths and trees sum edge weights, and connectivity finds what holds a graph together.
Choosing
10 choicesWhen You need the cheapest route between every pair of vertices, and there are a few hundred at most
, chooseWhen Edges have no weights, and you need the fewest edges from one start
, chooseWhen Weights are never negative, and you need the cheapest routes from one start
, chooseWhen Some weights are negative, or a negative cycle must be found, from one start
, chooseWhen Tasks depend on other tasks, and you need an order that respects every dependency
, chooseWhen You need the cheapest set of edges joining every vertex, and the graph is dense
, chooseWhen You need the cheapest set of edges joining every vertex
, chooseWhen Links are one-way, and you need the groups whose members can all reach each other
, chooseWhen Links are two-way, and you need the single links or junctions whose loss splits the network
, chooseWhen You need every vertex reachable from a start, or a cycle, in any order
, choose
Traversal
2 entriesBoth visit every vertex reachable from a start, and differ in the order: nearest first, or one path to its end.
A queue visits vertices in order of distance from the start, marking each one as it is queued.
Use when
Edges have no weights, and you need the fewest edges from one start, or the vertices level by level.
Facts
- Time
- O(V + E)
- worst case, with an adjacency list
- Extra space
- O(V)
- worst case, the queue and the visited set
Follow one path until it ends, then back up to the last vertex with an unseen neighbour.
Use when
Every reachable vertex must be visited in any order, or a cycle found in a directed graph.
Facts
- Time
- O(V + E)
- worst case, with an adjacency list
- Call stack
- O(V)
- worst case, one frame per vertex on the current path
- Recursion depth
- 1,000
- by default in Python, beyond which it raises RecursionError
Ordering
2 entriesBoth order a directed acyclic graph so every edge points forwards: one by in-degrees, one by finishing times.
Output a vertex once nothing it depends on is left, keeping a queue of vertices at in-degree 0.
Use when
Tasks depend on other tasks, and you need an order that does each task after what it needs.
Facts
- Time
- O(V + E)
- worst case, each edge lowers one count once
- Extra space
- O(V)
- worst case, the counts and the queue
- Cycle test
- fewer than V output
- in every case, a cycle never reaches in-degree 0
Reverse the order in which a depth-first search finishes the vertices.
Use when
A depth-first search already runs over the graph, and you need an order with every edge forwards.
Facts
- Time
- O(V + E)
- worst case, one depth-first search
- Call stack
- O(V)
- worst case, one frame per vertex on the current path
Shortest paths
3 entriesAll three find the cheapest routes over weighted edges, and differ in negative weights and in how many starts.
Settle the closest unsettled vertex next and relax its edges, using a priority queue.
Use when
Weights are never negative, and you need the cheapest routes from one start.
Facts
- Time
- O((V + E) log V)
- worst case, with a binary heap
- Extra space
- O(V + E)
- worst case, one heap entry per improved distance
- Negative edges
- not allowed
- in any graph, a settled vertex is never looked at again
Relax every edge V − 1 times; one more pass that still lowers a distance proves a negative cycle.
Use when
Some weights are negative, or a negative cycle must be found, and routes start from one vertex.
Facts
- Time
- O(V · E)
- worst case, V − 1 passes over every edge
- Extra space
- O(V)
- worst case, the distances
- Negative cycle check
- O(E)
- every case, one extra pass
Round k lets every route stop at vertex k, keeping a V by V table of the best distances.
Use when
You need the cheapest route between every pair, and there are a few hundred vertices at most.
Facts
- Time
- O(V³)
- every case, three nested loops
- Extra space
- O(V²)
- every case, the distance table
- Negative cycle
- a negative diagonal entry
- in every case, after the last round
Minimum spanning trees
2 entriesBoth join every vertex with the least total weight, and differ in whether they grow a forest or one tree.
Take edges lightest first, skipping any whose ends are already in the same tree.
Use when
A sparse graph, or edges given as a list, and you need the cheapest set joining every vertex.
Facts
- Time
- O(E log E)
- worst case, sorting the edges dominates
- Edges taken
- V − 1
- in every connected graph, so the scan can stop there
Grow one tree from a start, always adding the lightest edge that leaves it.
Use when
A dense graph, and you need the cheapest set of edges joining every vertex.
Facts
- Time
- O(E log V)
- worst case, with a binary heap and stale entries skipped
- Time
- O(V²)
- worst case, scanning for the best edge with no heap
Connectivity
2 entriesBoth find what holds a graph together: groups that reach each other, or the single links between them.
Kosaraju's two passes: finishing order first, then the reversed graph in reverse finishing order.
Use when
Links are one-way, and you need the groups whose members can all reach each other.
Facts
- Time
- O(V + E)
- worst case, two depth-first passes
- Extra space
- O(V + E)
- worst case, the reversed graph
One depth-first search compares each vertex's discovery time with the earliest its subtree reaches.
Use when
Links are two-way, and you need the single links or junctions whose loss splits the network.
Facts
- Time
- O(V + E)
- worst case, one depth-first search
- Bridge test
- low[child] > disc[parent]
- for every edge from a parent to its child
- Articulation test
- low[child] ≥ disc[parent]
- for every vertex but the root, which needs two children
Side by side
2 tables| Algorithm | Pairs | Negative edges | Negative cycles | Time | Space | Strategy |
|---|---|---|---|---|---|---|
| Dijkstra's algorithm | One source to every vertex | Not allowed | Not detected | O((V + E) log V) | O(V + E) | Greedy: settle the closest vertex and never revisit it |
| Bellman-Ford | One source to every vertex | Allowed | Reported by one extra pass | O(V · E) | O(V) | Dynamic programming over the number of edges in a path |
| Floyd-Warshall | Every pair | Allowed | Reported by a negative entry on the diagonal | O(V³) | O(V²) | Dynamic programming over which vertices may be stops |
| Question | Graph | Tool | Time |
|---|---|---|---|
| Are these two vertices connected, while edges keep arriving? | Undirected, edges added only | Union-find | Close to O(1) per edge or question |
| What are the connected parts, or what can this vertex reach? | Fixed; undirected for parts, either for reach | Breadth-first or depth-first search | O(V + E) for the whole graph |
| Which vertices can each reach the other? | Directed, fixed | Strongly connected components, by Kosaraju's two passes | O(V + E) |
| Which single edge or vertex, if it failed, would split the graph? | Undirected, fixed | Bridges and articulation points, from low values | O(V + E) |
Common mistakes
5 mistakesMarking a vertex visited when it leaves the queue, so it can be queued many times over.
Expecting one correct topological order, when any order with every edge forwards is right.
Running Dijkstra's algorithm on a negative edge, which can leave a vertex settled too high.
Reading shortest paths from a minimum spanning tree, which keeps the total low, not each route.
Running Kosaraju's second pass on the original graph, which merges components that should stay apart.
Learn it
5 topicsGraph Traversal6 questions
PractiseTopological Sort4 questions
PractiseShortest Paths6 questions
PractiseMinimum Spanning Trees4 questions
PractiseGraph Connectivity3 questions
Practise