Graph Algorithms
Pick the right representation (adjacency lists for sparse graphs), then match the problem to the algorithm: BFS for unweighted shortest paths, DFS for structure (components, cycles, topological order), Dijkstra for non-negative weights, Bellman–Ford for negative edges, and Kruskal or Prim for minimum spanning trees.
Key points
- 1
Adjacency lists use O(V + E) memory and make BFS and DFS O(V + E); a matrix is O(V²) and only suits dense graphs or constant-time edge checks.
- 2
BFS with a FIFO queue gives fewest-edge distances; mark vertices visited when you enqueue them, and use multi-source BFS for spreading problems such as rotting oranges.
- 3
Cycle detection differs by direction: undirected graphs use parent tracking or union-find; directed graphs use three colours (an edge to an on-stack vertex) or Kahn's algorithm outputting fewer than V vertices.
- 4
Dijkstra (binary heap, O((V + E) log V)) requires non-negative weights; Bellman–Ford handles negative edges in O(V·E) and detects reachable negative cycles in a V-th round.
- 5
Special cases: 0-1 BFS with a deque for weights in {0, 1}; Floyd–Warshall O(V³) for all pairs, with k as the outermost loop; A* = Dijkstra plus an admissible heuristic.
- 6
MSTs minimise total weight (Kruskal: sort edges plus union-find; Prim: grow from one vertex), but tree paths are not shortest paths.
- 7
Hop-limited shortest paths (at most k stops) need state (node, hops) or Bellman–Ford rounds that relax from the previous round's snapshot.
Common traps
Forgetting to start a new traversal from every unvisited vertex, which silently skips disconnected components.
Using "neighbour already visited means a cycle" on directed graphs: diamonds are not cycles.
Recursive DFS on deep graphs in Python hits the default recursion limit of 1,000; use an explicit stack.
Test yourself on Graph Algorithms
Ten questions, with the answer and explanation after each one.