Minimum Spanning Tree Prim's Algorithm in DSA C#

Mental Model

Start from any node and keep adding the smallest edge that connects a new node to the growing tree until all nodes are included.

Analogy: Imagine building a road network connecting cities. You start from one city and always pick the shortest road to a city not yet connected, gradually linking all cities with minimum total road length.

Graph nodes: 1, 2, 3, 4
Edges with weights:
1 --2-- 2
1 --3-- 3
2 --1-- 3
2 --4-- 4
3 --5-- 4

Initial:
[1] 2 3 4
Edges:
1 --2-- 2
1 --3-- 3
2 --1-- 3
2 --4-- 4
3 --5-- 4

Dry Run Walkthrough

Input: Graph with nodes 1,2,3,4 and edges: (1-2:2), (1-3:3), (2-3:1), (2-4:4), (3-4:5). Start from node 1.

Goal: Build a minimum spanning tree connecting all nodes with the smallest total edge weight.

Step 1: Start from node 1, add it to MST set

MST nodes: [1]
Edges considered: (1-2:2), (1-3:3)

Why: We begin from node 1 and look at edges connecting it to others.

Step 2: Pick smallest edge from MST to non-MST: (1-2:2), add node 2

MST nodes: 1 -> [2]
Edges considered: (2-3:1), (2-4:4), (1-3:3)

Why: Add the closest node to MST to keep total weight minimal.

Step 3: Pick smallest edge from MST to non-MST: (2-3:1), add node 3

MST nodes: 1 -> 2 -> [3]
Edges considered: (3-4:5), (2-4:4)

Why: Continue adding the nearest node not yet in MST.

Step 4: Pick smallest edge from MST to non-MST: (2-4:4), add node 4

MST nodes: 1 -> 2 -> 3 -> [4]
All nodes included

Why: All nodes are connected with minimum total edge weight.

Result:

MST edges: (1-2:2), (2-3:1), (2-4:4)
Total weight: 7

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

class Edge : IComparable<Edge> {
    public int Node;
    public int Weight;
    public Edge(int node, int weight) {
        Node = node;
        Weight = weight;
    }
    public int CompareTo(Edge other) {
        return Weight.CompareTo(other.Weight);
    }
}

class Graph {
    public int Vertices;
    public List<Edge>[] AdjList;

    public Graph(int vertices) {
        Vertices = vertices;
        AdjList = new List<Edge>[vertices + 1];
        for (int i = 0; i <= vertices; i++) {
            AdjList[i] = new List<Edge>();
        }
    }

    public void AddEdge(int u, int v, int w) {
        AdjList[u].Add(new Edge(v, w));
        AdjList[v].Add(new Edge(u, w));
    }

    public void PrimsMST(int start) {
        bool[] inMST = new bool[Vertices + 1];
        int[] key = new int[Vertices + 1];
        for (int i = 0; i <= Vertices; i++) key[i] = int.MaxValue;
        key[start] = 0;

        SortedSet<(int weight, int node)> pq = new SortedSet<(int, int)>();
        pq.Add((0, start));

        int totalWeight = 0;

        while (pq.Count > 0) {
            var current = pq.Min;
            pq.Remove(current);
            int u = current.node;

            if (inMST[u]) continue;
            inMST[u] = true;
            totalWeight += current.weight;

            foreach (var edge in AdjList[u]) {
                int v = edge.Node;
                int w = edge.Weight;
                if (!inMST[v] && w < key[v]) {
                    if (key[v] != int.MaxValue) pq.Remove((key[v], v));
                    key[v] = w;
                    pq.Add((w, v));
                }
            }
        }

        Console.WriteLine($"Total weight of MST: {totalWeight}");
    }
}

class Program {
    static void Main() {
        Graph g = new Graph(4);
        g.AddEdge(1, 2, 2);
        g.AddEdge(1, 3, 3);
        g.AddEdge(2, 3, 1);
        g.AddEdge(2, 4, 4);
        g.AddEdge(3, 4, 5);

        g.PrimsMST(1);
    }
}

key[start] = 0;

Initialize start node key to 0 to pick it first

var current = pq.Min; pq.Remove(current);

Extract node with smallest key not yet in MST

if (inMST[u]) continue; inMST[u] = true; totalWeight += current.weight;

Mark node as included and add edge weight to total

foreach (var edge in AdjList[u]) { if (!inMST[v] && w < key[v]) { ... } }

Update keys for adjacent nodes if smaller edge found

Output

Total weight of MST: 7

Complexity Analysis

Time: O(E log V) because each edge is processed and priority queue operations take log V time

Space: O(V + E) for adjacency list and auxiliary arrays

vs Alternative: Compared to Kruskal's algorithm which sorts edges first, Prim's is better for dense graphs using adjacency lists and priority queue

Edge Cases

Graph with single node and no edges

MST weight is zero, no edges to add

DSA C#

key[start] = 0;

Disconnected graph

Only connected component from start node is included; others ignored

DSA C#

while (pq.Count > 0) { ... }

Multiple edges with same weight

Algorithm picks any minimal edge; MST remains valid

DSA C#

if (!inMST[v] && w < key[v]) { ... }

When to Use This Pattern

When you need to connect all points with minimum total cost and the graph is weighted, reach for Prim's MST algorithm because it grows the tree step-by-step by choosing the cheapest edge.

Common Mistakes

Mistake: Not updating the priority queue when a smaller edge is found for a node
Fix: Remove the old entry and add the new one with updated smaller weight

Mistake: Including nodes multiple times by not checking if already in MST
Fix: Check and skip nodes already included in MST before processing

Summary

Builds a minimum spanning tree by adding the smallest connecting edge at each step.

Use when you want to connect all nodes with minimum total edge weight in a weighted graph.

The key insight is to always pick the closest node not yet in the tree to keep total cost minimal.

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