Algorithms on Graphs
Algorithms on Graphs
Graph algorithms transform structural properties into efficient computation. Breadth-first search (BFS) and depth-first search (DFS) explore graphs in $O(V+E)$; DFS discovers connected components, topological orderings, and biconnected components. Dijkstra's algorithm finds shortest paths in $O(E\log V)$; the Bellman-Ford algorithm handles negative edges. These algorithms underlie GPS navigation, web crawlers, social network analysis, and compiler construction.
BFS, DFS & Connectivity
BFS from source $s$: explore vertices in order of distance from $s$ (uses a queue). DFS: explore as deep as possible first (uses a stack/recursion). Both run in $O(V+E)$. DFS produces a DFS tree and classifies edges as tree/back/forward/cross. Applications: BFS finds shortest paths (unweighted); DFS finds strongly connected components (Kosaraju, Tarjan), articulation points, bridges, and topological sort of DAGs. Tarjan's algorithm: SCCs in $O(V+E)$ via DFS timestamps and a stack.
Shortest Paths: Dijkstra & Bellman-Ford
Dijkstra's algorithm (non-negative weights): maintain tentative distances $d[v]$; greedily extract the vertex $u$ with minimum $d[u]$, relax neighbors. With a min-heap: $O(E\log V)$. Correct because shortest paths have an optimal substructure. Bellman-Ford (may have negative edges, no negative cycles): relax all edges $V-1$ times. Detects negative cycles by checking if a $V$-th relaxation succeeds. All-pairs shortest paths: Floyd-Warshall $O(V^3)$ via $d^{(k)}[i][j]=\min(d^{(k-1)}[i][j],d^{(k-1)}[i][k]+d^{(k-1)}[k][j])$.
Example 1
Run Dijkstra on a graph with vertices $\{s,a,b,t\}$ and edges $s\to a:2, s\to b:5, a\to b:1, a\to t:6, b\to t:3$.
Solution: Init: $d=[\infty,\infty,\infty,\infty]$, $d[s]=0$. Extract $s$: relax $a$ ($d[a]=2$), $b$ ($d[b]=5$). Extract $a$ ($d=2$): relax $b$ ($d[b]=\min(5,3)=3$), $t$ ($d[t]=8$). Extract $b$ ($d=3$): relax $t$ ($d[t]=\min(8,6)=6$). Extract $t$ ($d=6$). Shortest paths: $s\to a:2$; $s\to a\to b:3$; $s\to a\to b\to t:6$.
Example 2
Find strongly connected components of the graph: $1\to 2$, $2\to 3$, $3\to 1$, $3\to 4$, $4\to 5$, $5\to 4$.
Solution: Kosaraju's: DFS on $G$, record finish times: order (by finish) $5,4,3,2,1$? Let's trace: start DFS from 1. 1→2→3→1 (back edge, 3 finishes, 2 finishes after 3), then 3→4→5→4 (back edge, 5 finishes, 4 finishes). Order: 5,4,2 (wait—need careful trace). SCCs by inspection: $\{1,2,3\}$ (cycle), $\{4,5\}$ (cycle), no edges between except $3\to 4$. Topological order of SCCs: $\{1,2,3\}\to\{4,5\}$.
Practice
- Prove Dijkstra's algorithm is correct for graphs with non-negative edge weights.
- Describe how to detect a negative cycle using Bellman-Ford.
- Show that a DAG has a topological sort, and describe the DFS-based algorithm.
- Apply Kruskal's and Prim's algorithms to the same graph and show they give the same MST.
Show Answer Key
1. Dijkstra maintains distances $d[v]$ initialized to $\infty$ ($d[s]=0$). At each step, extract the minimum-$d$ unvisited vertex $u$ and relax its neighbors. Correctness: when $u$ is extracted, $d[u]$ is the true shortest distance (by induction: any shorter path would pass through an unvisited vertex with $d[\cdot]\ge d[u]$, impossible with non-negative weights).
2. Run Bellman-Ford for $|V|-1$ iterations. Then do one more iteration: if any distance decreases, a negative cycle exists (reachable from the source). Proof: after $|V|-1$ iterations, all shortest paths (which have $\le|V|-1$ edges) are found. A further decrease means a shorter walk exists, which is only possible via a negative cycle.
3. A DAG (directed acyclic graph) has a vertex with in-degree 0 (otherwise follow predecessors to get a cycle). Place it first, remove it, and repeat — this produces a topological ordering. DFS-based: run DFS; output vertices in reverse finish-time order. A back edge would imply a cycle (contradicting DAG), so the reverse-finish order is a valid topological sort.
4. Both Kruskal's (sort edges, add if no cycle) and Prim's (grow tree greedily) find MSTs. They may process edges in different order but produce the same total weight. If all edge weights are distinct, the MST is unique, so both algorithms give the identical tree.