Prim's Minimum Spanning Tree (MST)

A Spanning Tree of a connected and undirected graph is a subgraph that is a tree (contains no cycles) and connects all vertices of the graph. A single graph can have many different spanning trees.

A Minimum Spanning Tree (MST) is a spanning tree whose sum of edge weights is minimized.

For a graph with $V$ vertices, its MST contains exactly $V - 1$ edges.

Prim's Algorithm (Greedy Approach)

Prim's algorithm starts with an empty spanning tree. It maintains two sets of vertices:

MST Set: Vertices already included in the MST.
Non-MST Set: Vertices not yet included.

At each step, the algorithm finds the cheapest edge that connects a vertex in the MST set to a vertex in the Non-MST set, and grows the tree by adding that vertex and edge.

The Algorithm Steps

Create a boolean array mstSet of size $V$ to keep track of vertices in the MST. Initialize all as false.
Create a key array of size $V$ to store the minimum weight edge connecting each vertex to the growing MST. Initialize all keys as Infinity, except key[0] = 0 (so vertex 0 is picked first).
Create a parent array of size $V$ to store the parent of each node in the MST (this helps reconstruct the tree).
Repeat $V$ times:
- Pick a vertex $u$ that is not in mstSet and has the minimum key value.
- Include $u$ in the MST (mstSet[u] = true).
- Update the key value and parent of all adjacent vertices of $u$: for each neighbor $v$, if the edge weight $u-v$ is less than key[v] and $v$ is not yet in mstSet, update key[v] = weight and parent[v] = u.

Visual Example Graph

Let's find the MST for this weighted undirected graph:

Trace Summary

Start at 0 (key = 0).
Neighbors 1 (key $\rightarrow$ 4) and 7 (key $\rightarrow$ 8) updated.
Pick 1 (minimum key: 4). Neighbors updated.
Pick 7 (minimum key: 8). Neighbor 6 updated (key $\rightarrow$ 1).
Pick 6 (minimum key: 1). Neighbor 5 updated (key $\rightarrow$ 2).
Pick 5 (minimum key: 2). Neighbor 2 updated (key $\rightarrow$ 4).
Pick 2 (minimum key: 4). Neighbor 8 (key $\rightarrow$ 2) and 3 (key $\rightarrow$ 7) updated.
Pick 8 (minimum key: 2).
Pick 3 (minimum key: 7). Neighbor 4 updated (key $\rightarrow$ 9).
Pick 4 (minimum key: 9).
Total MST Weight: $4 + 8 + 1 + 2 + 4 + 2 + 7 + 9 = 37$.

JavaScript Code Implementation

class WeightedGraph {
    constructor(verticesCount) {
        this.vertices = verticesCount;
        this.adj = Array.from({ length: verticesCount }, () => []);
    }
 
    addEdge(u, v, weight) {
        this.adj[u].push({ node: v, weight: weight });
        this.adj[v].push({ node: u, weight: weight });
    }
 
    // Prim's algorithm implementation
    primMST() {
        const parent = new Array(this.vertices).fill(null);
        const key = new Array(this.vertices).fill(Infinity);
        const mstSet = new Array(this.vertices).fill(false);
 
        // Always start with the first vertex
        key[0] = 0;
        parent[0] = -1; // First node is always root of MST
 
        for (let count = 0; count < this.vertices - 1; count++) {
            // Pick the minimum key vertex from the set of vertices not yet included in MST
            const u = this._minKey(key, mstSet);
 
            // Add the picked vertex to the MST Set
            mstSet[u] = true;
 
            // Update key value and parent index of the adjacent vertices of the picked vertex.
            for (let edge of this.adj[u]) {
                const v = edge.node;
                const weight = edge.weight;
 
                // Update key[v] only if v is not in mstSet and weight of u-v is less than key[v]
                if (!mstSet[v] && weight < key[v]) {
                    parent[v] = u;
                    key[v] = weight;
                }
            }
        }
 
        this._printMST(parent, key);
    }
 
    // Helper to find the vertex with the minimum key value
    _minKey(key, mstSet) {
        let min = Infinity;
        let minIndex = -1;
 
        for (let v = 0; v < this.vertices; v++) {
            if (!mstSet[v] && key[v] < min) {
                min = key[v];
                minIndex = v;
            }
        }
        return minIndex;
    }
 
    // Helper to print the constructed MST
    _printMST(parent, key) {
        console.log("Edge \tWeight");
        let totalWeight = 0;
        for (let i = 1; i < this.vertices; i++) {
            console.log(`${parent[i]} - ${i} \t${key[i]}`);
            totalWeight += key[i];
        }
        console.log("Total MST Weight:", totalWeight);
    }
}
 
// Driver code matching the example graph
const g = new WeightedGraph(9);
g.addEdge(0, 1, 4);
g.addEdge(0, 7, 8);
g.addEdge(1, 2, 8);
g.addEdge(1, 7, 11);
g.addEdge(2, 3, 7);
g.addEdge(2, 8, 2);
g.addEdge(2, 5, 4);
g.addEdge(3, 4, 9);
g.addEdge(3, 5, 14);
g.addEdge(4, 5, 10);
g.addEdge(5, 6, 2);
g.addEdge(6, 7, 1);
g.addEdge(6, 8, 6);
g.addEdge(7, 8, 7);
 
g.primMST();
/*
Output:
Edge    Weight
0 - 1   4
5 - 2   4
2 - 3   7
3 - 4   9
6 - 5   2
7 - 6   1
0 - 7   8
2 - 8   2
Total MST Weight: 37
*/

Complexity Analysis

Time Complexity:
- $O(V^2)$ with adjacency matrix or simple array lookup (as implemented above).
- $O(E \log V)$ if we implement it using an Adjacency List and a Binary Heap / Priority Queue (min-heap) to select the minimum key node.
Space Complexity: $O(V)$
- To store key, parent, and mstSet arrays.

Detect Cycle using Kahn's Algorithm Dijkstra's Shortest Path