DSA 450 Notes

Problem Statement

Given a connected, undirected, weighted graph with V vertices and E edges, find the Minimum Spanning Tree (MST) using Prim's Algorithm.

Example:

Input: V = 5, Edges = [[0,1,2],[0,3,6],[1,2,3],[1,3,8],[1,4,5],[2,4,7],[3,4,9]]
Output: MST weight = 16

Noob-Friendly Explanation

Prim's algorithm is another way to find the cheapest way to connect all towns with roads (Minimum Spanning Tree). Unlike Kruskal's (which sorts all roads), Prim's works like growing a tree:

Start from any town.
Look at all roads connecting your current tree to towns NOT in the tree.
Pick the cheapest road and add that town to your tree.
Repeat until all towns are in the tree.

It's like building a network outward from a starting point, always choosing the cheapest next connection.

Approach 1: Brute Force (Simple Array)

Intuition

Maintain a key[] array where key[v] is the minimum weight edge to connect vertex v to the MST. In each step, find the vertex with the minimum key that isn't in the MST yet.

Algorithm

Initialize all keys to infinity, start vertex key to 0.
Repeat V times: a. Pick the vertex with minimum key not in MST. b. Add it to MST. c. Update keys of its neighbors.

java

import java.util.*;

public class PrimBruteForce {
    public static int primMST(int V, int[][] edges) {
        List<List<int[]>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) {
            adj.get(e[0]).add(new int[]{e[1], e[2]});
            adj.get(e[1]).add(new int[]{e[0], e[2]});
        }

        int[] key = new int[V];       // minimum weight to connect to MST
        boolean[] inMST = new boolean[V];
        int[] parent = new int[V];

        Arrays.fill(key, Integer.MAX_VALUE);
        Arrays.fill(parent, -1);
        key[0] = 0; // start from vertex 0

        int totalWeight = 0;

        for (int count = 0; count < V; count++) {
            // Find vertex with minimum key not in MST — O(V)
            int u = -1;
            for (int v = 0; v < V; v++) {
                if (!inMST[v] && (u == -1 || key[v] < key[u])) {
                    u = v;
                }
            }

            inMST[u] = true;
            totalWeight += key[u];

            // Update keys of neighbors
            for (int[] neighbor : adj.get(u)) {
                int v = neighbor[0], weight = neighbor[1];
                if (!inMST[v] && weight < key[v]) {
                    key[v] = weight;
                    parent[v] = u;
                }
            }
        }

        // Print MST edges
        for (int i = 1; i < V; i++) {
            System.out.println(parent[i] + " - " + i + " : " + key[i]);
        }

        return totalWeight;
    }

    public static void main(String[] args) {
        int V = 5;
        int[][] edges = {{0,1,2},{0,3,6},{1,2,3},{1,3,8},{1,4,5},{2,4,7},{3,4,9}};
        System.out.println("Total MST weight: " + primMST(V, edges)); // 16
    }
}

Complexity Analysis

Time Complexity: O(V^2) — for each vertex, we scan all V vertices to find the minimum key.
Space Complexity: O(V) — for key, inMST, and parent arrays.

Approach 2: Optimal (Priority Queue / Min-Heap)

Intuition

Use a min-heap to efficiently find the next vertex with the minimum connection weight, instead of scanning all vertices.

Algorithm

Start from vertex 0 with weight 0.
Add (0, 0) to the priority queue.
While queue is not empty, extract the minimum weight vertex.
If already in MST, skip. Otherwise, add to MST.
Update all neighbors and add to the priority queue if a cheaper connection is found.

java

import java.util.*;

public class PrimOptimal {
    public static int primMST(int V, int[][] edges) {
        List<List<int[]>> adj = new ArrayList<>();
        for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) {
            adj.get(e[0]).add(new int[]{e[1], e[2]});
            adj.get(e[1]).add(new int[]{e[0], e[2]});
        }

        boolean[] inMST = new boolean[V];
        // Min-heap: {weight, vertex}
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        pq.add(new int[]{0, 0}); // start from vertex 0

        int totalWeight = 0;
        int edgesAdded = 0;

        while (!pq.isEmpty() && edgesAdded < V) {
            int[] curr = pq.poll();
            int weight = curr[0], u = curr[1];

            if (inMST[u]) continue;

            inMST[u] = true;
            totalWeight += weight;
            edgesAdded++;

            for (int[] neighbor : adj.get(u)) {
                int v = neighbor[0], w = neighbor[1];
                if (!inMST[v]) {
                    pq.add(new int[]{w, v});
                }
            }
        }

        return totalWeight;
    }

    public static void main(String[] args) {
        int V = 5;
        int[][] edges = {{0,1,2},{0,3,6},{1,2,3},{1,3,8},{1,4,5},{2,4,7},{3,4,9}};
        System.out.println("Total MST weight: " + primMST(V, edges)); // 16
    }
}

Complexity Analysis

Time Complexity: O(E log V) — each edge is processed once, and heap operations take O(log V).
Space Complexity: O(V + E) — for the adjacency list and priority queue.

Implement Prims Algorithm

Problem Statement

Noob-Friendly Explanation

Approach 1: Brute Force (Simple Array)

Intuition

Algorithm

Complexity Analysis

Approach 2: Optimal (Priority Queue / Min-Heap)

Intuition

Algorithm

Complexity Analysis