Graph algorithms form the backbone of countless real-world systems — from GPS navigation and social networks to compiler design and circuit layout. This cheat sheet covers the full spectrum: graph representations, traversals, shortest-path algorithms (single-source and all-pairs), minimum spanning trees, union-find, topological ordering, cycle detection, strongly connected components, and advanced heuristic search. Entries are ordered from foundational to specialized, and within each table from most-used to most-obscure.
What This Cheat Sheet Covers
This topic spans 12 focused tables and 48 indexed concepts. Below is a complete table-by-table outline of this topic, spanning foundational concepts through advanced details.
Table 1: Graph Representations
Before choosing an algorithm, the right data structure determines time and space efficiency. Adjacency lists are the default for sparse graphs; matrices suit dense graphs or when O(1) edge lookup is needed; edge lists are the input format for many sorting-based algorithms like Kruskal's.
| Representation | Example | Description |
|---|---|---|
graph = [[] for _ in range(V))graph[u].append((v, w)) | Array of lists where graph[u] stores (neighbor, weight) pairs. Space O(V+E) — optimal for sparse graphs. Standard choice for BFS, DFS, Dijkstra, and most traversal algorithms. | |
dist = [[INF]*V for _ in range(V)]dist[u][v] = w | V \times V matrix where dist[u][v] = edge weight or \infty. Space O(V^2) — O(1) edge lookup; required for Floyd-Warshall. Wasteful for sparse graphs. |