Minimum Spanning Tree Kruskal's Algorithm in DSA Python - Build from Scratch

Minimum Spanning Tree using Kruskal's Algorithm

📖 Scenario: Imagine you are helping a city planner connect several neighborhoods with roads. Each road has a cost. You want to connect all neighborhoods with the least total cost without creating loops.

🎯 Goal: You will build a program that finds the minimum total cost to connect all neighborhoods using Kruskal's algorithm. This algorithm picks the cheapest roads first and avoids loops.

📋 What You'll Learn

Create a list of edges with exact weights and nodes

Create a parent list for union-find structure

Implement union-find functions to detect cycles

Use Kruskal's algorithm to select edges

Print the edges chosen and the total cost

💡 Why This Matters

🌍 Real World

City planners use minimum spanning trees to design road networks that connect all areas with minimum construction cost.

💼 Career

Understanding Kruskal's algorithm is important for software engineers working on network design, optimization, and graph-related problems.

1

Create the graph edges list

Create a list called edges with these exact tuples representing roads: (0, 1, 4), (0, 2, 3), (1, 2, 1), (1, 3, 2), (2, 3, 4), (3, 4, 2), (4, 5, 6)

DSA Python

# Create the list edges with the given tuples
# Your code here

Hint

Use a list of tuples where each tuple has two nodes and the cost between them.

2

Create the parent list for union-find

Create a list called parent with 6 elements where each element is its own index (0 to 5). This will help track connected neighborhoods.

DSA Python

edges = [(0, 1, 4), (0, 2, 3), (1, 2, 1), (1, 3, 2), (2, 3, 4), (3, 4, 2), (4, 5, 6)]
# Create the parent list with values 0 to 5
# Your code here

Hint

Each neighborhood starts as its own parent in the union-find structure.

3

Implement union-find functions and Kruskal's algorithm

Define a function find_parent(node) that returns the root parent of node using recursion and path compression. Define a function union(a, b) that connects two nodes if they have different parents. Then, sort edges by cost and use a loop to pick edges that connect different sets, adding them to mst list and summing their costs in total_cost.

DSA Python

edges = [(0, 1, 4), (0, 2, 3), (1, 2, 1), (1, 3, 2), (2, 3, 4), (3, 4, 2), (4, 5, 6)]
parent = [0, 1, 2, 3, 4, 5]
# Define find_parent and union functions
# Sort edges and build mst list with total_cost
# Your code here

Hint

Use recursion in find_parent to find the root. Use union to connect sets only if roots differ. Sort edges by cost before looping.

4

Print the MST edges and total cost

Print the list mst and then print the string Total cost: followed by the value of total_cost.

DSA Python

edges = [(0, 1, 4), (0, 2, 3), (1, 2, 1), (1, 3, 2), (2, 3, 4), (3, 4, 2), (4, 5, 6)]
parent = [0, 1, 2, 3, 4, 5]

def find_parent(node):
    if parent[node] != node:
        parent[node] = find_parent(parent[node])
    return parent[node]

def union(a, b):
    rootA = find_parent(a)
    rootB = find_parent(b)
    if rootA != rootB:
        parent[rootB] = rootA
        return True
    return False

edges.sort(key=lambda x: x[2])
mst = []
total_cost = 0
for u, v, cost in edges:
    if union(u, v):
        mst.append((u, v, cost))
        total_cost += cost
# Print mst and total_cost below
# Your code here

Hint

Print the mst list and then print the total cost with a label.

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