Why Minimum Spanning Tree Kruskal's Algorithm in DSA Python?

The Big Idea

What if you could connect everything using the least material without missing any connection?

The Scenario

Imagine you want to connect several houses in a neighborhood with roads. You want to use the least amount of road material possible, but still make sure every house can reach every other house.

The Problem

Trying to draw all possible roads and then picking the shortest ones by hand is slow and confusing. You might miss some connections or build extra roads that waste materials and money.

The Solution

Kruskal's Algorithm helps by sorting all possible roads by length and then picking the shortest roads one by one, making sure no loops form. This way, it quickly finds the cheapest way to connect all houses.

Before vs After

✗ Before

edges = [('A', 'B', 5), ('B', 'C', 3), ('A', 'C', 4)]
# Manually check all combinations to find minimum roads

✓ After

edges.sort(key=lambda x: x[2])
for edge in edges:
    if not creates_cycle(edge):
        add_edge(edge)

What It Enables

This algorithm makes it easy to build the cheapest network connecting all points without wasting resources.

Real Life Example

Internet companies use Kruskal's Algorithm to lay cables connecting cities with the least cost while ensuring all cities are linked.

Key Takeaways

Manual road planning is slow and error-prone.

Kruskal's Algorithm sorts edges and picks the shortest without loops.

It finds the cheapest way to connect all points efficiently.

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