Prim’s Algorithm – Minimum Spanning Tree Algorithm (MST)

Prim’s Algorithm is one of the classic approaches for finding a Minimum Spanning Tree (MST) in a weighted undirected graph. It begins from any chosen start vertex, then repeatedly selects the cheapest edge (in terms of weight) connecting the current MST to a vertex not yet in the MST. It often uses a priority queue (min-heap) and can achieve O(E log V) complexity with an adjacency list representation.

---

1. Key Idea

1. Choose any start vertex and include it in the MST set.
2. Among the edges connecting the MST set to non-MST vertices, pick the lowest-weight edge.
3. Add that edge (and the corresponding vertex) to the MST set.
4. Repeat until all vertices are included (i.e., V – 1 edges are chosen for V vertices).

---

2. Time Complexity

• With an adjacency list and a priority queue (heap), Prim’s algorithm runs in about O(E log V).
• With an adjacency matrix, finding the minimum edge can take O(V) each time, leading to O(V^2) complexity for dense graphs.

---

3. Prim’s Algorithm Code Example (Java)

Below is an example using an adjacency list and a priority queue to implement Prim’s algorithm.

3.1 Source Code

import java.util.*;

class Edge {
    int to;
    int weight;

    public Edge(int to, int weight) {
        this.to = to;
        this.weight = weight;
    }
}

public class PrimExample {
    private List<List<Edge>> graph; // Adjacency list
    private int vertexCount;

    public PrimExample(int n) {
        vertexCount = n;
        graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
    }

    public void addEdge(int u, int v, int weight) {
        // Undirected edge
        graph.get(u).add(new Edge(v, weight));
        graph.get(v).add(new Edge(u, weight));
    }

    public int primMST(int start) {
        boolean[] visited = new boolean[vertexCount];
        int mstCost = 0;
        int edgeCount = 0;

        // Priority queue storing edges as (weight, destination)
        PriorityQueue<Edge> pq = new PriorityQueue<>(Comparator.comparingInt(e -> e.weight));

        // Mark the start vertex as visited and add its edges
        visited[start] = true;
        for (Edge e : graph.get(start)) {
            pq.offer(e);
        }

        // Continue until we've chosen V-1 edges or the queue is empty
        while (!pq.isEmpty() && edgeCount < vertexCount - 1) {
            Edge currentEdge = pq.poll();
            int nextVertex = currentEdge.to;
            int w = currentEdge.weight;

            if (visited[nextVertex]) {
                // Already in MST
                continue;
            }

            // Add the new vertex to MST
            visited[nextVertex] = true;
            mstCost += w;
            edgeCount++;

            // Add adjacent edges from this newly added vertex
            for (Edge adj : graph.get(nextVertex)) {
                if (!visited[adj.to]) {
                    pq.offer(adj);
                }
            }
        }

        return mstCost;
    }
}

3.2 Test Code

public class PrimTest {
    public static void main(String[] args) {
        int n = 6; // Number of vertices
        PrimExample primGraph = new PrimExample(n);

        // Add undirected edges: (u, v, weight)
        primGraph.addEdge(0, 1, 4);
        primGraph.addEdge(0, 2, 2);
        primGraph.addEdge(1, 2, 5);
        primGraph.addEdge(1, 3, 10);
        primGraph.addEdge(2, 4, 3);
        primGraph.addEdge(2, 5, 7);
        primGraph.addEdge(3, 4, 6);
        primGraph.addEdge(4, 5, 1);

        // Start Prim's from vertex 0
        int mstCost = primGraph.primMST(0);
        System.out.println("Prim MST Cost: " + mstCost);
        // Example result: 16, depending on the structure
    }
}

---

4. Prim’s Algorithm Code Example (Python)

Below is a similar approach using a list of adjacency information and a priority queue (heapq in Python).

4.1 Source Code

import heapq

class PrimExample:
    def __init__(self, n):
        self.n = n
        # Adjacency list: graph[u] = [(weight, v), ...]
        self.graph = [[] for _ in range(n)]

    def add_edge(self, u, v, weight):
        # Undirected edge
        self.graph[u].append((weight, v))
        self.graph[v].append((weight, u))

    def prim_mst(self, start):
        visited = [False] * self.n
        mst_cost = 0
        edge_count = 0

        # Priority queue with (weight, vertex)
        pq = []
        visited[start] = True

        # Add edges from start vertex
        for w, nxt in self.graph[start]:
            heapq.heappush(pq, (w, nxt))

        # Repeat until we have n-1 edges or run out of edges
        while pq and edge_count < self.n - 1:
            w, nxt = heapq.heappop(pq)
            if visited[nxt]:
                continue

            visited[nxt] = True
            mst_cost += w
            edge_count += 1

            # Add new edges from the newly visited vertex
            for adj_w, adj_v in self.graph[nxt]:
                if not visited[adj_v]:
                    heapq.heappush(pq, (adj_w, adj_v))

        return mst_cost

4.2 Test Code

def test_prim():
    n = 6
    prim_graph = PrimExample(n)

    # (u, v, weight)
    prim_graph.add_edge(0, 1, 4)
    prim_graph.add_edge(0, 2, 2)
    prim_graph.add_edge(1, 2, 5)
    prim_graph.add_edge(1, 3, 10)
    prim_graph.add_edge(2, 4, 3)
    prim_graph.add_edge(2, 5, 7)
    prim_graph.add_edge(3, 4, 6)
    prim_graph.add_edge(4, 5, 1)

    mst_cost = prim_graph.prim_mst(0)
    print("Prim MST Cost:", mst_cost)
    # For instance, might print 16

if __name__ == "__main__":
    test_prim()

---

5. Use Cases

1. Network Infrastructure
   • Connecting communication or power grids with minimal total cost.
2. Road/Bridge Construction
   • Minimizing the cost of linking cities with roads.
3. MST Problems (with Kruskal’s)
   • Often used in scenarios where the graph is dense, making Prim’s algorithm more efficient than Kruskal’s in some cases.

---

6. Comparison with Kruskal’s Algorithm

Aspect	Prim’s Algorithm	Kruskal’s Algorithm
Data Structure	Priority queue (min-heap) + adjacency list/ matrix	Sort edges + Union-Find
Approach	Vertex-centric: expand MST via min-edge from MST set	Edge-centric: pick edges in ascending weight
When to Use	Good for dense graphs (many edges)	Good for sparse graphs (fewer edges)

---

7. Conclusion

• Prim’s Algorithm expands the MST one vertex at a time, picking the lowest-weight edge connecting the MST set to a new vertex.
• With an adjacency list and a priority queue, it typically runs in O(E log V).
• Along with Kruskal’s, it is one of the two main MST algorithms; the choice depends on graph density and implementation preferences.