Minimum Spanning Tree Prim's Algorithm in DSA C# - Build from Scratch

Minimum Spanning Tree using Prim's Algorithm

📖 Scenario: You are working as a network engineer. You need to connect several computers with cables. Each cable has a cost. Your goal is to connect all computers with the least total cost.This is a classic problem solved by finding a Minimum Spanning Tree (MST) in a graph. You will use Prim's algorithm to find the MST.

🎯 Goal: Build a program that uses Prim's algorithm to find the Minimum Spanning Tree of a given weighted graph. The program will output the edges chosen and the total cost.

📋 What You'll Learn

Create a graph using an adjacency matrix with exact weights

Create a boolean array to track visited nodes

Implement Prim's algorithm core logic to find MST

Print the MST edges and total cost

💡 Why This Matters

🌍 Real World

Network design, where connecting devices with minimum cable cost is essential.

💼 Career

Understanding MST and Prim's algorithm is important for roles in network engineering, software development involving graphs, and optimization problems.

1

Create the graph as an adjacency matrix

Create a 2D integer array called graph representing the weighted graph with 5 nodes. Use this exact matrix:
int[,] graph = new int[5,5] { {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} };

DSA C#

# Create the graph adjacency matrix
# Your code here

Hint

This matrix shows the cost between nodes. Zero means no direct connection.

2

Create the visited array

Create a boolean array called visited with 5 elements, all initially set to false. This will track which nodes are included in the MST.

DSA C#

int[,] graph = new int[5,5] { {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} };
# Create the visited array
# Your code here

Hint

This array keeps track of nodes already added to the MST.

3

Implement Prim's algorithm core logic

Write code to find the Minimum Spanning Tree using Prim's algorithm. Use variables minCost initialized to 0, and a loop that runs 4 times to select edges. Use visited to track nodes. For each iteration, find the smallest edge connecting a visited node to an unvisited node. Store the edges in a list of tuples called mstEdges with elements (int from, int to, int cost).

DSA C#

int[,] graph = new int[5,5] { {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} };
bool[] visited = new bool[5] { false, false, false, false, false };
// Implement Prim's algorithm core logic here
// Your code here

Hint

Start from node 0. In each step, pick the smallest edge from visited to unvisited nodes.

4

Print the MST edges and total cost

Print each edge in mstEdges in the format "Edge from {from} to {to} with cost {cost}". Then print the total cost as "Total cost: {minCost}".

DSA C#

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        int[,] graph = new int[5,5] { {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} };
        bool[] visited = new bool[5] { false, false, false, false, false };

        int minCost = 0;
        List mstEdges = new List();

        visited[0] = true; // Start from node 0

        for (int edgesCount = 0; edgesCount < 4; edgesCount++)
        {
            int min = int.MaxValue;
            int from = -1;
            int to = -1;

            for (int i = 0; i < 5; i++)
            {
                if (visited[i])
                {
                    for (int j = 0; j < 5; j++)
                    {
                        if (!visited[j] && graph[i,j] != 0 && graph[i,j] < min)
                        {
                            min = graph[i,j];
                            from = i;
                            to = j;
                        }
                    }
                }
            }

            visited[to] = true;
            mstEdges.Add((from, to, min));
            minCost += min;
        }

        // Print MST edges and total cost
        // Your code here
    }
}

Hint

Use a foreach loop to print each edge, then print the total cost.

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