Minimum Spanning Tree Prim's Algorithm in DSA C# - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a Minimum Spanning Tree (MST)?

A Minimum Spanning Tree is a subset of edges in a connected, weighted graph that connects all vertices together without any cycles and with the minimum possible total edge weight.

beginner

What is the main idea behind Prim's Algorithm?

Prim's Algorithm builds the MST by starting from any vertex and repeatedly adding the smallest edge that connects a vertex in the MST to a vertex outside it, until all vertices are included.

beginner

In Prim's Algorithm, how do we choose the next edge to add?

We choose the edge with the smallest weight that connects a vertex already in the MST to a vertex not yet in the MST.

intermediate

What data structure is commonly used to efficiently select the next edge in Prim's Algorithm?

A priority queue (or min-heap) is used to quickly find and extract the edge with the smallest weight connecting the MST to the rest of the graph.

intermediate

What is the time complexity of Prim's Algorithm using a priority queue?

The time complexity is O(E log V), where E is the number of edges and V is the number of vertices, because each edge is processed and the priority queue operations take logarithmic time.

What does Prim's Algorithm start with?

A The edge with the smallest weight

B The vertex with the highest degree

C All vertices at once

D Any single vertex in the graph

Prim's Algorithm starts from any single vertex and grows the MST by adding edges.

Which data structure helps Prim's Algorithm pick the next smallest edge efficiently?

A Priority Queue

B Queue

C Stack

D Linked List

A priority queue (min-heap) is used to quickly select the smallest edge.

What condition must an edge meet to be added to the MST in Prim's Algorithm?

A Connects two vertices already in MST

B Connects a vertex in MST to one outside MST

C Has the largest weight

D Is the first edge found

Edges must connect the MST to a vertex not yet included.

What is the main goal of Prim's Algorithm?

A Find the shortest path between two vertices

B Find a cycle in the graph

C Find a Minimum Spanning Tree

D Sort the vertices

Prim's Algorithm finds a Minimum Spanning Tree.

What happens if the graph is not connected when running Prim's Algorithm?

A Algorithm fails to include all vertices

B Algorithm finds MST for all components

C Algorithm runs faster

D Algorithm ignores disconnected vertices

Prim's Algorithm only works on connected graphs; otherwise, it cannot reach all vertices.

Explain step-by-step how Prim's Algorithm builds a Minimum Spanning Tree.

Think about growing the tree one edge at a time.

Describe the role of the priority queue in Prim's Algorithm and why it improves efficiency.

Focus on how the algorithm picks edges.

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