Minimum Spanning Tree Kruskal'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 Kruskal's Algorithm?

Kruskal's Algorithm builds the MST by sorting all edges by weight and adding the smallest edge to the MST if it doesn't form a cycle, repeating until all vertices are connected.

intermediate

Why do we use a Disjoint Set (Union-Find) data structure in Kruskal's Algorithm?

We use Disjoint Set to efficiently check if adding an edge creates a cycle by checking if two vertices belong to the same set, and to union sets when edges are added.

intermediate

What is the time complexity of Kruskal's Algorithm?

The time complexity is O(E log E) mainly due to sorting edges, where E is the number of edges. Union-Find operations are almost O(1) amortized.

intermediate

How does Kruskal's Algorithm ensure no cycles are formed?

By only adding edges that connect vertices from different sets in the Union-Find structure, it prevents cycles because edges connecting vertices in the same set would form a cycle.

What is the first step in Kruskal's Algorithm?

A Sort all edges by their weight

B Pick any vertex as the starting point

C Create adjacency list for the graph

D Remove the heaviest edge

Kruskal's Algorithm starts by sorting all edges in ascending order of their weights.

Which data structure helps detect cycles in Kruskal's Algorithm?

A Disjoint Set (Union-Find)

B Stack

C Queue

D Binary Search Tree

Disjoint Set (Union-Find) efficiently checks if two vertices belong to the same set to avoid cycles.

What happens if adding an edge connects two vertices in the same set?

A The algorithm restarts

B The edge is added to MST

C The sets are merged

D The edge is skipped to avoid cycle

Adding such an edge would create a cycle, so it is skipped.

What does Kruskal's Algorithm output?

A Shortest path between two vertices

B Minimum Spanning Tree

C Maximum flow in the graph

D All cycles in the graph

Kruskal's Algorithm outputs the Minimum Spanning Tree of the graph.

If a graph has V vertices and E edges, what is the maximum number of edges in its MST?

A V

B E

C V - 1

D E - 1

A MST always has exactly V - 1 edges, where V is the number of vertices.

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

Think about sorting edges and using sets to avoid cycles.

Describe how the Union-Find data structure helps in cycle detection during Kruskal's Algorithm.

Focus on sets and how they represent connected components.

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