Prim's Algorithm for MST with Priority Queues

1. The Core Idea of Prim's Algorithm

Prim's algorithm is also a greedy algorithm, but its greedy choice is different from Kruskal's. It works by partitioning the graph's vertices into two sets:

1. Vertices already included in the MST.
2. Vertices not yet included.

The algorithm starts with an arbitrary vertex in the first set. Then, at each step, it makes the following greedy choice: find the minimum-weight edge that connects a vertex in the MST set to a vertex outside of it, and add that edge (and the new vertex) to the MST.

This process is repeated exactly V-1 times, where V is the number of vertices, until all vertices are connected.

To build your intuition for this process, let's look at a step-by-step example.

2. The Role of the Priority Queue

A naive implementation of Prim's would involve searching through all possible edges at each of the V-1 steps to find the minimum-weight one that crosses the boundary of our growing tree. This would be slow, with a time complexity of around $O(V\cdot E)$.

We can do much better. The problem of "repeatedly finding the minimum item from a collection" is a perfect use case for a min-priority queue.

The efficient version of Prim's algorithm is remarkably similar in structure to Dijkstra's algorithm for shortest paths. It uses a priority queue to keep track of the "fringe"—the set of all edges that connect vertices inside our MST to vertices outside it.

Here's the logic:

1. Initialize a min-priority queue. It will store pairs of {weight, vertex}.
2. Create a visited array to track vertices already in the MST.
3. Choose a starting vertex (e.g., vertex 0), and add {0, start_vertex} to the priority queue. The initial weight is 0 because there's no cost to start there.
4. Loop while the priority queue is not empty and the MST has fewer than V-1 edges:
   a. Extract the pair with the smallest weight from the priority queue. Let this be {weight, vertex u}.
   b. If u has already been visited, continue to the next iteration.
   c. Mark u as visited and add the edge to the MST (the total weight of the MST increases by weight).
   d. For each neighbor v of u: if v has not been visited, add the edge connecting u and v (i.e., {edge_weight, v}) to the priority queue.

This approach is efficient because the priority queue handles finding the minimum-weight edge in logarithmic time, rather than us needing to scan all edges manually.

3. Java Implementation

Now let's translate this logic into Java code. We'll use an adjacency list to represent the graph and Java's PriorityQueue to implement the min-heap.

For the priority queue to work correctly with our custom data, we can either store an object that implements Comparable or provide a Comparator during the PriorityQueue's initialization. Storing a simple int[] of {vertex, weight} and using a lambda for the comparator is a common and clean approach in competitive programming.

Below is a complete, runnable Java program that implements Prim's algorithm. It finds the total weight of the MST and prints the edges that form it.

import java.util.*;

public class PrimsAlgorithm {

    // A class to represent a pair of (vertex, weight) for the adjacency list
    static class Pair {
        int vertex;
        int weight;

        Pair(int v, int w) {
            this.vertex = v;
            this.weight = w;
        }
    }

    // A class to represent an edge for the priority queue and MST result
    // Stores {source, destination, weight}
    static class Edge {
        int source;
        int destination;
        int weight;

        Edge(int u, int v, int w) {
            this.source = u;
            this.destination = v;
            this.weight = w;
        }
    }

    public static void primMST(int V, ArrayList<ArrayList<Pair>> adj) {
        // Priority Queue to store edges, ordered by weight
        // We store an array {weight, vertex, parent}
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));

        boolean[] visited = new boolean[V];
        List<Edge> mstEdges = new ArrayList<>();
        int mstWeight = 0;

        // Start with vertex 0
        // {weight, vertex, parent}
        pq.add(new int[]{0, 0, -1}); // -1 indicates no parent

        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int weight = current[0];
            int u = current[1];
            int parent = current[2];

            // If we have already included this vertex in the MST, skip it.
            if (visited[u]) {
                continue;
            }

            // Mark vertex as visited and add weight to the total
            visited[u] = true;
            mstWeight += weight;
            if (parent != -1) { // Add edge to our result list, skipping the initial pseudo-edge
                mstEdges.add(new Edge(parent, u, weight));
            }

            // Explore neighbors
            for (Pair neighborPair : adj.get(u)) {
                int v = neighborPair.vertex;
                int edgeWeight = neighborPair.weight;
                if (!visited[v]) {
                    pq.add(new int[]{edgeWeight, v, u});
                }
            }
        }

        System.out.println("Minimum Spanning Tree Weight: " + mstWeight);
        System.out.println("Edges in the MST:");
        for (Edge edge : mstEdges) {
            System.out.println(edge.source + " - " + edge.destination + " \tWeight: " + edge.weight);
        }
    }

    public static void main(String[] args) {
        int V = 5;
        ArrayList<ArrayList<Pair>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) {
            adj.add(new ArrayList<>());
        }

        // Example from netjstech.com resource
        adj.get(0).add(new Pair(1, 2));
        adj.get(1).add(new Pair(0, 2));

        adj.get(0).add(new Pair(2, 2));
        adj.get(2).add(new Pair(0, 2));

        adj.get(1).add(new Pair(2, 4));
        adj.get(2).add(new Pair(1, 4));

        adj.get(1).add(new Pair(4, 5));
        adj.get(4).add(new Pair(1, 5));

        adj.get(2).add(new Pair(3, 7));
        adj.get(3).add(new Pair(2, 7));

        adj.get(2).add(new Pair(4, 1));
        adj.get(4).add(new Pair(2, 1));
        
        adj.get(3).add(new Pair(4, 6));
        adj.get(4).add(new Pair(3, 6));

        primMST(V, adj);
    }
}

4. Complexity Analysis

A solid understanding of complexity is essential for interviews.

• Time Complexity:

  • The main while loop runs until all vertices are visited. In each iteration where we add a vertex to the MST, we iterate through its neighbors. Over the entire execution, each edge (u, v) will be processed once from u's side and once from v's side.
  • This means we perform at most $O(E)$ add operations and $O(V)$ poll operations on the priority queue.
  • Both add and poll take $O(\log N)$ time, where $N$ is the number of elements in the queue. In the worst case, the queue can hold $O(E)$ edges.
  • Therefore, the time complexity is $O(E\log E)$. Since $E$ can be at most $V^2$, $\log E$ is asymptotically equivalent to $O(\log V)$, so the complexity is often stated as $O(E\log V)$.

• Space Complexity:

  • Adjacency list: $O(V+E)$.
  • visited array: $O(V)$.
  • PriorityQueue: In the worst case, can store all edges, so $O(E)$.
  • The total space complexity is dominated by the adjacency list and priority queue, making it $O(V+E)$.

For a final confirmation of this analysis, you can review the complexity section of the netjstech.com resource. Look for the final analysis that uses an adjacency list and priority queue.

Conclusion

You have now learned and implemented Prim's algorithm, the second fundamental approach to finding a Minimum Spanning Tree.

Key Takeaways:

• Prim's algorithm builds an MST by starting from a single vertex and greedily growing the tree, always adding the cheapest edge that connects a vertex in the tree to one outside of it.
• An efficient implementation relies on a min-priority queue to quickly find this minimum-weight edge.
• The time complexity using an adjacency list and a binary heap (like Java's PriorityQueue) is $O(E\log V)$.
• The space complexity is $O(V+E)$.

Prim's vs. Kruskal's:

• Prim's is generally faster for dense graphs (where $E$ is close to $V^2$).
• Kruskal's is often faster for sparse graphs (where $E$ is close to $V$) because its complexity depends more on sorting edges ($E\log E$) than on vertex operations.

Preview of the Next Lesson:
The structure of Prim's algorithm—using a priority queue to explore a graph from a starting point—is a powerful pattern. In our next lesson, we will see it again when we implement Dijkstra's algorithm. While Prim's finds an MST by minimizing edge weights to connect all vertices, Dijkstra's finds the shortest path from a single source to all other vertices by minimizing the total path distance from the source. The code will look surprisingly similar, but the greedy choice will be different.