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

Practice - 5 Tasks

1fill in blank

easy

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

DSA C#

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'

Aint.MaxValue

B0

C-1

DV

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 instead of int.MaxValue causes incorrect minimum edge selection.

Using negative values can cause logic errors.

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

2fill in blank

medium

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

DSA C#

int minKey = int.MaxValue, minIndex = -1;
for (int v = 0; v < V; v++) {
    if (!mstSet[v] && key[v] < [1]) {
        minKey = key[v];
        minIndex = v;
    }
}

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

Akey[v]

BminKey

CminIndex

Dv

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing with key[v] instead of minKey causes wrong vertex selection.

Using minIndex in comparison leads to errors.

We compare key[v] with minKey to find the smallest key value among vertices not yet in MST.

3fill in blank

hard

Fix the error in updating the key and parent arrays for adjacent vertices.

DSA C#

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]

Bparent[v]

Cgraph[u, v]

DmstSet[v]

Attempts:

3 left

💡 Hint

Common Mistakes

Comparing with parent[v] instead of key[v] causes logic errors.

Comparing with graph[u, v] itself is incorrect.

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

4fill in blank

hard

Fill both blanks to complete the loop that builds the MST by repeating for all vertices.

DSA C#

for (int count = 0; count < [1] - 1; count++) {
    int u = [2](key, mstSet);
    mstSet[u] = true;
    // Update key and parent arrays
}

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

AV

BV - 1

CMinKeyIndex

DMinKey

Attempts:

3 left

💡 Hint

Common Mistakes

Using V - 1 in loop condition causes off-by-one error.

Using MinKey instead of MinKeyIndex causes type errors.

We loop V-1 times to include all vertices except the first, and select the vertex with minimum key using MinKeyIndex function.

5fill in blank

hard

Fill all three blanks to print the constructed MST edges and their weights.

DSA C#

Console.WriteLine("Edge \tWeight");
for (int i = 1; i < [1]; i++) {
    Console.WriteLine($"{parent[i]} - [2] \t[3]", graph[i, parent[i]]);
}

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

AV

Bi

Cgraph[i, parent[i]]

Dparent[i]

Attempts:

3 left

💡 Hint

Common Mistakes

Looping from 0 causes printing invalid edges.

Using parent[i] in place of i in string interpolation causes wrong output.

We loop from 1 to V-1 to print edges from parent to i with their weights from graph matrix.

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