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

Minimum Spanning Tree using Kruskal's Algorithm

📖 Scenario: You are working as a network engineer. You have a list of cities connected by roads with different costs. Your goal is to connect all cities with the minimum total road cost, so the network is efficient and cost-effective.

🎯 Goal: Build a program that uses Kruskal's algorithm to find the minimum spanning tree (MST) of a graph represented by edges with costs. The MST connects all cities with the least total cost.

📋 What You'll Learn

Create a list of edges with city pairs and their costs

Create a helper structure to track connected components (disjoint sets)

Implement Kruskal's algorithm to select edges for MST

Print the edges included in the MST and the total cost

💡 Why This Matters

🌍 Real World

Network design, such as connecting cities with roads or computers with cables at minimum cost.

💼 Career

Understanding MST algorithms is important for roles in network engineering, operations research, and software development involving graph problems.

1

Create the list of edges

Create a list called edges of tuples with these exact entries: ("A", "B", 4), ("A", "C", 3), ("B", "C", 1), ("B", "D", 2), ("C", "D", 4), ("D", "E", 2), ("E", "F", 6)

DSA C#

# Create a list called edges with the given city pairs and costs
# Your code here

Hint

Use List<(string, string, int)> and add the exact tuples inside curly braces.

2

Create the Disjoint Set helper

Create a class called DisjointSet with methods Find and Union to track connected components. Inside Main, create a DisjointSet instance called ds and initialize it with the unique cities A, B, C, D, E, F.

DSA C#

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        List edges = new List
        {
            ("A", "B", 4),
            ("A", "C", 3),
            ("B", "C", 1),
            ("B", "D", 2),
            ("C", "D", 4),
            ("D", "E", 2),
            ("E", "F", 6)
        };

        // Create DisjointSet instance ds with cities A, B, C, D, E, F
        // Your code here
    }

    // Create DisjointSet class with Find and Union methods
    // Your code here
}

Hint

Use a dictionary to store parents. Initialize each city as its own parent. Implement Find with path compression and Union to merge sets.

3

Implement Kruskal's algorithm

Sort the edges list by cost ascending. Create a list called mst to store edges in the minimum spanning tree. Use a for loop with variables city1, city2, cost to iterate over edges. For each edge, if ds.Find(city1) is not equal to ds.Find(city2), add the edge to mst and call ds.Union(city1, city2).

DSA C#

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
        List edges = new List
        {
            ("A", "B", 4),
            ("A", "C", 3),
            ("B", "C", 1),
            ("B", "D", 2),
            ("C", "D", 4),
            ("D", "E", 2),
            ("E", "F", 6)
        };

        DisjointSet ds = new DisjointSet(new List { "A", "B", "C", "D", "E", "F" });

        // Sort edges by cost and create mst list
        // Use for loop with city1, city2, cost to iterate edges
        // If ds.Find(city1) != ds.Find(city2), add edge to mst and union
        // Your code here
    }

    class DisjointSet
    {
        private Dictionary parent = new Dictionary();

        public DisjointSet(List elements)
        {
            foreach (var e in elements)
            {
                parent[e] = e;
            }
        }

        public string Find(string item)
        {
            if (parent[item] == item)
                return item;
            parent[item] = Find(parent[item]);
            return parent[item];
        }

        public void Union(string a, string b)
        {
            string rootA = Find(a);
            string rootB = Find(b);
            if (rootA != rootB)
            {
                parent[rootB] = rootA;
            }
        }
    }
}

Hint

Sort edges by cost. Loop over edges with foreach (var (city1, city2, cost) in edges). Use Find to check if cities are in different sets. If yes, add edge to MST and union sets.

4

Print the MST edges and total cost

Create a variable totalCost initialized to 0. Use a foreach loop with variables city1, city2, cost to iterate over mst. Inside the loop, print the edge in the format "city1 - city2: cost" and add cost to totalCost. After the loop, print "Total cost: totalCost".

DSA C#

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
        List edges = new List
        {
            ("A", "B", 4),
            ("A", "C", 3),
            ("B", "C", 1),
            ("B", "D", 2),
            ("C", "D", 4),
            ("D", "E", 2),
            ("E", "F", 6)
        };

        DisjointSet ds = new DisjointSet(new List { "A", "B", "C", "D", "E", "F" });

        edges = edges.OrderBy(e => e.Item3).ToList();
        List mst = new List();

        foreach (var (city1, city2, cost) in edges)
        {
            if (ds.Find(city1) != ds.Find(city2))
            {
                mst.Add((city1, city2, cost));
                ds.Union(city1, city2);
            }
        }

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

    class DisjointSet
    {
        private Dictionary parent = new Dictionary();

        public DisjointSet(List elements)
        {
            foreach (var e in elements)
            {
                parent[e] = e;
            }
        }

        public string Find(string item)
        {
            if (parent[item] == item)
                return item;
            parent[item] = Find(parent[item]);
            return parent[item];
        }

        public void Union(string a, string b)
        {
            string rootA = Find(a);
            string rootB = Find(b);
            if (rootA != rootB)
            {
                parent[rootB] = rootA;
            }
        }
    }
}

Hint

Use a variable totalCost to sum costs. Print each edge in MST with Console.WriteLine. Finally, print total cost.

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