Minimum Spanning Tree Prim's Algorithm in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Prim's Algorithm on a Small Graph

What is the total weight of the minimum spanning tree after running Prim's algorithm on this graph?

DSA Java

import java.util.*;

class Edge {
    int to, weight;
    Edge(int to, int weight) {
        this.to = to;
        this.weight = weight;
    }
}

public class MST {
    public static int prim(int n, List<List<Edge>> graph) {
        boolean[] visited = new boolean[n];
        PriorityQueue<Edge> pq = new PriorityQueue<>(Comparator.comparingInt(e -> e.weight));
        pq.add(new Edge(0, 0));
        int totalWeight = 0;
        while (!pq.isEmpty()) {
            Edge current = pq.poll();
            if (visited[current.to]) continue;
            visited[current.to] = true;
            totalWeight += current.weight;
            for (Edge e : graph.get(current.to)) {
                if (!visited[e.to]) pq.add(e);
            }
        }
        return totalWeight;
    }

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

        System.out.println(prim(n, graph));
    }
}

A 7

B 6

C 8

D 9

💡 Hint

Think about choosing edges with the smallest weights connecting new vertices.

Prim's algorithm starts from node 0, picks edge (0-1) with weight 1, then edge (1-2) with weight 2, then edge (2-3) with weight 3. Total weight is 1+2+3=6.

🧠 Conceptual

intermediate

Understanding Prim's Algorithm Data Structures

Which data structure is best suited to efficiently select the next edge with the smallest weight in Prim's algorithm?

A Priority Queue (Min-Heap)

B Queue

C Stack

D Hash Map

💡 Hint

You want to always pick the smallest edge quickly.

A priority queue (min-heap) allows quick access to the smallest edge weight, which is essential for Prim's algorithm efficiency.

🔧 Debug

advanced

Identify the Bug in Prim's Algorithm Implementation

What error will this code produce when running Prim's algorithm on a connected graph?

DSA Java

import java.util.*;

class Edge {
    int to, weight;
    Edge(int to, int weight) {
        this.to = to;
        this.weight = weight;
    }
}

public class MST {
    public static int prim(int n, List<List<Edge>> graph) {
        boolean[] visited = new boolean[n];
        PriorityQueue<Edge> pq = new PriorityQueue<>(Comparator.comparingInt(e -> e.weight));
        pq.add(new Edge(0, 0));
        int totalWeight = 0;
        while (!pq.isEmpty()) {
            Edge current = pq.poll();
            if (visited[current.to]) continue;
            visited[current.to] = true;
            totalWeight += current.weight;
            for (Edge e : graph.get(current.to)) {
                if (visited[e.to]) pq.add(e);
            }
        }
        return totalWeight;
    }
}

A The code throws a ClassCastException in the priority queue.

B The code runs correctly and returns the MST weight.

C The code throws a NullPointerException due to uninitialized graph.

D The code causes an infinite loop because edges to visited nodes are added repeatedly.

💡 Hint

Check the condition inside the for loop when adding edges to the priority queue.

The code adds edges to already visited nodes back into the priority queue, causing repeated processing and an infinite loop.

❓ Predict Output

advanced

Prim's Algorithm Output on Disconnected Graph

What will be the output of the Prim's algorithm function when run on this disconnected graph?

DSA Java

import java.util.*;

class Edge {
    int to, weight;
    Edge(int to, int weight) {
        this.to = to;
        this.weight = weight;
    }
}

public class MST {
    public static int prim(int n, List<List<Edge>> graph) {
        boolean[] visited = new boolean[n];
        PriorityQueue<Edge> pq = new PriorityQueue<>(Comparator.comparingInt(e -> e.weight));
        pq.add(new Edge(0, 0));
        int totalWeight = 0;
        while (!pq.isEmpty()) {
            Edge current = pq.poll();
            if (visited[current.to]) continue;
            visited[current.to] = true;
            totalWeight += current.weight;
            for (Edge e : graph.get(current.to)) {
                if (!visited[e.to]) pq.add(e);
            }
        }
        return totalWeight;
    }

    public static void main(String[] args) {
        int n = 5;
        List<List<Edge>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
        graph.get(0).add(new Edge(1, 2));
        graph.get(1).add(new Edge(0, 2));
        graph.get(1).add(new Edge(2, 3));
        graph.get(2).add(new Edge(1, 3));
        // Node 3 and 4 are disconnected

        System.out.println(prim(n, graph));
    }
}

A Throws an exception

B 0

C 5

D 2

💡 Hint

Prim's algorithm only covers the connected component starting from node 0.

The algorithm covers nodes 0,1,2 with edges 2 and 3, total 5. Nodes 3 and 4 are disconnected and not included.

🧠 Conceptual

expert

Prim's Algorithm Time Complexity Analysis

What is the time complexity of Prim's algorithm when implemented using an adjacency list and a binary heap priority queue for a graph with V vertices and E edges?

A O(E log V)

B O(E + V log V)

C O(V log V + E)

D O(V^2)

💡 Hint

Consider the cost of extracting minimum edges and updating the priority queue.

Using a binary heap, each edge can be added to the priority queue once, and extracting minimum takes O(log V). So total is O(E log V).

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