Minimum Spanning Tree Kruskal's Algorithm in DSA C# - Time & Space Complexity

Time Complexity: Minimum Spanning Tree Kruskal's Algorithm

O(E log E)

Understanding Time Complexity

We want to understand how the time needed to find a minimum spanning tree using Kruskal's algorithm grows as the graph gets bigger.

Specifically, how does the number of edges and vertices affect the work done?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Kruskal's algorithm to find MST
List<Edge> edges = graph.GetAllEdges();
edges.Sort((a, b) => a.Weight.CompareTo(b.Weight));
DisjointSet ds = new DisjointSet(graph.VertexCount);
List<Edge> mst = new List<Edge>();
foreach (var edge in edges) {
  if (ds.Find(edge.U) != ds.Find(edge.V)) {
    ds.Union(edge.U, edge.V);
    mst.Add(edge);
  }
}

This code sorts all edges by weight, then adds edges to the MST if they connect different sets, using a disjoint set to avoid cycles.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Sorting all edges and iterating over them.
• How many times: Sorting takes about E log E steps for E edges; the loop runs once per edge (E times).
• Disjoint set operations (Find and Union) happen up to E times, each almost constant time.

How Execution Grows With Input

As the number of edges (E) and vertices (V) grow, the sorting step dominates the time.

Input Size (V, E)	Approx. Operations
V=10, E=20	About 20 * log 20 ≈ 86 steps
V=100, E=500	About 500 * log 500 ≈ 4483 steps
V=1000, E=5000	About 5000 * log 5000 ≈ 64850 steps

Pattern observation: The time grows a bit faster than the number of edges because of sorting, but the disjoint set operations add only a small extra cost.

Final Time Complexity

Time Complexity: O(E log E)

This means the time grows mostly with sorting the edges, which depends on the number of edges and grows a bit faster than just counting them.

Common Mistake

[X] Wrong: "The algorithm runs in O(V^2) because it checks all pairs of vertices."

[OK] Correct: Kruskal's algorithm works mainly with edges, not all vertex pairs. It sorts edges and uses efficient union-find, so the time depends on edges, not all vertex pairs.

Interview Connect

Understanding Kruskal's time complexity shows you how sorting and efficient data structures work together to solve graph problems quickly. This skill helps you explain and improve algorithms confidently.

Self-Check

"What if we used a simple list instead of a disjoint set for cycle detection? How would the time complexity change?"

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