Minimum Spanning Tree Prim's Algorithm in DSA Java - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the key array with maximum values.

DSA Java

int[] key = new int[V];
for (int i = 0; i < V; i++) {
    key[i] = [1];
}

Drag options to blanks, or click blank then click option'

A0

B-1

CInteger.MAX_VALUE

DV

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing key with 0 causes incorrect minimum edge selection.

Using negative values can cause logic errors.

We initialize the key array with Integer.MAX_VALUE to represent infinite distance before updating with actual edge weights.

2fill in blank

medium

Complete the code to pick the vertex with the minimum key value not yet included in MST.

DSA Java

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

Drag options to blanks, or click blank then click option'

Av

BInteger.MAX_VALUE

Cmin_index

Dmin

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing key[v] with Integer.MAX_VALUE inside the loop always true for first iteration but not updated later.

Using min_index instead of min causes type mismatch.

We compare key[v] with the current minimum value stored in min to find the smallest key.

3fill in blank

hard

Fix the error in the loop that updates key values for adjacent vertices.

DSA Java

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

Drag options to blanks, or click blank then click option'

Akey[v]

Bkey[u]

Cparent[u]

Dparent[v]

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing with key[u] causes wrong logic since key[u] is for the selected vertex.

Using parent array in comparison causes type errors.

We compare the edge weight graph[u][v] with key[v] to update the minimum edge weight for vertex v.

4fill in blank

hard

Fill both blanks to complete the code that prints the MST edges and their weights.

DSA Java

void printMST(int[] parent, int[][] graph) {
    System.out.println("Edge \tWeight");
    for (int i = 1; i < V; i++) {
        System.out.println(parent[i] + " - " + [1] + " \t" + [2]);
    }
}

Drag options to blanks, or click blank then click option'

Ai

Bgraph[parent[i]][i]

Cparent[i]

Dgraph[i][parent[i]]

Attempts:

3 left

💡 Hint

Common Mistakes

Swapping i and parent[i] in graph indexing causes wrong weights.

Printing parent[i] twice instead of i causes incorrect output.

We print the edge from parent[i] to i and the weight from graph[parent[i]][i].

5fill in blank

hard

Fill all three blanks to complete the main loop of Prim's algorithm updating MST and keys.

DSA Java

for (int count = 0; count < V - 1; count++) {
    int u = [1](key, mstSet);
    mstSet[u] = true;
    for (int v = 0; v < V; v++) {
        if (graph[u][v] != 0 && ![3] && graph[u][v] < [2]) {
            parent[v] = u;
            key[v] = graph[u][v];
        }
    }
}

Drag options to blanks, or click blank then click option'

AminKey

Bkey[v]

Ckey[u]

DmstSet[v]

Attempts:

3 left

💡 Hint

Common Mistakes

Using key[u] instead of key[v] in comparison.

Not checking mstSet[v] causes revisiting vertices.

We pick the vertex u with minimum key using minKey, then update key[v] if graph[u][v] is smaller than key[v] and v is not in mstSet.

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