Prim‘s algorithm is a fundamental algorithm in computer science used to find the minimum spanning tree of a weighted, undirected graph. A minimum spanning tree is a subset of edges in a connected, undirected graph that connects all the vertices together with the minimum total edge weight. Minimum spanning trees have important applications in fields like computer networks, transportation, and circuit design.
In this comprehensive guide, we‘ll take a deep dive into how Prim‘s algorithm works, prove its correctness, analyze its efficiency, and see how to implement it in code. Whether you‘re a computer science student or a developer brushing up on your algorithm fundamentals, understanding Prim‘s algorithm is valuable knowledge to have. Let‘s get started!
Overview of Prim‘s Algorithm
Prim‘s algorithm is a greedy algorithm that builds the minimum spanning tree one vertex at a time. It starts with an arbitrary root vertex and grows the MST by adding the cheapest possible connection from the tree to another vertex not in the tree. This process is repeated until all vertices are included in the tree.
Here are the high-level steps of Prim‘s algorithm:
- Initialize an empty set to keep track of vertices already in MST.
- Assign key values to all vertices. Set root vertex key to 0 so it is picked first, and others to infinity.
- While there are vertices not in MST:
A) Pick the vertex with minimum key value not already in MST and add it to MST set.
B) Update the key values of adjacent vertices not in MST. If any adjacent vertex‘s key decreases, set its parent to picked vertex. - Return the set of edges in the constructed minimum spanning tree.
The key insight of Prim‘s algorithm is this greedy choice property: The edges already included in the MST at any step are the best possible ones with minimum total weight. So Prim‘s maintains an invariant that the currently constructed sub-tree is always a subset of the final MST.
Proof of Correctness
Here is a formal proof by contradiction that Prim‘s algorithm correctly constructs a minimum spanning tree:
Suppose the set of edges T returned by Prim‘s algorithm is not a minimum spanning tree. Consider the first edge e = (v,u) added to T that is not part of the actual MST M. At the point right before e was added to T, there must have been a path from the root to u, using vertices entirely in T, as well as a path from root to u in the true MST M.
These two paths form a cycle containing the edge e. The rest of the cycle minus e must consist alternately of edges in T and M. Let f be the edge in M that is adjacent to u. Since Prim‘s picked e over f to add to T, it must be the case that the weight of e is less than or equal to the weight of f.
If we cut the cycle at e and f, deleting e and adding f to T would form a new spanning tree. The weight of this new tree would be the same as T if e and f have equal weights, or less than T if f is heavier than e. But T was presumed to be the MST, so this is a contradiction. Therefore, Prim‘s algorithm must construct the correct MST.
Comparison to Kruskal‘s Algorithm
Prim‘s algorithm is quite similar to Kruskal‘s algorithm, another well-known algorithm for finding minimum spanning trees. The main difference is in how the two algorithms greedily decide which edges to add:
-
Prim‘s algorithm works by building the tree one vertex at a time, always adding the cheapest edge that connects the tree to a new vertex.
-
Kruskal‘s algorithm works by always adding the globally cheapest edge that doesn‘t produce a cycle, regardless of whether it connects to the current tree.
Both algorithms have the same overall effect of incrementally growing the MST with the cheapest edges. The choice of which algorithm to use depends on the representation of the graph and density of edges:
-
Prim‘s algorithm can be faster when the graph is dense and the priority queue operations dominate. It has better locality of reference.
-
Kruskal‘s algorithm can be faster when the graph is sparse and the sorting step dominates the process. It has a lower total time complexity.
In general, Prim‘s performs better on dense graphs with many edges, while Kruskal‘s works better on sparse graphs with fewer edges. The asymptotic time complexity is the same for both.
Time Complexity
The time complexity of Prim‘s algorithm depends on the data structures used for the graph representation and priority queue. Here is the complexity for the two most common implementations:
-
Adjacency matrix graph representation and array-based priority queue: The total time is O(V^2), where V is the number of vertices. This is because we search through all V vertices to find the minimum key value each iteration.
-
Adjacency list graph representation and binary heap priority queue: The total time is O((V+E)logV), where V is number of vertices and E is number of edges. This is because each of the V iterations requires O(logV) time to extract the minimum key vertex, and there are O(E) updates to the priority queue which cost O(logV) each.
In most cases, it‘s more efficient to use the binary heap and adjacency list, especially for sparse graphs where E is much smaller than V^2. But for dense graphs the adjacency matrix can be competitive.
Pseudocode
Here is the pseudocode for Prim‘s algorithm using a binary heap priority queue:
function PrimMST(Graph, root):
for each vertex v in Graph:
dist[v] = INFINITY
prev[v] = NULL
add v to Q (priority queue)
dist[root] = 0
while Q is not empty:
u = extract_min(Q)
for each neighbor v of u:
if v in Q and dist[v] > weight(u, v):
dist[v] = weight(u, v)
prev[v] = u
decrease_key(Q, v)
return tree from prev arrayHere is an equivalent version using an adjacency matrix:
function PrimMST(Graph[V][V], root):
selected[V] = {false}
dist[V] = {INFINITY}
dist[root] = 0
for i = 1 to V:
u = minimumdist(dist, selected)
selected[u] = true
for each neighbor v of u:
if selected[v] == false and Graph[u][v] < dist[v]:
dist[v] = Graph[u][v]
prev[v] = u
return tree from prev arrayCode Implementation
Here is an implementation of Prim‘s algorithm in Python using an adjacency list graph representation:
from collections import defaultdict
import heapq
def prim(graph, start):
mst = defaultdict(set)
visited = set([start])
edges = [(cost, start, to) for to, cost in graph[start].items()]
heapq.heapify(edges)
while edges:
cost, frm, to = heapq.heappop(edges)
if to not in visited:
visited.add(to)
mst[frm].add(to)
for to_next, cost in graph[to].items():
if to_next not in visited:
heapq.heappush(edges, (cost, to, to_next))
return mst
graph = {
‘A‘: {‘B‘: 2, ‘C‘: 3},
‘B‘: {‘A‘: 2, ‘C‘: 1, ‘D‘: 1, ‘E‘: 4},
‘C‘: {‘A‘: 3, ‘B‘: 1, ‘F‘: 5},
‘D‘: {‘B‘: 1, ‘E‘: 1},
‘E‘: {‘B‘: 4, ‘D‘: 1, ‘F‘: 1},
‘F‘: {‘C‘: 5, ‘E‘: 1, ‘G‘: 1},
‘G‘: {‘F‘: 1},
}
print(dict(prim(graph, ‘A‘)))And here is an implementation in Java using an adjacency matrix:
import java.util.*;
class Graph {
int vertices;
int matrix[][];
public Graph(int vertex) {
this.vertices = vertex;
matrix = new int[vertex][vertex];
}
public void addEdge(int source, int destination, int weight) {
matrix[source][destination] = weight;
matrix[destination][source] = weight;
}
int getMinimumVertex(boolean [] mst, int [] key){
int minKey = Integer.MAX_VALUE;
int vertex = -1;
for (int i = 0; i < vertices ; i++) {
if(mst[i]==false && minKey>key[i]){
minKey = key[i];
vertex = i;
}
}
return vertex;
}
class ResultSet{
int parent;
int weight;
}
public void primMST(){
boolean[] mst = new boolean[vertices];
ResultSet[] resultSet = new ResultSet[vertices];
int [] key = new int[vertices];
for (int i = 0; i <vertices ; i++) {
key[i] = Integer.MAX_VALUE;
resultSet[i] = new ResultSet();
}
key[0] = 0;
resultSet[0] = new ResultSet();
resultSet[0].parent = -1;
for (int i = 0; i <vertices ; i++) {
int vertex = getMinimumVertex(mst, key);
mst[vertex] = true;
for (int j = 0; j <vertices ; j++) {
if(matrix[vertex][j]>0){
if(mst[j]==false && matrix[vertex][j]<key[j]){
key[j] = matrix[vertex][j];
resultSet[j].parent = vertex;
resultSet[j].weight = key[j];
}
}
}
}
printMST(resultSet);
}
public void printMST(ResultSet[] resultSet){
int total_min_weight = 0;
System.out.println("Minimum Spanning Tree: ");
for (int i = 1; i <vertices ; i++) {
System.out.println("Edge: " + i + " - " + resultSet[i].parent +
" key: " + resultSet[i].weight);
total_min_weight += resultSet[i].weight;
}
System.out.println("Total minimum key: " + total_min_weight);
}
public static void main(String[] args) {
Graph graph = new Graph(6);
graph.addEdge(0, 1, 4);
graph.addEdge(0, 2, 3);
graph.addEdge(1, 2, 1);
graph.addEdge(1, 3, 2);
graph.addEdge(2, 3, 4);
graph.addEdge(3, 4, 2);
graph.addEdge(4, 5, 6);
graph.primMST();
}
}Applications
Prim‘s algorithm has numerous real-world applications in domains like networks, circuit design, transportation, and more. Here are a few examples:
-
Designing telecommunication networks: Telephone companies often need to lay out physical wires to connect subscribers. Using Prim‘s algorithm ensures the network has minimum wire length.
-
Traveling Salesman Problem approximation: The TSP asks for the shortest route visiting all cities exactly once. While finding the exact solution is NP-hard, constructing a MST and doing a preorder traversal gives a 2-approximate solution.
-
Cluster analysis: Prim‘s algorithm can be used to perform hierarchical clustering of data points based on pairwise similarity measures. The algorithm represents clustering as a MST problem.
-
Image segmentation: In computer vision, segmenting an image into meaningful components can be modeled as a graph partition problem. Prim‘s algorithm helps find regions with minimal variation.
-
Designing power grids: Transmitting power from plants to consumers requires an efficient network of transmission lines. The MST found by Prim‘s algorithm ensures minimal resource usage.
-
Circuit design: In VLSI chip design and wiring layouts, Prim‘s algorithm helps minimize total wire length and signal interference.
-
Transportation networks: In road, rail, or pipeline construction, Prim‘s algorithm can model the most cost-effective way to connect a set of locations.
As you can see, the applications are incredibly diverse! Prim‘s is a powerful tool in a computer scientist‘s toolkit for modeling and optimizing a wide variety of network design problems.
Conclusion
Prim‘s algorithm is a classic example of a simple yet brilliant algorithmic idea – greedily grow the minimum spanning tree by adding the cheapest edge that expands it. With an efficient implementation using a binary heap, it solves the MST problem in near-linearithmic time.
I hope this in-depth guide helped you understand the inner workings of Prim‘s algorithm! Studying classic algorithms like Prim‘s is an excellent way to develop your algorithmic thinking and problem-solving skills as a programmer. Try implementing it yourself in a language of your choice, and let me know how it goes.
Happy coding, and thank you for reading!
