Minimum Spanning Tree Kruskal's Algorithm in DSA Python

Mental Model

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

Analogy: Imagine building roads between cities by always choosing the cheapest road that doesn't create a circle, so all cities connect with minimum cost.

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

Edges with weights:
(1-2:2), (1-3:3), (2-4:1), (3-4:4)

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 minimize total cost.

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

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

Why: No cycle formed, so we add the smallest edge.

Step 3: Pick edge (1-2:2), add it 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: Connecting new node without cycle.

Step 4: Pick edge (1-3:3), add it 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: All nodes connected, MST complete.

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

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

Why: Adding this edge would create a loop, so we ignore it.

Result:

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

Annotated Code

DSA Python

class DisjointSet:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # path compression
        return self.parent[x]

    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX == rootY:
            return False  # already connected
        if self.rank[rootX] < self.rank[rootY]:
            self.parent[rootX] = rootY
        elif self.rank[rootX] > self.rank[rootY]:
            self.parent[rootY] = rootX
        else:
            self.parent[rootY] = rootX
            self.rank[rootX] += 1
        return True

def kruskal(n, edges):
    ds = DisjointSet(n)
    mst = []
    edges.sort(key=lambda x: x[2])  # sort by weight
    for u, v, w in edges:
        if ds.union(u, v):  # if union is successful, no cycle
            mst.append((u, v, w))
    return mst

# Nodes are 0-based indexed internally
nodes = 4
edges = [
    (0, 1, 2),  # edge 1-2 weight 2
    (0, 2, 3),  # edge 1-3 weight 3
    (1, 3, 1),  # edge 2-4 weight 1
    (2, 3, 4)   # edge 3-4 weight 4
]
mst = kruskal(nodes, edges)
for u, v, w in mst:
    print(f"Edge {u+1}-{v+1} with weight {w}")

edges.sort(key=lambda x: x[2]) # sort by weight

Sort edges from smallest to largest weight to pick cheapest first

if ds.union(u, v): # if union is successful, no cycle

Add edge only if it connects two different sets to avoid cycles

def find(self, x): if self.parent[x] != x: self.parent[x] = self.find(self.parent[x]) # path compression return self.parent[x]

Find root parent of node with path compression for efficiency

def union(self, x, y): rootX = self.find(x) rootY = self.find(y) if rootX == rootY: return False # already connected if self.rank[rootX] < self.rank[rootY]: self.parent[rootX] = rootY elif self.rank[rootX] > self.rank[rootY]: self.parent[rootY] = rootX else: self.parent[rootY] = rootX self.rank[rootX] += 1 return True

Union two sets by rank to keep tree shallow and return if union happened

Output

Edge 2-4 with weight 1

Edge 1-2 with weight 2

Edge 1-3 with weight 3

Complexity Analysis

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

Space: O(V) for the disjoint set parent and rank arrays

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

Edge Cases

Empty graph (no edges)

Returns empty MST since no edges to connect nodes

DSA Python

for u, v, w in edges:

Graph with one node

Returns empty MST since no edges needed

DSA Python

for u, v, w in edges:

Graph with multiple edges having same weight

Algorithm still picks edges in sorted order and avoids cycles correctly

DSA Python

if ds.union(u, v):

When to Use This Pattern

When you need to connect all points with minimum total cost and avoid loops, reach for Kruskal's MST using sorting and union-find to efficiently build the solution.

Common Mistakes

Mistake: Not using union-find to detect cycles, causing incorrect MST with loops
Fix: Use union-find data structure to check if adding an edge creates a cycle before adding it

Mistake: Sorting edges incorrectly or not sorting at all
Fix: Always sort edges by weight ascending before processing

Summary

Builds a minimum spanning tree by adding smallest edges without cycles.

Use when you want the cheapest way to connect all nodes in a graph.

Sort edges by weight and use 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 find the shortest path between two nodes

B. To find the minimum spanning tree of a graph

C. To detect cycles in a graph

D. To find the maximum flow in a network

Solution

1. Step 1: Understand Kruskal's algorithm purpose

   Kruskal's algorithm is designed to find a subset of edges that connects all vertices with the minimum total edge weight.

2. Step 2: Compare with other graph problems

   Shortest path, cycle detection, and max flow are different problems with different algorithms.

3. Final Answer:

   To find the minimum spanning tree of a graph -> Option B

4. Quick Check:

   Kruskal's algorithm = Minimum Spanning Tree [OK]

Hint: Kruskal always builds minimum spanning tree by edge weights [OK]

Common Mistakes:

• Confusing MST with shortest path
• Thinking it detects cycles only
• Mixing with max flow problems

2. Which of the following is the correct syntax to sort edges by weight in Python for Kruskal's algorithm?

easy

A. edges.sort(key=lambda x: x[2])

B. edges.sort(key=lambda x: x[1])

C. edges.sort()

D. edges.sort(key=lambda x: x[0])

Solution

1. Step 1: Identify edge structure

   Edges are usually stored as tuples (node1, node2, weight), so weight is at index 2.

2. Step 2: Use sort with key on weight

   Sorting by weight means sorting by the third element, so key=lambda x: x[2] is correct.

3. Final Answer:

   edges.sort(key=lambda x: x[2]) -> Option A

4. Quick Check:

   Sort edges by weight = key=lambda x: x[2] [OK]

Hint: Weight is usually third element in edge tuple [OK]

Common Mistakes:

• Sorting by wrong tuple index
• Using sort() without key when edges are tuples
• Confusing node indices with weight index

3. What is the output of the following code snippet that applies Kruskal's algorithm on a graph with edges [(0, 1, 10), (0, 2, 6), (0, 3, 5), (1, 3, 15), (2, 3, 4)]?

edges = [(0, 1, 10), (0, 2, 6), (0, 3, 5), (1, 3, 15), (2, 3, 4)]
edges.sort(key=lambda x: x[2])
parent = list(range(4))
def find(x):
    while parent[x] != x:
        x = parent[x]
    return x
def union(a, b):
    rootA = find(a)
    rootB = find(b)
    if rootA != rootB:
        parent[rootB] = rootA
        return True
    return False
mst = []
for u, v, w in edges:
    if union(u, v):
        mst.append((u, v, w))
print(mst)

medium

A. [(0, 2, 6), (0, 3, 5), (2, 3, 4)]

B. [(0, 3, 5), (2, 3, 4), (1, 3, 15)]

C. [(0, 1, 10), (0, 2, 6), (1, 3, 15)]

D. [(2, 3, 4), (0, 3, 5), (0, 1, 10)]

Solution

1. Step 1: Sort edges by weight

   Sorted edges: (2,3,4), (0,3,5), (0,2,6), (0,1,10), (1,3,15)

2. Step 2: Apply union-find to select edges without cycles

   Pick (2,3,4), union success; pick (0,3,5), union success; pick (0,2,6), union fails (cycle); pick (0,1,10), union success; stop as MST has 3 edges for 4 nodes.

3. Final Answer:

   [(2, 3, 4), (0, 3, 5), (0, 1, 10)] -> Option D

4. Quick Check:

   Edges chosen = minimum weights without cycles [OK]

Hint: Sort edges, pick smallest without cycle until MST complete [OK]

Common Mistakes:

• Not sorting edges correctly
• Adding edges that form cycles
• Stopping too early or too late

4. Identify the bug in this Kruskal's algorithm snippet and select the fix:

edges = [(0,1,1), (1,2,2), (0,2,3)]
parent = [0, 1, 2]
def find(x):
    if parent[x] == x:
        return x
    return find(parent[x])
def union(a, b):
    rootA = find(a)
    rootB = find(b)
    if rootA != rootB:
        parent[a] = b  # Bug here
        return True
    return False
mst = []
for u,v,w in sorted(edges, key=lambda x: x[2]):
    if union(u,v):
        mst.append((u,v,w))
print(mst)

medium

A. Change 'parent[a] = b' to 'parent[rootB] = rootA'

B. Change 'parent[a] = b' to 'parent[rootA] = rootB'

C. Change 'parent[a] = b' to 'parent[b] = a'

D. No bug, code is correct

Solution

1. Step 1: Analyze union function

   Union should link roots of sets, not original nodes directly.

2. Step 2: Fix parent assignment

   Assign parent of rootB to rootA to merge sets correctly: 'parent[rootB] = rootA'.

3. Final Answer:

   Change 'parent[a] = b' to 'parent[rootB] = rootA' -> Option A

4. Quick Check:

   Union sets by root parents, not nodes [OK]

Hint: Always union by root parents, not direct nodes [OK]

Common Mistakes:

• Assigning parent of node instead of root
• Confusing rootA and rootB in assignment
• Skipping path compression in find

5. Given a graph with vertices 0 to 4 and edges [(0,1,2), (0,3,6), (1,2,3), (1,3,8), (1,4,5), (2,4,7), (3,4,9)], what is the total weight of the minimum spanning tree found by Kruskal's algorithm?

hard

A. 19

B. 20

C. 16

D. 18

Solution

1. Step 1: Sort edges by weight

   Sorted edges: (0,1,2), (1,2,3), (1,4,5), (0,3,6), (2,4,7), (1,3,8), (3,4,9)

2. Step 2: Select edges without cycles until all vertices connected

   Pick (0,1,2), (1,2,3), (1,4,5), (0,3,6). Total weight = 2+3+5+6 = 16. But check if (2,4,7) creates cycle: yes, skip. (1,3,8) and (3,4,9) create cycles, skip.

3. Step 3: Verify MST completeness

   All 5 vertices connected with 4 edges, total weight 16.

4. Final Answer:

   16 -> Option C

5. Quick Check:

   MST total weight = sum of chosen edges [OK]

Hint: Sum smallest edges connecting all nodes without cycles [OK]

Common Mistakes:

• Including edges that form cycles
• Missing edges needed to connect all vertices
• Adding heavier edges unnecessarily