Minimum Spanning Tree Prim's Algorithm in DSA Java

Mental Model

Start from any node and keep adding the cheapest edge that connects a new node to the growing tree until all nodes are included.

Analogy: Imagine building a network of roads connecting cities. You start from one city and always pick the shortest road that connects a new city to your existing network, avoiding loops.

Graph:
  (0)
 /   \
(1)---(2)
Edges with weights:
0-1: 4, 0-2: 3, 1-2: 5

Start at node 0:
[0] -> (2) -> (1)
Prim's tree grows by adding cheapest edges connecting new nodes.

Dry Run Walkthrough

Input: Graph with nodes 0,1,2 and edges: 0-1(4), 0-2(3), 1-2(5). Start at node 0.

Goal: Build a minimum spanning tree connecting all nodes with minimum total edge weight.

Step 1: Start at node 0, add it to MST set

MST nodes: [0]
Edges considered: 0-1(4), 0-2(3)

Why: We need a starting point to build the tree.

Step 2: Pick edge with smallest weight connecting MST to new node: 0-2(3)

MST nodes: 0 -> [2]
Edges considered: 0-1(4), 2-1(5)

Why: Choose cheapest edge to expand MST without cycles.

Step 3: Pick next smallest edge connecting MST to new node: 0-1(4)

MST nodes: 0 -> 2 -> [1]
All nodes included

Why: Add remaining node with minimum cost edge.

Result:

MST edges: 0-2(3) -> 0-1(4)
Total weight: 7

Annotated Code

DSA Java

import java.util.*;

class Edge implements Comparable<Edge> {
    int target, weight;
    Edge(int target, int weight) {
        this.target = target;
        this.weight = weight;
    }
    public int compareTo(Edge other) {
        return this.weight - other.weight;
    }
}

public class PrimsMST {
    public static int primMST(List<List<Edge>> graph, int start) {
        int n = graph.size();
        boolean[] inMST = new boolean[n];
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        int totalWeight = 0;

        pq.add(new Edge(start, 0));

        while (!pq.isEmpty()) {
            Edge current = pq.poll();
            int node = current.target;
            if (inMST[node]) continue; // skip if already in MST
            inMST[node] = true;
            totalWeight += current.weight;

            for (Edge edge : graph.get(node)) {
                if (!inMST[edge.target]) {
                    pq.add(new Edge(edge.target, edge.weight));
                }
            }
        }
        return totalWeight;
    }

    public static void main(String[] args) {
        int n = 3;
        List<List<Edge>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());

        // Add edges
        graph.get(0).add(new Edge(1, 4));
        graph.get(1).add(new Edge(0, 4));

        graph.get(0).add(new Edge(2, 3));
        graph.get(2).add(new Edge(0, 3));

        graph.get(1).add(new Edge(2, 5));
        graph.get(2).add(new Edge(1, 5));

        int totalWeight = primMST(graph, 0);
        System.out.println("Total weight of MST: " + totalWeight);
    }
}

pq.add(new Edge(start, 0));

Initialize priority queue with start node at zero cost

Edge current = pq.poll();

Extract edge with smallest weight to expand MST

if (inMST[node]) continue;

Skip nodes already included to avoid cycles

inMST[node] = true;

Mark node as included in MST

totalWeight += current.weight;

Add edge weight to total MST cost

for (Edge edge : graph.get(node)) { if (!inMST[edge.target]) pq.add(new Edge(edge.target, edge.weight)); }

Add all edges from current node to priority queue if target not in MST

Output

Total weight of MST: 7

Complexity Analysis

Time: O(E log V) because each edge is processed and priority queue operations take log V time

Space: O(V + E) to store the graph and priority queue

vs Alternative: Compared to Kruskal's algorithm which sorts edges first, Prim's can be more efficient on dense graphs using adjacency lists and priority queue

Edge Cases

Graph with single node and no edges

MST weight is zero since no edges to add

DSA Java

pq.add(new Edge(start, 0));

Disconnected graph

Only nodes reachable from start are included; MST covers connected component

DSA Java

if (inMST[node]) continue;

Graph with multiple edges of same weight

Algorithm picks any minimal edge; MST still valid

DSA Java

pq.add(new Edge(edge.target, edge.weight));

When to Use This Pattern

When you need to connect all points with minimum total cost and avoid cycles, use Prim's MST algorithm because it grows the tree step-by-step by choosing the cheapest connecting edge.

Common Mistakes

Mistake: Not checking if a node is already in MST before adding edges
Fix: Add a check to skip nodes already included to prevent cycles and repeated work

Mistake: Starting from a node not in the graph or empty graph
Fix: Ensure start node is valid and graph is non-empty before running algorithm

Summary

Builds a minimum spanning tree by adding the cheapest edge connecting new nodes to the tree.

Use when you want to connect all nodes with minimum total edge cost without cycles.

The key insight is to always pick the smallest edge that expands the tree to a new node.

Practice

1. What is the main goal of Prim's Algorithm in graph theory?

easy

A. To sort vertices based on their degree

B. To find the shortest path between two vertices

C. To detect cycles in a graph

D. To find the minimum spanning tree connecting all vertices with minimum total edge weight

Solution

1. Step 1: Understand Prim's Algorithm purpose

   Prim's Algorithm builds a tree connecting all vertices with the smallest sum of edge weights.

2. Step 2: Compare with other graph tasks

   It is not for shortest path, cycle detection, or sorting vertices.

3. Final Answer:

   To find the minimum spanning tree connecting all vertices with minimum total edge weight -> Option D

4. Quick Check:

   Prim's Algorithm = Minimum Spanning Tree [OK]

Hint: Prim's always finds minimum spanning tree, not shortest path [OK]

Common Mistakes:

• Confusing Prim's with Dijkstra's algorithm
• Thinking it finds shortest paths
• Assuming it detects cycles

2. Which of the following Java code snippets correctly initializes the key array for Prim's Algorithm for a graph with 5 vertices?

easy

A. int key[] = new int[5]; for(int i=0; i<5; i++) key[i] = 0;

B. int[] key = new int[5]; Arrays.fill(key, 0); key[0] = Integer.MAX_VALUE;

C. int[] key = new int[5]; Arrays.fill(key, Integer.MAX_VALUE); key[0] = 0;

D. int[] key = new int[5]; key[0] = Integer.MIN_VALUE; Arrays.fill(key, Integer.MAX_VALUE);

Solution

1. Step 1: Understand key array initialization

   Key array stores minimum edge weights to vertices; initialize with max values except start vertex 0 with 0.

2. Step 2: Check each option

   int[] key = new int[5]; Arrays.fill(key, Integer.MAX_VALUE); key[0] = 0; correctly sets all to Integer.MAX_VALUE and start vertex key[0] to 0.

3. Final Answer:

   int[] key = new int[5]; Arrays.fill(key, Integer.MAX_VALUE); key[0] = 0; -> Option C

4. Quick Check:

   Initialize keys with max except start = 0 [OK]

Hint: Start vertex key = 0, others = max value [OK]

Common Mistakes:

• Setting all keys to 0
• Setting start vertex key to max value
• Incorrect order of fill and assignment

3. Given the following adjacency matrix for a graph with 4 vertices, what is the total weight of the minimum spanning tree found by Prim's Algorithm starting from vertex 0?

int[][] graph = {
  {0, 2, 0, 6},
  {2, 0, 3, 8},
  {0, 3, 0, 0},
  {6, 8, 0, 0}
};

medium

A. 14

B. 11

C. 9

D. 10

Solution

1. Step 1: Start from vertex 0 and pick minimum edges

   Edges chosen: 0-1 (2), 1-2 (3), 0-3 (6)

2. Step 2: Sum the weights of chosen edges

   Total weight = 2 + 3 + 6 = 11

3. Final Answer:

   11 -> Option B

4. Quick Check:

   Sum edges 2+3+6 = 11 [OK]

Hint: Add weights of edges chosen by Prim's stepwise [OK]

Common Mistakes:

• Choosing wrong edges ignoring minimum weight
• Adding edges that form cycles
• Starting from wrong vertex

4. Identify the error in the following Java code snippet implementing Prim's Algorithm and select the correct fix:

int minKey(int[] key, boolean[] mstSet) {
  int min = Integer.MAX_VALUE, minIndex = -1;
  for (int v = 0; v < key.length; v++) {
    if (!mstSet[v] && key[v] < min) {
      min = key[v];
      minIndex = v;
    }
  }
  return minIndex;
}

// Usage in main loop:
int u = minKey(key, mstSet);
mstSet[u] = true;

medium

A. No error; code correctly finds vertex with minimum key not in MST

B. minIndex should be initialized to 0 instead of -1

C. Return type should be void instead of int

D. The loop should start from 1 instead of 0

Solution

1. Step 1: Analyze minKey function logic

   It finds vertex with smallest key not yet included in MST correctly.

2. Step 2: Check initialization and loop

   minIndex = -1 is correct to detect no valid vertex; loop from 0 covers all vertices.

3. Final Answer:

   No error; code correctly finds vertex with minimum key not in MST -> Option A

4. Quick Check:

   minKey returns correct vertex index [OK]

Hint: minIndex = -1 signals no vertex found yet, loop from 0 covers all [OK]

Common Mistakes:

• Changing minIndex initialization incorrectly
• Changing return type wrongly
• Starting loop from 1 misses vertex 0

5. You have a weighted undirected graph with 6 vertices and the following edges:

0-1: 3, 0-3: 1, 1-2: 7, 1-4: 5, 2-4: 2, 3-4: 4, 3-5: 6, 4-5: 8

Using Prim's Algorithm starting from vertex 0, what is the total weight of the minimum spanning tree?

hard

A. 16

B. 15

C. 19

D. 21

Solution

1. Step 1: Start from vertex 0 and pick minimum edges stepwise

   Edges chosen: 0-3 (1), 0-1 (3), 3-4 (4), 4-2 (2), 3-5 (6)

2. Step 2: Sum the weights of chosen edges

   Total weight = 1 + 3 + 4 + 2 + 6 = 16

3. Step 3: Check for better MST

   Replacing 3-5 (6) with 4-5 (8) is heavier; so total is 16

4. Final Answer:

   16 -> Option A

5. Quick Check:

   Sum edges 1+3+4+2+6 = 16 [OK]

Hint: Pick smallest edges connecting new vertices stepwise [OK]

Common Mistakes:

• Choosing heavier edges unnecessarily
• Missing to update keys after adding vertices
• Not starting from vertex 0