Graph Algorithms

Overview

Traversing and Optimizing

Graph algorithms are among the most important in computer science. They solve problems like finding the shortest route between cities, detecting cycles in dependencies, and building efficient networks.

Definition

Breadth-First Search (BFS)

BFS explores a graph level by level, starting from a source vertex s. It uses a queue.

1. Visit s, add it to the queue. 2. While the queue is not empty: dequeue a vertex v, visit all unvisited neighbors of v, and enqueue them.

BFS finds the shortest path (fewest edges) from s to every other vertex. Time complexity: O(|V| + |E|).

Definition

Depth-First Search (DFS)

DFS explores a graph by going as deep as possible before backtracking. It uses a stack (or recursion).

1. Visit s, push it onto the stack. 2. While the stack is not empty: peek at the top vertex v. If v has an unvisited neighbor w, visit w and push it. Otherwise, pop v.

DFS is useful for detecting cycles, topological sorting, and finding connected components. Time complexity: O(|V| + |E|).

Definition

Dijkstra's Algorithm

Dijkstra's algorithm finds the shortest weighted path from a source vertex to all other vertices in a graph with non-negative edge weights.

1. Set dist(s) = 0, dist(v) = ∞ for all other v. 2. Mark all vertices as unvisited. 3. Pick the unvisited vertex u with smallest dist(u). 4. For each neighbor v of u: if dist(u) + weight(u,v) < dist(v), update dist(v). 5. Mark u as visited. Repeat from step 3.

Time complexity: O(|V|² ) or O((|V| + |E|) log |V|) with a priority queue.

Definition

Prim's and Kruskal's Algorithms

Both find a minimum spanning tree (MST) of a weighted connected graph.

Prim's: Start with any vertex. Repeatedly add the cheapest edge that connects a tree vertex to a non-tree vertex.

Kruskal's: Sort all edges by weight. Add edges in order, skipping any that would create a cycle.

Both are greedy algorithms and produce optimal MSTs.

Example

Kruskal's Algorithm Example

Consider a graph with edges: {A,B}=1, {B,C}=4, {A,C}=3, {C,D}=2, {B,D}=5.

Sorted edges: {A,B}=1, {C,D}=2, {A,C}=3, {B,C}=4, {B,D}=5.

Kruskal's picks: 1. {A,B}=1 ✓ (no cycle) 2. {C,D}=2 ✓ (no cycle) 3. {A,C}=3 ✓ (no cycle, connects the two components)

MST weight = 1 + 2 + 3 = 6. We have 4 vertices and 3 edges - done!