Challenge 4
- Algorithms course
- Advanced
- Lesson 56/56
- 4 min
Print the MST weight with Kruskal.
Challenge 4: Kruskal
In this challenge you will apply Kruskal's algorithm. Sort edges and add those that form no cycle to find the MST total weight.
Edges: [(0, 1, 1), (1, 2, 2), (0, 2, 3), (1, 3, 4), (2, 3, 5)]. The MST weight is 7.
Practice mst_total function
Write mst_total(edges, n). find and union are given; sort edges, add cycle-free ones, return the total. Print 7 with print(mst_total([(0, 1, 1), (1, 2, 2), (0, 2, 3), (1, 3, 4), (2, 3, 5)], 4)).
Starter code
def find(parent, x):
while parent[x] != x:
x = parent[x]
return x
def union(parent, x, y):
px, py = find(parent, x), find(parent, y)
if px != py:
parent[px] = py
def mst_total(edges, n):
# Find total MST weightSample solution
def find(parent, x):
while parent[x] != x:
x = parent[x]
return x
def union(parent, x, y):
px, py = find(parent, x), find(parent, y)
if px != py:
parent[px] = py
def mst_total(edges, n):
# Find total MST weight
edges = sorted(edges, key=lambda e: e[2])
parent = list(range(n))
total = 0
for u, v, w in edges:
if find(parent, u) != find(parent, v):
union(parent, u, v)
total += w
return total
print(mst_total([(0, 1, 1), (1, 2, 2), (0, 2, 3), (1, 3, 4), (2, 3, 5)], 4))Expected output
7
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 What is Kruskal's first step?
- Visit nodes
- Grow tree
- Find cycle
- Sort edges Correct answer
Explanation: The first step is to sort edges by weight.
2 Challenge 4: match the terms
| Term | Meaning |
|---|---|
(0,1,1) |
First added |
(1,2,2) |
Second |
(1,3,4) |
Third |
(0,2,3) |
Skip |
3 Total computation
Question
total ____ w
Answer
total += wExplanation: += is right.