Minimum Spanning Tree Kruskal's Algorithm in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Kruskal's MST edges

What is the output list of edges included in the MST after running Kruskal's algorithm on the given graph?

DSA Python

edges = [(1, 2, 4), (1, 3, 1), (2, 3, 3), (2, 4, 2), (3, 4, 5)]
parent = {}
rank = {}

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:
        if rank[rootA] < rank[rootB]:
            parent[rootA] = rootB
        elif rank[rootA] > rank[rootB]:
            parent[rootB] = rootA
        else:
            parent[rootB] = rootA
            rank[rootA] += 1
        return True
    return False

nodes = {1, 2, 3, 4}
for node in nodes:
    parent[node] = node
    rank[node] = 0

edges.sort(key=lambda x: x[2])
mst = []
for u, v, w in edges:
    if union(u, v):
        mst.append((u, v, w))
print(mst)

A [(1, 2, 4), (2, 3, 3), (2, 4, 2)]

B [(1, 3, 1), (1, 2, 4), (2, 4, 2)]

C [(1, 3, 1), (2, 4, 2), (2, 3, 3)]

D [(1, 3, 1), (2, 3, 3), (3, 4, 5)]

💡 Hint

Sort edges by weight and pick edges that don't form a cycle.

Kruskal's algorithm sorts edges by weight and adds edges that connect different sets. The MST edges are those with weights 1, 2, and 3 connecting nodes (1,3), (2,4), and (2,3).

🧠 Conceptual

intermediate

Number of edges in MST for a connected graph

For a connected graph with 7 nodes, how many edges will the Minimum Spanning Tree (MST) contain?

A 5

B 7

C 8

D 6

💡 Hint

MST connects all nodes with minimum edges to avoid cycles.

An MST for a connected graph with n nodes always has n-1 edges.

🔧 Debug

advanced

Identify the error in union-find implementation

What error will this union-find code cause when running Kruskal's algorithm?

DSA Python

def find(x):
    if parent[x] != x:
        return find(parent[x])
    return x

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

parent = {1:1, 2:2, 3:3}
rank = {1:0, 2:0, 3:0}

edges = [(1, 2, 1), (2, 3, 2)]

for u, v, w in edges:
    union(u, v)

print(parent)

A No error, but union does not update rank causing inefficient find

B No error, prints {1: 1, 2: 1, 3: 1}

C KeyError because rank is unused

D RecursionError due to missing path compression

💡 Hint

Check if rank is used to balance trees in union.

The code runs without error but does not use rank to balance trees, which can cause inefficient find operations.

❓ Predict Output

advanced

Output of MST total weight calculation

What is the total weight of the MST after running Kruskal's algorithm on this graph?

DSA Python

edges = [(1, 2, 10), (1, 3, 6), (1, 4, 5), (2, 4, 15), (3, 4, 4)]
parent = {}
rank = {}

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:
        if rank[rootA] < rank[rootB]:
            parent[rootA] = rootB
        elif rank[rootA] > rank[rootB]:
            parent[rootB] = rootA
        else:
            parent[rootB] = rootA
            rank[rootA] += 1
        return True
    return False

nodes = {1, 2, 3, 4}
for node in nodes:
    parent[node] = node
    rank[node] = 0

edges.sort(key=lambda x: x[2])
mst_weight = 0
for u, v, w in edges:
    if union(u, v):
        mst_weight += w
print(mst_weight)

A 19

B 15

C 20

D 25

💡 Hint

Sum weights of edges chosen by Kruskal's algorithm.

Edges chosen are (3,4,4), (1,4,5), and (1,2,10) totaling 19.

🧠 Conceptual

expert

Why does Kruskal's algorithm use union-find?

What is the main reason Kruskal's algorithm uses the union-find data structure?

A To store the graph nodes in order

B To efficiently check if adding an edge creates a cycle

C To sort edges by weight quickly

D To find the shortest path between two nodes

💡 Hint

Think about cycle detection during edge addition.

Union-find helps quickly determine if two nodes belong to the same connected component, preventing cycles.

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