Minimum Spanning Tree Kruskal's Algorithm in DSA C# - Execution Trace

Concept Flow - Minimum Spanning Tree Kruskal's Algorithm

Start with all edges sorted by weight

↓

Pick smallest edge

↓

Check if adding edge forms cycle?

↓

Add edge to MST

↓

More edges left?

No→Done

Yes↓

Repeat picking next smallest edge

Kruskal's algorithm sorts edges by weight and adds them one by one to the MST if they don't form a cycle, until all vertices are connected.

Execution Sample

DSA C#

edges = [("A","B",1), ("B","C",3), ("A","C",2)]
Sort edges by weight
Initialize MST empty
For each edge in sorted edges:
  If adding edge doesn't form cycle:
    Add edge to MST
Return MST

This code builds a minimum spanning tree by adding edges from smallest to largest weight without creating cycles.

Execution Table

Step	Operation	Edge Considered	Cycle Check Result	MST Edges	Visual MST State
1	Sort edges by weight	-	-	[]	Empty MST
2	Consider edge	(A,B,1)	No cycle	[(A,B)]	A--1--B
3	Consider edge	(A,C,2)	No cycle	[(A,B), (A,C)]	A--1--B | 2 | C
4	Consider edge	(B,C,3)	Forms cycle	[(A,B), (A,C)]	A--1--B | 2 | C
5	No more edges	-	-	[(A,B), (A,C)]	Final MST: A--B and A--C

💡 All edges considered or MST connects all vertices without cycles

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
edges_sorted	[('A','B',1), ('B','C',3), ('A','C',2)]	[('A','B',1), ('A','C',2), ('B','C',3)]	[('A','B',1), ('A','C',2), ('B','C',3)]	[('A','B',1), ('A','C',2), ('B','C',3)]	[('A','B',1), ('A','C',2), ('B','C',3)]
MST	[]	[('A','B')]	[('A','B'), ('A','C')]	[('A','B'), ('A','C')]	[('A','B'), ('A','C')]
CycleCheck(B,C)	N/A	N/A	N/A	True	True

Key Moments - 3 Insights

Why do we discard the edge (B,C,3) even though it connects two vertices?

Because adding (B,C,3) creates a cycle with edges (A,B) and (A,C), so it is discarded to keep MST cycle-free as shown in step 4 of execution_table.

How do we know when to stop adding edges?

We stop when all vertices are connected without cycles or when no edges remain, as shown in step 5 where MST connects all vertices.

Why do we sort edges by weight first?

Sorting ensures we always pick the smallest edge available to keep total MST weight minimal, as shown in step 1.

Visual Quiz - 3 Questions

Look at the execution_table, what edges are in MST after step 3?

A [(A,B)]

B [(A,B), (A,C)]

C [(B,C)]

D []

💡 Hint

Check the MST Edges column at step 3 in execution_table

At which step does the algorithm discard an edge due to cycle formation?

A Step 2

B Step 3

C Step 4

D Step 5

💡 Hint

Look at Cycle Check Result column in execution_table

If the edge (B,C,3) had weight 0.5, what would happen in the MST after step 3?

A Edge (B,C) would be added before (A,C)

B Edge (B,C) would be discarded

C MST would remain the same

D Algorithm would stop early

💡 Hint

Consider edges sorted by weight and MST edges after step 3 in variable_tracker

Concept Snapshot

Kruskal's Algorithm builds MST by:
- Sorting edges by weight
- Adding smallest edge if no cycle forms
- Using cycle check (Union-Find or DFS)
- Stopping when all vertices connected
- Result is MST with minimum total weight

Full Transcript

Kruskal's algorithm starts by sorting all edges by their weight. Then it picks the smallest edge and checks if adding it creates a cycle in the growing MST. If no cycle forms, the edge is added. If a cycle would form, the edge is discarded. This process repeats until all vertices are connected or no edges remain. The algorithm ensures the MST has the smallest total weight by always choosing the smallest available edge that does not create a cycle.

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