Minimum Spanning Tree Prim's Algorithm in DSA Java - Build from Scratch

Minimum Spanning Tree using Prim's Algorithm

📖 Scenario: You are working as a network engineer. You need to connect several computers with cables. Each cable has a cost. Your goal is to connect all computers with the least total cost.This is a classic problem solved by finding a Minimum Spanning Tree (MST) in a network graph.

🎯 Goal: Build a program that uses Prim's Algorithm to find the Minimum Spanning Tree of a given weighted graph. The program will output the edges chosen and the total cost.

📋 What You'll Learn

Create a weighted graph using an adjacency matrix

Use a variable to track the number of vertices

Implement Prim's Algorithm to find the MST

Print the edges in the MST and the total cost

💡 Why This Matters

🌍 Real World

Network engineers use MST algorithms to design cost-effective networks connecting computers or routers.

💼 Career

Understanding MST and Prim's Algorithm is important for roles in network design, optimization, and software engineering involving graph problems.

1

Create the weighted graph using an adjacency matrix

Create a 2D integer array called graph with 5 vertices. Use this exact matrix:

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

DSA Java

# Your code here

Hint

Use a 2D array to represent the graph. Each row and column represents a vertex. The value is the cost between vertices. Zero means no direct connection.

2

Add a variable for the number of vertices

Create an integer variable called V and set it to 5 to represent the number of vertices in the graph.

DSA Java

int[][] graph = {
  {0, 2, 0, 6, 0},
  {2, 0, 3, 8, 5},
  {0, 3, 0, 0, 7},
  {6, 8, 0, 0, 9},
  {0, 5, 7, 9, 0}
};
# Your code here

Hint

This variable helps to control loops and array sizes.

3

Implement Prim's Algorithm core logic

Write a method called primMST that takes the graph and V as inputs. Inside, create arrays parent, key, and mstSet. Use a loop to pick the minimum key vertex not yet included in MST. Update keys and parents for adjacent vertices. Complete the MST construction logic.

DSA Java

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

int V = 5;

// Your code here

Hint

Use arrays to track the MST structure and keys. Pick the smallest key vertex not in MST each time. Update neighbors' keys and parents.

4

Print the MST edges and total cost

Call the primMST method with graph and V as arguments. This will print the edges in the MST and the total cost.

DSA Java

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

int V = 5;

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

void primMST(int[][] graph, int V) {
    int[] parent = new int[V];
    int[] key = new int[V];
    boolean[] mstSet = new boolean[V];

    for (int i = 0; i < V; i++) {
        key[i] = Integer.MAX_VALUE;
        mstSet[i] = false;
    }

    key[0] = 0;
    parent[0] = -1;

    for (int count = 0; count < V - 1; count++) {
        int u = minKey(key, mstSet, V);
        mstSet[u] = true;

        for (int v = 0; v < V; v++) {
            if (graph[u][v] != 0 && !mstSet[v] && graph[u][v] < key[v]) {
                parent[v] = u;
                key[v] = graph[u][v];
            }
        }
    }

    printMST(parent, graph, V);
}

void printMST(int[] parent, int[][] graph, int V) {
    int totalCost = 0;
    for (int i = 1; i < V; i++) {
        totalCost += graph[i][parent[i]];
    }
    System.out.println("Edge 	Weight");
    for (int i = 1; i < V; i++) {
        System.out.println(parent[i] + " - " + i + " \t" + graph[i][parent[i]]);
    }
    System.out.println("Total cost: " + totalCost);
}

// Your code here

Hint

Call the primMST method from main to see the MST edges and total cost printed.

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