🧩Intro to Algorithms Unit 9 – Kruskal's and Prim's Minimum Spanning Trees

Key Concepts

• Minimum Spanning Trees (MSTs) find the subset of edges in a weighted, connected graph that connects all vertices with minimum total edge weight
• MSTs have applications in network design, transportation networks, and clustering algorithms
• Kruskal's algorithm builds the MST by greedily adding the smallest weight edge that doesn't create a cycle
• Prim's algorithm grows the MST from a starting vertex, greedily adding the smallest weight edge that connects a new vertex to the tree
• Both algorithms use greedy approaches to find the optimal solution
  • Greedy algorithms make the locally optimal choice at each stage, leading to a globally optimal solution
• MSTs are unique for a graph if all edge weights are distinct
• MSTs may not be unique if there are edges with equal weights

Graph Theory Basics

• Graphs consist of a set of vertices (nodes) and a set of edges connecting pairs of vertices
• Edges can be undirected (bidirectional) or directed (one-way)
• Weighted graphs assign a numerical value (weight) to each edge, representing cost, distance, or capacity
• A path is a sequence of vertices connected by edges
• A cycle is a path that starts and ends at the same vertex, with no repeated edges
• A connected graph has a path between every pair of vertices
• A tree is a connected, acyclic graph (no cycles)
  • In a tree, there is exactly one path between any pair of vertices

Minimum Spanning Tree (MST) Overview

• An MST is a tree that spans all vertices in a weighted, connected graph with the minimum total edge weight
• MSTs are useful for finding the cheapest way to connect all nodes in a network
• The total number of edges in an MST is always one less than the number of vertices (|V| - 1)
• For a graph with |V| vertices, the maximum number of edges in an MST is |V| - 1
• The minimum number of edges required for a connected graph is also |V| - 1
• MSTs are not necessarily unique if the graph has edges with equal weights
• Removing any edge from an MST disconnects the graph into two components

Kruskal's Algorithm

• Kruskal's algorithm is a greedy algorithm that finds an MST for a weighted, connected graph
• It builds the MST by repeatedly adding the smallest weight edge that doesn't create a cycle
• The algorithm maintains a forest (a collection of trees) and merges trees by adding edges
• It uses a disjoint set data structure to efficiently check for cycles and merge trees
  • Each vertex is initially in its own set (tree)
  • The

    find

    operation determines the set a vertex belongs to
  • The

    union

    operation merges two sets (trees) when adding an edge
• Kruskal's algorithm guarantees an optimal solution (MST) by the greedy choice property and optimal substructure

Prim's Algorithm

• Prim's algorithm is another greedy algorithm for finding an MST in a weighted, connected graph
• It starts with a single vertex and grows the MST by repeatedly adding the smallest weight edge that connects a new vertex to the tree
• The algorithm maintains two sets: vertices already in the MST and vertices not yet in the MST
• It uses a priority queue (min-heap) to efficiently select the minimum weight edge connecting a new vertex to the MST
  • The priority queue stores edges, with the edge weight as the key
• At each step, Prim's algorithm adds the vertex connected by the minimum weight edge to the MST
• Like Kruskal's algorithm, Prim's algorithm guarantees an optimal solution (MST) by the greedy choice property and optimal substructure

Algorithm Comparison

• Both Kruskal's and Prim's algorithms find an MST in a weighted, connected graph
• Kruskal's algorithm builds the MST by adding edges, while Prim's algorithm grows the MST from a starting vertex
• Kruskal's algorithm is better suited for sparse graphs (fewer edges) because it iterates over edges
• Prim's algorithm is more efficient for dense graphs (many edges) because it uses a priority queue to select the minimum weight edge
• The time complexity of Kruskal's algorithm is $O(E \log E)$ or $O(E \log V)$ using a disjoint set data structure and sorting edges
• The time complexity of Prim's algorithm is $O((V + E) \log V)$ using a binary heap priority queue, or $O(E + V \log V)$ using a Fibonacci heap

Implementation and Complexity

• Implementing Kruskal's algorithm requires a disjoint set data structure and a way to sort edges by weight
  • The disjoint set data structure can be implemented using an array or a tree-based approach (union by rank, path compression)
  • Sorting edges takes $O(E \log E)$ time using a comparison-based sorting algorithm
• Implementing Prim's algorithm requires a priority queue (min-heap) and an adjacency list or matrix representation of the graph
  • A binary heap priority queue can be implemented using an array, with $O(\log V)$ time for insertions and deletions
  • An adjacency list allows for efficient traversal of a vertex's neighbors
• The space complexity of both algorithms is $O(V + E)$ to store the graph and additional data structures
• Kruskal's algorithm can be parallelized by processing edges concurrently, while Prim's algorithm is more challenging to parallelize effectively

Real-World Applications

• MSTs have numerous applications in network design, including computer networks, telecommunication networks, and transportation networks
  • Designing a network topology with minimum cost while ensuring connectivity between all nodes
• In transportation networks, MSTs can be used to find the cheapest way to connect cities or airports
  • Road networks connecting cities with minimum total road length
  • Flight networks connecting airports with minimum total distance
• MSTs are used in clustering algorithms, such as single-linkage clustering, to group similar objects based on their pairwise distances
• In image segmentation, MSTs can be used to identify connected regions with similar pixel values
• MSTs can be applied to find the minimum cost of laying pipelines or electrical wiring to connect all buildings in a city
• In circuit design, MSTs are used to minimize the total wire length connecting components on a printed circuit board (PCB)