Minimum Spanning Tree Prim's Algorithm in DSA Java - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a Minimum Spanning Tree (MST)?

A Minimum Spanning Tree is a subset of edges in a connected, weighted graph that connects all vertices together without any cycles and with the minimum possible total edge weight.

beginner

What is the main idea behind Prim's Algorithm?

Prim's Algorithm builds the MST by starting from any vertex and repeatedly adding the smallest edge that connects a vertex in the MST to a vertex outside it, until all vertices are included.

beginner

In Prim's Algorithm, how do we choose the next edge to add?

We choose the edge with the smallest weight that connects a vertex already in the MST to a vertex not yet included in the MST.

intermediate

What data structure is commonly used to efficiently select the next edge in Prim's Algorithm?

A priority queue (often implemented as a min-heap) is used to quickly find and extract the edge with the smallest weight.

intermediate

Why does Prim's Algorithm always produce a Minimum Spanning Tree?

Because it always picks the smallest edge connecting the growing MST to a new vertex, it ensures no cycles and minimal total weight, satisfying MST properties.

What does Prim's Algorithm start with?

A Any single vertex

B All edges

C The largest edge

D An empty graph

Prim's Algorithm starts from any single vertex and grows the MST from there.

Which data structure helps Prim's Algorithm pick the next smallest edge efficiently?

A Priority Queue

B Stack

C Queue

D Linked List

A priority queue (min-heap) is used to efficiently select the smallest edge.

Prim's Algorithm is used to find:

A Topological order

B Shortest path between two nodes

C Maximum flow in a network

D Minimum Spanning Tree

Prim's Algorithm finds the Minimum Spanning Tree of a graph.

What condition must the graph satisfy for Prim's Algorithm to work correctly?

A Graph must be directed

B Graph must be connected

C Graph must be disconnected

D Graph must have negative weights

The graph must be connected so all vertices can be included in the MST.

When does Prim's Algorithm stop?

A After a fixed number of steps

B When all edges are added

C When all vertices are included in MST

D When the graph is empty

Prim's Algorithm stops when all vertices are included in the MST.

Explain step-by-step how Prim's Algorithm builds a Minimum Spanning Tree.

Think about growing the tree one vertex at a time by picking the smallest connecting edge.

Describe why a priority queue is important in Prim's Algorithm and how it improves efficiency.

Consider how to quickly find the smallest edge connecting the MST to the rest of the graph.

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