Prim's Algorithm

1. Introduction

Prim's algorithm, originally developed by Vojtech Jarnik in 1930 and independently rediscovered by Robert C. Prim in 1957 and Edsger Dijkstra in 1959, is a greedy algorithm that finds a minimum spanning tree (MST) for a connected, undirected, weighted graph. The algorithm grows the MST one vertex at a time, always adding the cheapest edge that connects a vertex inside the tree to a vertex outside it.

The algorithm bears a structural resemblance to Dijkstra's shortest path algorithm -- both use a priority queue and grow outward from a starting vertex. However, while Dijkstra minimizes the total distance from the source, Prim's algorithm minimizes the individual edge weight added at each step.

"At every stage of the algorithm, we maintain a tree that is a subtree of the minimum spanning tree. We grow this tree by one edge at a time: we add the minimum weight edge that has exactly one endpoint in the tree." -- Robert Sedgewick, Algorithms

2. How It Works

Prim's algorithm maintains a partition of the vertices into two sets: those already included in the growing MST and those not yet included. At each step, it finds the minimum-weight edge that crosses this partition (one endpoint in the tree, one outside) and adds it to the MST.

1. Start: Choose an arbitrary vertex as the starting point. Initialize a priority queue with all edges from this vertex.
2. Select: Extract the minimum-weight edge from the priority queue that connects to a vertex not yet in the MST.
3. Add: Add the selected edge and the new vertex to the MST. Insert all edges from the newly added vertex to vertices not yet in the MST into the priority queue.
4. Repeat: Continue selecting and adding until all vertices are included in the MST, or the priority queue is empty.

3. Algorithm and Pseudocode

functionPrim(Graph, startVertex): MST = empty set visited = empty set PQ = MinPriorityQueue() // Start from the chosen vertex visited.add(startVertex) for each edge (startVertex, v, w) in Graph.adjacency[startVertex]: PQ.insert((w, startVertex, v)) while PQ is not empty and |visited| < |Graph.vertices|: (weight, u, v) = PQ.extractMin() if v in visited: continue// Add edge and vertex to MST MST.add((u, v, weight)) visited.add(v) // Add edges from newly added vertexfor each edge (v, neighbor, w) in Graph.adjacency[v]: if neighbor not in visited: PQ.insert((w, v, neighbor)) return MST

Alternative: Key-Based Approach

functionPrimWithKeys(Graph, startVertex): key[v] = INFINITY for all v parent[v] = NULL for all v inMST[v] = falsefor all v key[startVertex] = 0 PQ = MinPriorityQueue(all vertices, keyed by key[]) while PQ is not empty: u = PQ.extractMin() inMST[u] = truefor each neighbor v of u with weight w: if not inMST[v] and w < key[v]: key[v] = w parent[v] = u PQ.decreaseKey(v, w) return parent[] // MST edges: (parent[v], v) for all v != start

4. Complexity Analysis

For dense graphs where E = O(V^2), the simple adjacency matrix approach with O(V^2) time is both simple and optimal. For sparse graphs, the binary heap implementation is practical and efficient. The Fibonacci heap offers the best theoretical bound but is rarely used in practice due to high constant factors.

5. Worked Example

Consider a connected undirected graph with 7 vertices (A-G):

Starting vertex: A

Step-by-Step Trace

Step 1: Start with A

MST vertices: {A}. Add edges from A to PQ:

• A-B (7), A-D (5)

Step 2: Extract A-D (weight 5)

MST vertices: {A, D}. MST edges: {A-D(5)}. Add edges from D:

• PQ now contains: A-B(7), D-B(9), D-E(15), D-F(6)

Step 3: Extract D-F (weight 6)

MST vertices: {A, D, F}. MST edges: {A-D(5), D-F(6)}. Add edges from F:

• PQ now contains: A-B(7), D-B(9), D-E(15), E-F(8), F-G(11)

Step 4: Extract A-B (weight 7)

MST vertices: {A, D, F, B}. MST edges: {A-D(5), D-F(6), A-B(7)}. Add edges from B:

• PQ now contains: B-C(8), B-E(7), D-B(9-skip), D-E(15), E-F(8), F-G(11)

Step 5: Extract B-E (weight 7)

MST vertices: {A, D, F, B, E}. MST edges: {A-D(5), D-F(6), A-B(7), B-E(7)}. Add edges from E:

• PQ now contains: B-C(8), C-E(5), D-E(15-skip), E-F(8-skip), E-G(9), F-G(11)

Step 6: Extract C-E (weight 5)

MST vertices: {A, D, F, B, E, C}. MST edges: {A-D(5), D-F(6), A-B(7), B-E(7), C-E(5)}.

Step 7: Extract E-G (weight 9)

MST vertices: {A, D, F, B, E, C, G}. MST edges: {A-D(5), D-F(6), A-B(7), B-E(7), C-E(5), E-G(9)}.

Final MST

Total MST weight: 5 + 5 + 6 + 7 + 7 + 9 = 39

6. Priority Queue Considerations

The efficiency of Prim's algorithm depends heavily on the priority queue implementation. There are two common approaches:

Lazy Approach (Edge-Based PQ)

Insert edges into the priority queue and skip edges whose destination vertex is already in the MST. This is simpler to implement but may store up to E entries in the queue. This approach avoids the need for a decrease-key operation.

Eager Approach (Vertex-Based PQ with Decrease-Key)

Maintain at most V entries in the priority queue, one per vertex, storing the minimum weight edge connecting each non-MST vertex to the MST. This requires a decrease-key operation when a lighter edge to a vertex is discovered.

7. Advantages and Disadvantages

Advantages

• Efficient for dense graphs: With an adjacency matrix, the O(V^2) implementation is optimal for dense graphs.
• Grows from a single source: The resulting MST is naturally rooted at the starting vertex, which is useful in some applications.
• Online capability: Can process edges as they are discovered, useful in graph exploration scenarios.
• Works well with adjacency lists: Integrates naturally with adjacency list graph representations.
• Similar to Dijkstra: Programmers familiar with Dijkstra's algorithm can easily adapt to Prim's.

Disadvantages

• Requires connected graph: Does not naturally handle disconnected graphs (must be run on each component separately).
• Priority queue overhead: Heap-based implementations have higher constant factors than Kruskal's Union-Find.
• Less parallelizable: The sequential vertex-growing nature makes it harder to parallelize than Kruskal's edge-sorting approach.
• Starting vertex choice: While the MST is the same regardless of starting vertex, the tree structure may differ.

8. Comparison with Other MST Algorithms

9. Applications

• Network infrastructure: Designing minimum-cost telephone, electrical, or water distribution networks connecting all nodes.
• Maze generation: Randomized Prim's algorithm can generate random mazes by treating grid cells as vertices and walls as weighted edges.
• Approximate Steiner tree: Prim's MST provides a 2-approximation for the Steiner tree problem in metric spaces.
• Taxonomy construction: Building minimum evolution phylogenetic trees from distance matrices in biology.
• VLSI circuit design: Minimizing wire length in very-large-scale integrated circuit routing.
• Broadcast networks: Computing efficient broadcast trees for distributing information in networks.

10. References

1. Prim, R. C. (1957). "Shortest Connection Networks and Some Generalizations." Bell System Technical Journal, 36(6), 1389-1401.
2. Jarnik, V. (1930). "O jistem problemu minimalnim." Prace Moravske Prirodovedecke Spolecnosti, 6, 57-63.
3. Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press. Chapter 23.
4. Sedgewick, R. and Wayne, K. (2011). Algorithms (4th ed.). Addison-Wesley. Section 4.3.
5. Fredman, M. L. and Tarjan, R. E. (1987). "Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms." Journal of the ACM, 34(3), 596-615.