Prim’s Algorithm: Minimum Spanning Tree Using Priority Queue Explained with Examples

Prim’s algorithm is a popular greedy algorithm used to find the Minimum Spanning Tree (MST) of a weighted, connected, undirected graph. The MST connects all vertices in such a way that the total weight of the edges included is minimal, without any cycles.

This article provides a detailed and SEO-friendly explanation of Prim’s algorithm with a focus on implementing it efficiently using a Priority Queue. It includes step-by-step examples, illustrative Mermaid diagrams for better understanding, and a comprehensive walkthrough to help grasp the concept deeply.

What is Prim’s Algorithm?

Prim’s algorithm starts with an arbitrary node and grows the MST by repeatedly adding the lowest-weight edge that connects a vertex inside the MST to a vertex outside it. The process continues until all vertices are included in the MST.

The key idea: At each step, add the edge with the smallest weight that expands the growing MST without forming a cycle.

Why Use a Priority Queue?

Using a Priority Queue (often implemented as a min-heap) improves the efficiency of Prim’s algorithm by quickly selecting the edge with the smallest weight at every step. This reduces the complexity compared to scanning all edges repeatedly.

When implemented with an adjacency list and a priority queue, Prim’s runs in O(E log V) time, where E is the number of edges and V is the number of vertices.

Algorithm Steps Using Priority Queue

1. Initialize a min-priority queue to store edges available to be added, starting with edges from an arbitrary node (commonly node 0).
2. Keep a boolean array to track which vertices have been added to the MST.
3. Pop the edge with the smallest weight from the priority queue.
4. If the edge connects to a vertex not yet in MST, add that vertex and the edge to the MST.
5. Add all edges from the new vertex that connect to vertices outside the MST to the priority queue.
6. Repeat steps 3-5 until all vertices are included in the MST.

Example: Prim’s Algorithm in Action

Consider this weighted undirected graph with vertices numbered 0 to 4:

Step-by-step walkthrough:

• Start: Choose vertex 0. Add edges (0-1:2), (0-3:3) to the priority queue.
• Pop minimum edge: (0-1:2). Vertex 1 is not yet in MST, include it.
• Add edges from vertex 1 → (1-2:3), (1-3:4) to the priority queue.
• Pop minimum edge: (0-3:3). Vertex 3 is not yet in MST, include it.
• Add edges from vertex 3 → (3-4:7) to the priority queue.
• Pop minimum edge: (1-2:3). Vertex 2 not in MST, include it.
• Add edges from vertex 2 → (2-4:5) to the priority queue.
• Pop minimum edge: (2-4:5). Vertex 4 not in MST, include it.
• All vertices included — MST complete with edges (0-1), (0-3), (1-2), (2-4).

Visualizing the MST formed:

Prim’s Algorithm: Pseudocode Using Priority Queue

function primMST(graph):
    Initialize mstSet[] as false for all vertices
    Initialize priority queue pq
    Initialize key[] with infinity values
    key[0] = 0
    pq.push((0, 0)) // (weight, vertex)
    
    while pq is not empty:
        weight, u = pq.pop()
        
        if mstSet[u] is true:
            continue
        
        mstSet[u] = true
        
        for each (v, wt) in adjacency list of u:
            if mstSet[v] == false and wt < key[v]:
                key[v] = wt
                pq.push((wt, v))
                
    // key[] now contains edges of MST

Code Example in Python

import heapq

def prim_mst(graph, start=0):
    mst_set = [False] * len(graph)
    min_heap = []
    heapq.heappush(min_heap, (0, start))  # (weight, vertex)
    total_weight = 0
    edges_in_mst = []
    
    while min_heap:
        weight, u = heapq.heappop(min_heap)
        if mst_set[u]:
            continue
        
        mst_set[u] = True
        total_weight += weight
        
        if weight != 0:
            edges_in_mst.append((u, weight))
        
        for v, w in graph[u]:
            if not mst_set[v]:
                heapq.heappush(min_heap, (w, v))
    
    return edges_in_mst, total_weight

# Example graph represented as adjacency list
# Each list item is (vertex, weight)
graph = {
    0: [(1, 2), (3, 3)],
    1: [(0, 2), (2, 3), (3, 4)],
    2: [(1, 3), (4, 5)],
    3: [(0, 3), (1, 4), (4, 7)],
    4: [(2, 5), (3, 7)]
}

edges, total = prim_mst(graph)
print("Edges in MST and weights:", edges)
print("Total weight of MST:", total)

Explanation of Code

• We use a min_heap to always pick the edge with the smallest weight.
• mst_set keeps track of included vertices to prevent cycles.
• Edges and weights are collected in edges_in_mst for output demonstration.
• Total weight of the MST is summed during traversal.

When to Use Prim’s Algorithm?

Prim’s algorithm is especially efficient for dense graphs where the number of edges is close to \( V^2 \), due to the performance advantage provided by the priority queue. For sparse graphs, algorithms like Kruskal may be competitive, but Prim’s remains simple when represented with adjacency lists and heaps.

Summary

Prim’s algorithm is a fundamental graph algorithm to compute the Minimum Spanning Tree efficiently through a greedy approach. Using a priority queue improves edge selection to achieve optimal time complexity. This article showed detailed explanations, visual diagrams, pseudocode, and a Python implementation for practical understanding.

For further exploration, try modifying the code for directed graphs or adapting the algorithm to return the explicit edge pairs forming the MST.