6.2 Minimum spanning tree algorithms (Kruskal's and Prim's)

Minimum spanning trees (MSTs) are crucial in graph theory, connecting all vertices with the least total edge weight. They're used in network design, clustering, and solving complex problems efficiently.

Two main algorithms find MSTs: Kruskal's and Prim's. Kruskal's sorts edges and builds the tree, while Prim's grows from a starting point. Both are proven correct using the Cut Property and induction.

Understanding Minimum Spanning Trees

Properties of minimum spanning trees

• Minimum Spanning Tree (MST) connects all vertices in weighted, connected graph minimizes total edge weight without cycles
• Contains exactly $n-1$ edges where $n$ is number of vertices
• Unique with distinct edge weights may not be unique with equal weights
• Applications include network design optimizes connectivity costs (computer networks, transportation systems)
• Used in clustering algorithms groups similar data points (image segmentation, customer segmentation)
• Aids approximation algorithms for NP-hard problems provides near-optimal solutions (traveling salesman problem)

Algorithms for Finding Minimum Spanning Trees

Kruskal's algorithm for MST

• Steps:
  1. Sort edges in non-decreasing weight order
  2. Initialize forest with each vertex as separate tree
  3. Iterate through sorted edges
  4. Add edge to MST if it connects different trees
  5. Merge connected trees
  6. Continue until $n-1$ edges added
• Uses disjoint-set data structure for efficient merging and checking (union-find)
• Time Complexity: $O(E \log E)$ or $O(E \log V)$
  • $E$ number of edges $V$ number of vertices
  • Sorting dominates time complexity
• Efficient for sparse graphs fewer edges to sort and process

Prim's algorithm for MST

• Steps:
  1. Start with arbitrary vertex
  2. Maintain set of visited vertices
  3. Add minimum weight edge connecting visited to unvisited vertex
  4. Repeat until all vertices visited
• Uses priority queue for efficient minimum weight edge selection (binary heap, Fibonacci heap)
• Time Complexity:
  • Binary heap: $O((V + E) \log V)$
  • Fibonacci heap: $O(E + V \log V)$
• Efficient for dense graphs processes fewer edges overall

Kruskal's vs Prim's algorithms

• Approach: Kruskal's global considers all edges Prim's local grows single tree
• Efficiency: Kruskal's better for sparse graphs Prim's better for dense graphs
• Implementation: Kruskal's requires edge sorting Prim's needs efficient priority queue
• Memory: Kruskal's stores all edges Prim's stores vertices and adjacent edges
• Parallelization: Kruskal's easier to parallelize Prim's inherently sequential
• Choose based on graph structure and implementation constraints

Correctness proofs of MST algorithms

• Proof strategy uses Cut Property and induction
• Cut Property: Minimum weight edge crossing any cut in graph is in MST
• Kruskal's Proof:
  • Induction on number of edges added
  • Each added edge is safe doesn't create cycle
  • Final tree is spanning and minimum
• Prim's Proof:
  • Induction on number of vertices added to tree
  • Each added edge is minimum weight crossing a cut
  • Final tree is spanning and minimum
• Exchange Argument proves minimality:
  • Non-MST edge can be exchanged with MST edge without increasing total weight
• Both algorithms guaranteed to find correct MST