Minimum Spanning Tree Prim's Algorithm in DSA C# - Execution Trace

Concept Flow - Minimum Spanning Tree Prim's Algorithm

Start with any node

↓

Add node to MST set

↓

Find edges from MST to non-MST nodes

↓

Pick edge with smallest weight

↓

Add connected node to MST

↓

Repeat until all nodes in MST

Prim's algorithm builds the MST by starting from one node, then repeatedly adding the smallest edge connecting the MST to a new node.

Execution Sample

DSA C#

int[] key = new int[V];
for (int i = 0; i < V; i++) {
  key[i] = int.MaxValue;
}
bool[] mstSet = new bool[V];
key[0] = 0;
for (int count = 0; count < V - 1; count++) {
  int u = MinKey(key, mstSet);
  mstSet[u] = true;
  UpdateKeys(u, key, mstSet);
}

This code initializes keys, picks the minimum key node not in MST, adds it, and updates keys for neighbors.

Execution Table

Step	Operation	Nodes in MST Set	Edge Chosen (u-v)	Key Array	Visual MST State
1	Initialize: Start at node 0	[0]	None	[0, ∞, ∞, ∞]	0
2	Pick min key node not in MST: node 0	[0]	None	[0, ∞, ∞, ∞]	0
3	Update keys for neighbors of 0	[0]	Edges: 0-1(1), 0-2(4)	[0, 1, 4, ∞]	0
4	Pick min key node not in MST: node 1	[0,1]	0-1	[0, 1, 4, ∞]	0 - 1
5	Update keys for neighbors of 1	[0,1]	Edges: 1-2(2), 1-3(6)	[0, 1, 2, 6]	0 - 1
6	Pick min key node not in MST: node 2	[0,1,2]	1-2	[0, 1, 2, 6]	0 - 1 - 2
7	Update keys for neighbors of 2	[0,1,2]	Edges: 2-3(3)	[0, 1, 2, 3]	0 - 1 - 2
8	Pick min key node not in MST: node 3	[0,1,2,3]	2-3	[0, 1, 2, 3]	0 - 1 - 2 - 3
9	All nodes included, MST complete	[0,1,2,3]	None	[0, 1, 2, 3]	0 - 1 - 2 - 3

💡 All nodes are included in MST set, algorithm stops.

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 7	Final
key	[0, ∞, ∞, ∞]	[0, 1, 4, ∞]	[0, 1, 2, 6]	[0, 1, 2, 3]	[0, 1, 2, 3]
mstSet	[false, false, false, false]	[true, false, false, false]	[true, true, false, false]	[true, true, true, false]	[true, true, true, true]
MST Nodes	[]	[0]	[0,1]	[0,1,2]	[0,1,2,3]

Key Moments - 3 Insights

Why do we update the key array after adding a node to MST?

After adding a node, we check its neighbors to see if connecting through this node offers a smaller edge weight. This is shown in steps 3, 5, and 7 where key values get updated.

Why do we pick the node with the smallest key not in MST?

Picking the smallest key ensures we add the closest node to MST next, keeping the total weight minimal. This is seen in steps 2, 4, 6, and 8 where the minimum key node is chosen.

What happens when all nodes are in MST?

When all nodes are included, the algorithm stops as the MST is complete. This is shown in step 9 where MST contains all nodes.

Visual Quiz - 3 Questions

Look at the execution table, what is the key array after step 5?

A [0, 1, 2, 6]

B [0, 1, 4, ∞]

C [0, 1, 2, 3]

D [∞, ∞, ∞, ∞]

💡 Hint

Check the 'Key Array' column in row for step 5 in the execution table.

At which step does node 2 get added to the MST set?

A Step 4

B Step 6

C Step 7

D Step 8

💡 Hint

Look at the 'Nodes in MST Set' column to see when node 2 appears.

If the edge 1-2 had weight 5 instead of 2, how would the key array change after step 5?

A [0, 1, 2, 6]

B [0, 1, 5, 6]

C [0, 1, 4, 6]

D [0, 1, 3, 6]

💡 Hint

Check how key values update based on edge weights in step 5.

Concept Snapshot

Prim's Algorithm builds MST by:
- Starting at any node
- Adding smallest edge connecting MST to new node
- Updating keys for neighbors
- Repeating until all nodes included
Key array tracks minimum edge weights to MST
MST set tracks included nodes

Full Transcript

Prim's algorithm starts from a chosen node and builds the minimum spanning tree by adding the smallest edge connecting the tree to a new node. It uses a key array to keep track of the smallest edge weight to each node not yet in the MST. At each step, it picks the node with the smallest key value not in the MST, adds it to the MST set, and updates the keys of its neighbors if smaller edges are found. This process repeats until all nodes are included in the MST. The execution table shows each step, the nodes included, the edge chosen, and the key array updates. The variable tracker shows how the key array and MST set change over time. Key moments clarify why keys are updated, why the smallest key node is chosen, and when the algorithm stops. The visual quiz tests understanding of key array values, MST inclusion steps, and effects of edge weight changes.

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