Minimum Spanning Tree Kruskal's Algorithm in DSA Python - Execution Trace

Concept Flow - Minimum Spanning Tree Kruskal's Algorithm

Start with all edges sorted by weight

↓

Pick smallest edge

↓

Check if adding edge forms cycle?

↓

Add edge to MST

↓

More edges?

No→Done

Yes↓

Pick next smallest edge

Kruskal's algorithm sorts edges by weight and adds the smallest edge that does not create a cycle until all vertices are connected.

Execution Sample

DSA Python

edges = [(1, 2, 1), (1, 3, 3), (2, 3, 2)]
edges.sort(key=lambda x: x[2])
parent = {1:1, 2:2, 3:3}

# Pick edges in order and union sets if no cycle

Sort edges by weight and add them to MST if they connect different sets.

Execution Table

Step	Operation	Edge Considered	Cycle Check Result	Action	MST Edges	Parent Sets	Visual MST State
1	Sort edges	N/A	N/A	Edges sorted by weight	[]	{1:1, 2:2, 3:3}	Empty MST
2	Pick edge	(1, 2, 1)	No cycle	Add edge to MST	[(1, 2, 1)]	{1:1, 2:1, 3:3}	1--1--2
3	Pick edge	(2, 3, 2)	No cycle	Add edge to MST	[(1, 2, 1), (2, 3, 2)]	{1:1, 2:1, 3:1}	1--1--2--2--3
4	Pick edge	(1, 3, 3)	Cycle detected	Skip edge	[(1, 2, 1), (2, 3, 2)]	{1:1, 2:1, 3:1}	1--1--2--2--3
5	Check edges left	No more edges	N/A	Stop	[(1, 2, 1), (2, 3, 2)]	{1:1, 2:1, 3:1}	Final MST

💡 All edges processed or skipped; MST connects all vertices without cycles.

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	Final
MST Edges	[]	[(1, 2, 1)]	[(1, 2, 1), (2, 3, 2)]	[(1, 2, 1), (2, 3, 2)]	[(1, 2, 1), (2, 3, 2)]
Parent Sets	{1:1, 2:2, 3:3}	{1:1, 2:1, 3:3}	{1:1, 2:1, 3:1}	{1:1, 2:1, 3:1}	{1:1, 2:1, 3:1}

Key Moments - 3 Insights

Why do we skip the edge (1, 3, 3) even though it connects two vertices?

Because adding edge (1, 3, 3) would create a cycle as vertices 1 and 3 are already connected through edges (1, 2, 1) and (2, 3, 2). This is shown in step 4 of the execution_table where cycle detection prevents adding this edge.

How does the parent set help in detecting cycles?

The parent set tracks which group each vertex belongs to. If two vertices of an edge have the same parent, adding that edge creates a cycle. This is why in step 4, both vertices 1 and 3 have the same parent 1, so the edge is skipped.

What happens to the MST when we add an edge?

When an edge is added, it connects two previously separate sets. The parent of one set is updated to the parent of the other, merging them. This is visible in steps 2 and 3 where parent sets change and MST edges grow.

Visual Quiz - 3 Questions

Look at the execution_table at step 3. What is the MST Edges list?

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

B [(1, 3, 3)]

C [(1, 2, 1)]

D []

💡 Hint

Check the MST Edges column at step 3 in the execution_table.

At which step does the algorithm detect a cycle and skip an edge?

A Step 2

B Step 4

C Step 3

D Step 5

💡 Hint

Look for 'Cycle detected' in the Cycle Check Result column in the execution_table.

If the edge (1, 3, 3) had weight 0.5 instead of 3, what would happen in the execution_table?

A It would be added last

B It would still be skipped

C It would be added first to MST

D Algorithm would stop early

💡 Hint

Edges are sorted by weight; smaller weights are considered first as shown in step 1.

Concept Snapshot

Kruskal's Algorithm:
- Sort all edges by weight
- Pick smallest edge that doesn't form a cycle
- Use parent sets to detect cycles
- Repeat until MST connects all vertices
- MST has (V-1) edges for V vertices

Full Transcript

Kruskal's algorithm builds a minimum spanning tree by sorting edges by weight and adding them one by one if they don't create a cycle. It uses a parent set to track connected components and avoid cycles. The process stops when all vertices are connected. This example shows edges sorted, cycle checks, and MST updates step-by-step.

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