Graph Algorithms
Traversal, shortest paths, and spanning trees — with the one to reach for in each case.
Traversal
- BFS
- queue, level by level ·
O(V + E)· shortest path by edge count on unweighted graphs - DFS
- stack / recursion ·
O(V + E)· cycle detection, topological sort, connected components - Topological sort
- DFS post-order or Kahn (BFS on in-degrees) ·
O(V + E)· DAGs only — order tasks by dependency
Shortest paths
- BFS (unweighted)
O(V + E)· fewest edges from a source — no weights- Dijkstra
- single-source, non-negative weights ·
O((V + E) log V)with a binary heap - Bellman–Ford
- single-source, handles negative edges · detects negative cycles ·
O(V·E) - Floyd–Warshall
- all-pairs, negatives OK (no negative cycle) ·
O(V³)· spaceO(V²) - A*
- Dijkstra + heuristic · faster to a single target when a good admissible heuristic exists
Minimum spanning tree
- Kruskal
- sort edges + union-find, add if no cycle ·
O(E log E)· great for sparse graphs - Prim
- grow the tree from a node with a min-heap ·
O((V + E) log V)· great for dense graphs
Which to use
- Unweighted shortest path
- BFS — fewest edges,
O(V + E) - Non-negative weights
- Dijkstra with a heap
- Negative edges present
- Bellman–Ford (and it flags negative cycles)
- All-pairs shortest paths
- Floyd–Warshall on small/dense graphs
- Cheapest connecting tree
- Kruskal (sparse) or Prim (dense)
- Order with dependencies
- Topological sort (DFS or Kahn)
- Connectivity / cycles
- Union-Find or a DFS