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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Prim's Algorithm on a Small Graph

What is the printed MST edges and their weights after running Prim's algorithm starting from vertex 0 on this graph?

DSA C#

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}
};

// Prim's algorithm implementation
int V = 5;
int[] parent = new int[V];
int[] key = new int[V];
bool[] mstSet = new bool[V];

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

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

for (int count = 0; count < V - 1; count++) {
    int u = -1;
    int minKey = int.MaxValue;
    for (int v = 0; v < V; v++) {
        if (!mstSet[v] && key[v] < minKey) {
            minKey = key[v];
            u = 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];
        }
    }
}

for (int i = 1; i < V; i++) {
    Console.WriteLine($"{parent[i]} - {i} : {graph[i, parent[i]]}");
}

A

0 - 1 : 2
1 - 2 : 3
0 - 3 : 6
1 - 4 : 5

B

0 - 1 : 2
0 - 2 : 3
3 - 4 : 9
1 - 4 : 5

C

0 - 1 : 2
1 - 2 : 3
3 - 4 : 9
0 - 4 : 5

D

0 - 1 : 2
2 - 3 : 6
1 - 4 : 5
0 - 2 : 3

💡 Hint

Trace the algorithm step-by-step, always picking the smallest edge connecting MST to a new vertex.

Prim's algorithm starts from vertex 0, picks edge 0-1 with weight 2, then 1-2 with weight 3, then 0-3 with weight 6, and finally 1-4 with weight 5, forming the MST.

🧠 Conceptual

intermediate

Understanding Prim's Algorithm Data Structures

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

A Stack

B Queue

C Priority Queue (Min-Heap)

D Hash Table

💡 Hint

Think about how to always pick the smallest edge quickly.

Prim's algorithm uses a priority queue (min-heap) to pick the edge with the smallest weight efficiently at each step.

❓ Predict Output

advanced

Prim's Algorithm Output on a Disconnected Graph

What will be the output or error when running Prim's algorithm on this disconnected graph starting from vertex 0?

DSA C#

int[,] graph = {
  {0, 1, 0, 0},
  {1, 0, 0, 0},
  {0, 0, 0, 2},
  {0, 0, 2, 0}
};

int V = 4;
int[] parent = new int[V];
int[] key = new int[V];
bool[] mstSet = new bool[V];

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

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

for (int count = 0; count < V - 1; count++) {
    int u = -1;
    int minKey = int.MaxValue;
    for (int v = 0; v < V; v++) {
        if (!mstSet[v] && key[v] < minKey) {
            minKey = key[v];
            u = v;
        }
    }
    if (u == -1) break;
    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];
        }
    }
}

for (int i = 1; i < V; i++) {
    if (parent[i] == 0 || parent[i] > 0) {
        Console.WriteLine($"{parent[i]} - {i} : {graph[i, parent[i]]}");
    } else {
        Console.WriteLine($"{i} is not connected to MST");
    }
}

A

0 - 1 : 1
2 - 3 : 2
3 is not connected to MST

B

0 - 1 : 1
2 is not connected to MST
3 is not connected to MST

C

0 - 1 : 1
2 - 3 : 2

D Runtime error due to uninitialized parent values

💡 Hint

Disconnected vertices won't get included in MST and parent remains default.

Vertices 2 and 3 are disconnected from vertex 0's component, so they are not included in MST and print as not connected.

🔧 Debug

advanced

Identify the Bug in Prim's Algorithm Implementation

What is the bug in this Prim's algorithm code snippet that causes incorrect MST construction?

DSA C#

int V = 4;
int[] parent = new int[V];
int[] key = new int[V];
bool[] mstSet = new bool[V];

for (int i = 0; i < V; i++) {
    key[i] = int.MaxValue;
    mstSet[i] = false;
    parent[i] = -1;
}

key[0] = 0;

for (int count = 0; count < V - 1; count++) {
    int u = -1;
    int minKey = int.MaxValue;
    for (int v = 0; v < V; v++) {
        if (!mstSet[v] && key[v] < minKey) {
            minKey = key[v];
            u = v;
        }
    }
    mstSet[u] = true;
    for (int v = 0; v < V; v++) {
        if (graph[u, v] != 0 && !mstSet[v] && graph[u, v] < key[v]) {
            key[v] = graph[u, v];
            // Missing parent update here
        }
    }
}

A The loop runs one extra iteration causing index out of range

B The key array is not initialized properly before the loop

C The mstSet array is not updated after selecting vertex u

D The parent array is never updated inside the inner loop, so MST edges are incorrect

💡 Hint

Check if the parent array tracks the MST edges correctly.

Without updating parent[v] when key[v] changes, the MST edges are not recorded correctly.

🚀 Application

expert

Minimum Spanning Tree Weight Calculation

Given the following weighted graph, what is the total weight of the MST found by Prim's algorithm starting from vertex 0?

DSA C#

int[,] graph = {
  {0, 10, 6, 5},
  {10, 0, 0, 15},
  {6, 0, 0, 4},
  {5, 15, 4, 0}
};

int V = 4;
int[] parent = new int[V];
int[] key = new int[V];
bool[] mstSet = new bool[V];

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

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

for (int count = 0; count < V - 1; count++) {
    int u = -1;
    int minKey = int.MaxValue;
    for (int v = 0; v < V; v++) {
        if (!mstSet[v] && key[v] < minKey) {
            minKey = key[v];
            u = 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];
        }
    }
}

int totalWeight = 0;
for (int i = 1; i < V; i++) {
    totalWeight += graph[i, parent[i]];
}
Console.WriteLine(totalWeight);

A 19

B 15

C 20

D 25

💡 Hint

Sum the weights of edges selected in MST after running Prim's algorithm.

The MST edges are 0-3 (5), 3-2 (4), and 0-1 (10), total weight = 5 + 4 + 10 = 19.

Practice

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

easy

A. To find the minimum spanning tree of a connected weighted graph

B. To find the shortest path between two nodes

C. To detect cycles in a graph

D. To sort the vertices of a graph

Solution

1. Step 1: Understand Prim's Algorithm purpose

   Prim's Algorithm is designed to find a tree that connects all vertices with the smallest total edge weight.

2. Step 2: Compare with other graph tasks

   Shortest path, cycle detection, and sorting vertices are different problems solved by other algorithms.

3. Final Answer:

   To find the minimum spanning tree of a connected weighted graph -> Option A

4. Quick Check:

   Prim's Algorithm = Minimum Spanning Tree [OK]

Hint: Prim's always builds a tree with minimum total edge weight [OK]

Common Mistakes:

• Confusing Prim's with shortest path algorithms
• Thinking it detects cycles
• Assuming it sorts graph nodes

2. Which of the following C# code snippets correctly initializes a priority queue for Prim's Algorithm using .NET 6+ syntax?

easy

A. var pq = new Queue<int>();

B. var pq = new Stack<int>();

C. var pq = new SortedList();

D. var pq = new PriorityQueue();

Solution

1. Step 1: Identify correct data structure for Prim's

   Prim's Algorithm requires a priority queue to pick the minimum weight edge efficiently.

2. Step 2: Match with C# syntax

   PriorityQueue<TElement, TPriority> is the correct .NET 6+ class for priority queues.

3. Final Answer:

   var pq = new PriorityQueue<int, int>(); -> Option D

4. Quick Check:

   PriorityQueue<int,int> = Correct initialization [OK]

Hint: Use PriorityQueue<TElement, TPriority> in .NET 6+ [OK]

Common Mistakes:

• Using Queue instead of PriorityQueue
• Using Stack which is LIFO, not priority-based
• Using SortedList which is not a priority queue

3. Consider the following C# code snippet implementing Prim's Algorithm on a graph with 4 nodes and edges with weights:

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

var mst = PrimMST(graph);
Console.WriteLine(string.Join(", ", mst));

// PrimMST returns the parent array representing MST

What is the output printed by this code?

medium

A. [ -1, 0, 1, 0 ]

B. [ 0, 2, 1, 3 ]

C. [ -1, 2, 0, 1 ]

D. [ 0, -1, 1, 2 ]

Solution

1. Step 1: Run Prim's Algorithm on given graph

   Start from node 0: parent[0] = -1. Choose edges with minimum weights connecting new nodes: 0-1 (2), 1-2 (3), 0-3 (6).

2. Step 2: Construct parent array

   Node 0 has no parent (-1). Node 1's parent is 0. Node 2's parent is 1. Node 3's parent is 0.

3. Final Answer:

   [ -1, 0, 1, 0 ] -> Option A

4. Quick Check:

   Parent array = [-1,0,1,0] [OK]

Hint: Trace edges picked by minimum weight stepwise [OK]

Common Mistakes:

• Mixing up parent indices
• Starting from wrong node
• Ignoring zero weights as no edge

4. The following C# code snippet for Prim's Algorithm has a bug. What is the error?

int V = 5;
int[] key = new int[V];
bool[] mstSet = new bool[V];

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

key[0] = 0;
int parent[] = new int[V];

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

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

What is the bug?

medium

A. The loop should run from 0 to V instead of V - 1

B. The key array is not initialized with int.MaxValue

C. The parent array is not initialized before use

D. The mstSet array is not updated correctly

Solution

1. Step 1: Check parent array initialization

   The parent array is declared but not initialized with any default values, so it contains garbage values initially.

2. Step 2: Importance of initializing parent array

   Without initialization, parent[v] may hold invalid data before assignment, causing incorrect MST representation.

3. Final Answer:

   The parent array is not initialized before use -> Option C

4. Quick Check:

   Parent array must be initialized [OK]

Hint: Always initialize parent array before MST loop [OK]

Common Mistakes:

• Ignoring uninitialized parent array
• Thinking key or mstSet are incorrect
• Changing loop bounds unnecessarily

5. You have a weighted graph with 6 nodes and edges:

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

Using Prim's Algorithm starting from node 0, which edges will be included in the minimum spanning tree?

hard

A. (0-1), (1-3), (3-4), (4-5), (2-3)

B. (0-2), (1-2), (1-3), (3-4), (4-5)

C. (0-2), (1-2), (3-4), (4-5), (0-1)

D. (0-1), (1-2), (1-3), (3-4), (4-5)

Solution

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

   From 0, edges are (0-1:4) and (0-2:3). Pick (0-2) with weight 3.

2. Step 2: Add next minimum edges connecting new nodes

   From nodes {0,2}, edges are (1-2:1), (0-1:4), (2-3:4). Pick (1-2) with weight 1.

3. Step 3: Continue adding minimum edges

   From {0,1,2}, edges are (1-3:2), (2-3:4), (0-1:4). Pick (1-3) with weight 2.

4. Step 4: Add edges to connect remaining nodes

   From {0,1,2,3}, edges are (3-4:2), (4-5:6). Pick (3-4) with weight 2, then (4-5) with weight 6.

5. Final Answer:

   (0-2), (1-2), (1-3), (3-4), (4-5) -> Option B

6. Quick Check:

   Edges chosen minimize total weight [OK]

Hint: Always pick smallest edge connecting new node [OK]

Common Mistakes:

• Picking edges with higher weights first
• Not updating the set of connected nodes
• Including edges that form cycles