Minimum Spanning Tree Kruskal's Algorithm in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Kruskal's MST edges

What is the output edges list after running Kruskal's algorithm on the given graph?

DSA C#

using System;
using System.Collections.Generic;

class Edge : IComparable<Edge> {
    public int Src, Dest, Weight;
    public Edge(int s, int d, int w) { Src = s; Dest = d; Weight = w; }
    public int CompareTo(Edge other) => Weight.CompareTo(other.Weight);
}

class DisjointSet {
    private int[] parent, rank;
    public DisjointSet(int n) {
        parent = new int[n]; rank = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    public int Find(int x) {
        if (parent[x] != x) parent[x] = Find(parent[x]);
        return parent[x];
    }
    public bool Union(int x, int y) {
        int rx = Find(x), ry = Find(y);
        if (rx == ry) return false;
        if (rank[rx] < rank[ry]) parent[rx] = ry;
        else if (rank[ry] < rank[rx]) parent[ry] = rx;
        else { parent[ry] = rx; rank[rx]++; }
        return true;
    }
}

class Program {
    static void Main() {
        int V = 4;
        List<Edge> edges = new List<Edge> {
            new Edge(0, 1, 10),
            new Edge(0, 2, 6),
            new Edge(0, 3, 5),
            new Edge(1, 3, 15),
            new Edge(2, 3, 4)
        };

        edges.Sort();
        DisjointSet ds = new DisjointSet(V);
        List<Edge> mst = new List<Edge>();

        foreach (var e in edges) {
            if (ds.Union(e.Src, e.Dest)) mst.Add(e);
        }

        foreach (var e in mst) {
            Console.WriteLine($"{e.Src} - {e.Dest}: {e.Weight}");
        }
    }
}

A "0 - 1: 10\n1 - 3: 15\n2 - 3: 4"

B "2 - 3: 4\n0 - 3: 5\n0 - 1: 10"

C "0 - 2: 6\n0 - 3: 5\n1 - 3: 15"

D "0 - 3: 5\n1 - 3: 15\n0 - 1: 10"

💡 Hint

Sort edges by weight and pick edges that don't form a cycle.

Kruskal's algorithm sorts edges by weight and adds edges if they connect different sets.

The edges chosen are (2-3:4), (0-3:5), and (0-1:10) forming the MST.

🧠 Conceptual

intermediate

Why does Kruskal's algorithm use a disjoint set?

What is the main purpose of using a disjoint set (union-find) data structure in Kruskal's algorithm?

A To efficiently check if adding an edge creates a cycle by checking if vertices belong to the same set.

B To store the edges in sorted order by their weights.

C To keep track of the total weight of the MST during the algorithm.

D To find the shortest path between two vertices in the graph.

💡 Hint

Think about how to avoid cycles when adding edges.

The disjoint set helps quickly determine if two vertices are already connected, preventing cycles.

🔧 Debug

advanced

Identify the error in this Kruskal's implementation snippet

What error will this code snippet cause when running Kruskal's algorithm?

DSA C#

DisjointSet ds = new DisjointSet(V);
foreach (var e in edges) {
    if (ds.Find(e.Src) != ds.Find(e.Dest)) {
        mst.Add(e);
    }
}

A The MST will contain cycles because Union is not called to merge sets.

B SyntaxError due to missing semicolon after mst.Add(e)

C NullReferenceException because ds is not initialized properly.

D The code will run correctly and produce the MST.

💡 Hint

Check if sets are merged after adding edges.

The code checks if vertices are in different sets but never merges them, so cycles can form.

❓ Predict Output

advanced

Output of MST total weight calculation

What is the total weight of the MST after running Kruskal's algorithm on this graph?

DSA C#

int V = 5;
List<Edge> edges = new List<Edge> {
    new Edge(0, 1, 2),
    new Edge(0, 3, 6),
    new Edge(1, 2, 3),
    new Edge(1, 3, 8),
    new Edge(1, 4, 5),
    new Edge(2, 4, 7),
    new Edge(3, 4, 9)
};

edges.Sort();
DisjointSet ds = new DisjointSet(V);
int totalWeight = 0;
foreach (var e in edges) {
    if (ds.Union(e.Src, e.Dest)) totalWeight += e.Weight;
}
Console.WriteLine(totalWeight);

A 20

B 23

C 19

D 16

💡 Hint

Add weights of edges chosen by Kruskal's algorithm.

The MST edges chosen have weights 2, 3, 5, and 6, totaling 16.

🧠 Conceptual

expert

Why does Kruskal's algorithm always produce a minimum spanning tree?

Which property ensures that Kruskal's algorithm always produces a minimum spanning tree?

A It sorts vertices by degree and connects the highest degree vertices first.

B It uses depth-first search to explore all edges and picks the shortest path.

C The greedy choice property and the cut property guarantee the MST is minimal and valid.

D It uses dynamic programming to find the optimal spanning tree.

💡 Hint

Think about why picking the smallest edges first works.

Kruskal's algorithm relies on the greedy choice and cut properties to ensure the MST is minimal and contains no cycles.

Practice

1. What is the main goal of Kruskal's Algorithm in graph theory?

easy

A. To sort the vertices of a graph

B. To find the shortest path between two nodes

C. To find the minimum spanning tree of a connected weighted graph

D. To detect cycles in a graph

Solution

1. Step 1: Understand the purpose of Kruskal's Algorithm

   Kruskal's Algorithm is designed to find a subset of edges that connects all vertices with the minimum total edge weight and no cycles.

2. Step 2: Compare with other graph algorithms

   Unlike shortest path algorithms or cycle detection, Kruskal's focuses on building a minimum spanning tree.

3. Final Answer:

   To find the minimum spanning tree of a connected weighted graph -> Option C

4. Quick Check:

   Minimum Spanning Tree = To find the minimum spanning tree of a connected weighted graph [OK]

Hint: Kruskal connects all nodes with least total edge weight [OK]

Common Mistakes:

• Confusing MST with shortest path
• Thinking Kruskal detects cycles only
• Assuming it sorts vertices

2. Which of the following C# code snippets correctly initializes a list of edges for Kruskal's Algorithm?

easy

A. var edges = new List<(int, int, int)> { (0, 1, 4), (1, 2, 3) };

B. var edges = new List { [0, 1, 4], [1, 2, 3] };

C. var edges = new List<(int, int, int)> { [0, 1, 4], [1, 2, 3] };

D. var edges = new List<(int, int)> { (0, 1), (1, 2) };

Solution

1. Step 1: Check tuple syntax for edges

   In C#, tuples are declared with parentheses and commas, e.g., (int, int, int). var edges = new List<(int, int, int)> { (0, 1, 4), (1, 2, 3) }; uses this correctly.

2. Step 2: Identify incorrect list initializations

   var edges = new List { [0, 1, 4], [1, 2, 3] }; uses square brackets inside List initialization which is invalid. var edges = new List<(int, int, int)> { [0, 1, 4], [1, 2, 3] }; mixes tuple and array syntax incorrectly. var edges = new List<(int, int)> { (0, 1), (1, 2) }; misses the weight part of edges.

3. Final Answer:

   var edges = new List<(int, int, int)> { (0, 1, 4), (1, 2, 3) }; -> Option A

4. Quick Check:

   Correct tuple list syntax = var edges = new List<(int, int, int)> { (0, 1, 4), (1, 2, 3) }; [OK]

Hint: Use parentheses for tuples, curly braces for list initialization [OK]

Common Mistakes:

• Using square brackets for tuples
• Omitting edge weights
• Mixing array and tuple syntax

3. What is the output MST edges after running Kruskal's Algorithm on this graph?

var edges = new List<(int, int, int)>{ (0,1,1), (1,2,2), (0,2,3), (2,3,4) };
// Vertices: 0,1,2,3
// Edges: (0-1:1), (1-2:2), (0-2:3), (2-3:4)

medium

A. [(0,1,1), (0,2,3), (2,3,4)]

B. [(0,1,1), (1,2,2), (2,3,4)]

C. [(1,2,2), (0,2,3), (2,3,4)]

D. [(0,1,1), (1,2,2)]

Solution

1. Step 1: Sort edges by weight

   Edges sorted: (0-1:1), (1-2:2), (0-2:3), (2-3:4)

2. Step 2: Pick edges without forming cycles

   Pick (0-1:1), then (1-2:2). Adding (0-2:3) creates a cycle, so skip. Add (2-3:4).

3. Final Answer:

   [(0,1,1), (1,2,2), (2,3,4)] -> Option B

4. Quick Check:

   Edges chosen without cycle = [(0,1,1), (1,2,2), (2,3,4)] [OK]

Hint: Sort edges by weight, skip edges forming cycles [OK]

Common Mistakes:

• Including edges that form cycles
• Not sorting edges by weight
• Missing edges to connect all vertices

4. Identify the error in this Kruskal's Algorithm snippet:

var edges = new List<(int, int, int)> { (0,1,1), (1,2,2), (0,2,3) };
var parent = new int[3];
for(int i=0; i<3; i++) parent[i] = i;

int Find(int x) {
  if(parent[x] == x) return x;
  return Find(parent[x]);
}

void Union(int a, int b) {
  int rootA = Find(a);
  int rootB = Find(b);
  parent[rootA] = rootB;
}

foreach(var edge in edges) {
  int u = edge.Item1, v = edge.Item2;
  if(Find(u) != Find(v)) {
    Union(u, v);
    Console.WriteLine($"Edge: {u}-{v}");
  }
}

medium

A. Union function does not use union by rank or size, causing inefficiency

B. Find function lacks path compression, causing stack overflow

C. Parent array size is incorrect for the number of vertices

D. Edges list is missing weights, so MST cannot be formed

Solution

1. Step 1: Check parent array size

   There are 3 vertices (0,1,2), so parent array size 3 is correct for these vertices.

2. Step 2: Verify if all vertices are covered

   Edges use vertices 0,1,2 only, so parent array size matches vertices count. No error here.

3. Step 3: Eliminate incorrect options

   Parent array size [3] is correct for vertices 0-2 (C wrong). Edges include weights (D wrong). Path compression absent but no stack overflow for small graph (B wrong). Thus, A is correct: lacking union by rank or size causes inefficiency.

4. Final Answer:

   Union function does not use union by rank or size, causing inefficiency -> Option A

5. Quick Check:

   Missing union by rank causes inefficiency = Union function does not use union by rank or size, causing inefficiency [OK]

Hint: Check array sizes and union-find optimizations carefully [OK]

Common Mistakes:

• Confusing inefficiency with error
• Assuming missing weights when present
• Ignoring union-find optimization importance

5. Given a graph with vertices 0 to 4 and edges:

var edges = new List<(int, int, int)> {
  (0,1,10), (0,2,6), (0,3,5), (1,3,15), (2,3,4), (3,4,2)
};

Apply Kruskal's Algorithm to find the total weight of the minimum spanning tree.

hard

A. 17

B. 27

C. 37

D. 21

Solution

1. Step 1: Sort edges by weight

   Sorted edges: (3-4:2), (2-3:4), (0-3:5), (0-2:6), (0-1:10), (1-3:15)

2. Step 2: Pick edges without cycles to connect all vertices

   Pick (3-4:2), (2-3:4), (0-3:5), (0-1:10). Adding (0-2:6) or (1-3:15) creates cycles or is unnecessary.

3. Step 3: Calculate total weight

   Total = 2 + 4 + 5 + 10 = 21

4. Final Answer:

   21 -> Option D

5. Quick Check:

   Sum MST edges weights = 21 [OK]

Hint: Sort edges, pick smallest without cycle until all connected [OK]

Common Mistakes:

• Adding edges that form cycles
• Forgetting to connect all vertices
• Misordering edges by weight