Minimum Spanning Tree Kruskal's Algorithm in DSA C#

Mental Model

Pick the smallest edges one by one to connect all points without making loops.

Analogy: Imagine building roads between cities using the cheapest roads first, but never making a circle of roads.

Graph:
  (1)---2---(2)
   |         |
   3         1
   |         |
  (3)---4---(4)

Edges with weights shown between nodes.

Dry Run Walkthrough

Input: Graph with nodes 1,2,3,4 and edges: (1-2:2), (1-3:3), (2-4:1), (3-4:4)

Goal: Find the minimum set of edges connecting all nodes with the smallest total weight and no cycles.

Step 1: Sort edges by weight: (2-4:1), (1-2:2), (1-3:3), (3-4:4)

(Edges sorted) [2-4:1] -> [1-2:2] -> [1-3:3] -> [3-4:4]

Why: We pick edges from smallest to largest to keep total cost low.

Step 2: Pick edge (2-4:1), add to MST since it connects two separate nodes

MST edges: (2-4:1)
Sets: {1}, {2,4}, {3}

Why: No cycle formed, connects nodes 2 and 4.

Step 3: Pick edge (1-2:2), add to MST since it connects node 1 to set {2,4}

MST edges: (2-4:1), (1-2:2)
Sets: {1,2,4}, {3}

Why: No cycle formed, connects node 1 to existing set.

Step 4: Pick edge (1-3:3), add to MST since it connects node 3 to set {1,2,4}

MST edges: (2-4:1), (1-2:2), (1-3:3)
Sets: {1,2,3,4}

Why: No cycle formed, all nodes connected now.

Step 5: Skip edge (3-4:4) because it forms a cycle in MST

MST edges unchanged: (2-4:1), (1-2:2), (1-3:3)

Why: Adding this edge would create a loop, which MST forbids.

Result:

MST edges: (2-4:1) -> (1-2:2) -> (1-3:3)
Total weight: 6

Annotated Code

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) { return Weight.CompareTo(other.Weight); }
}

class DisjointSet {
    private int[] parent, rank;
    public DisjointSet(int n) {
        parent = new int[n + 1];
        rank = new int[n + 1];
        for (int i = 1; i <= n; i++) parent[i] = i;
    }
    public int Find(int x) {
        if (parent[x] != x) parent[x] = Find(parent[x]); // path compression
        return parent[x];
    }
    public bool Union(int x, int y) {
        int xRoot = Find(x);
        int yRoot = Find(y);
        if (xRoot == yRoot) return false; // same set, cycle
        if (rank[xRoot] < rank[yRoot]) parent[xRoot] = yRoot;
        else if (rank[yRoot] < rank[xRoot]) parent[yRoot] = xRoot;
        else {
            parent[yRoot] = xRoot;
            rank[xRoot]++;
        }
        return true;
    }
}

class KruskalMST {
    public static List<Edge> FindMST(int n, List<Edge> edges) {
        edges.Sort(); // sort edges by weight
        DisjointSet ds = new DisjointSet(n);
        List<Edge> mst = new List<Edge>();
        foreach (var edge in edges) {
            if (ds.Union(edge.Src, edge.Dest)) {
                mst.Add(edge); // add edge if no cycle
            }
        }
        return mst;
    }

    static void Main() {
        int n = 4;
        List<Edge> edges = new List<Edge> {
            new Edge(1, 2, 2),
            new Edge(1, 3, 3),
            new Edge(2, 4, 1),
            new Edge(3, 4, 4)
        };
        var mst = FindMST(n, edges);
        int totalWeight = 0;
        foreach (var e in mst) {
            Console.WriteLine($"Edge: {e.Src} - {e.Dest} Weight: {e.Weight}");
            totalWeight += e.Weight;
        }
        Console.WriteLine($"Total weight: {totalWeight}");
    }
}

edges.Sort(); // sort edges by weight

sort edges ascending by weight to pick smallest first

if (ds.Union(edge.Src, edge.Dest)) {

try to union sets; if no cycle, add edge to MST

if (parent[x] != x) parent[x] = Find(parent[x]); // path compression

find root parent with path compression to speed up future finds

if (xRoot == yRoot) return false; // same set, cycle

detect cycle by checking if both nodes share root

mst.Add(edge); // add edge if no cycle

include edge in MST because it connects new nodes

Output

Edge: 2 - 4 Weight: 1

Edge: 1 - 2 Weight: 2

Edge: 1 - 3 Weight: 3

Total weight: 6

Complexity Analysis

Time: O(E log E) because sorting edges dominates and union-find operations are almost O(1)

Space: O(V + E) for storing edges and disjoint set data structures

vs Alternative: Compared to Prim's algorithm, Kruskal is simpler for sparse graphs and uses sorting edges instead of priority queues.

Edge Cases

Empty graph with no edges

Returns empty MST with total weight 0

DSA C#

edges.Sort(); // sort edges by weight

Graph with single node and no edges

Returns empty MST since no edges to connect

DSA C#

edges.Sort(); // sort edges by weight

Graph with multiple edges having same weight

Algorithm picks edges in sorted order; union-find prevents cycles

DSA C#

if (ds.Union(edge.Src, edge.Dest)) {

When to Use This Pattern

When you need to connect all points with minimum total cost and no loops, reach for Kruskal's MST using edge sorting and union-find to avoid cycles.

Common Mistakes

Mistake: Not sorting edges before processing
Fix: Sort edges by weight first to ensure smallest edges are chosen first

Mistake: Not using union-find or cycle detection, causing loops in MST
Fix: Use union-find to check if adding an edge creates a cycle before adding it

Summary

Builds a minimum cost tree connecting all nodes without cycles by picking edges from smallest to largest.

Use when you want the cheapest way to connect all points in a network without loops.

The key is sorting edges by weight and using union-find to avoid cycles while adding edges.

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