Summary - Kruskal
- Algorithms course
- Advanced
- Lesson 40/56
- 4 min
Run Kruskal and print the MST weight in a mini task.
Summary - Kruskal
In this group you learned Kruskal, which finds the MST by sorting edges and adding those that form no cycle. Edge list, sorting and cycle check combine into the solution.
Now you will write a function that brings all pieces together. This summary unites the group's concepts in a single piece of code.
Practice mst_weight function
Write mst_weight(edges, n). find and union are given; sort edges, add cycle-free ones, return the total. Print 19 with print(mst_weight(init_edges(), 4)).
Starter code
def init_edges():
# Return edge list
return [(0, 1, 10), (0, 2, 6), (0, 3, 5), (1, 3, 15), (2, 3, 4)]
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_weight(edges, n):
# Find total MST weightSample solution
def init_edges():
# Return edge list
return [(0, 1, 10), (0, 2, 6), (0, 3, 5), (1, 3, 15), (2, 3, 4)]
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_weight(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_weight(init_edges(), 4))Expected output
19
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 What is the output of Kruskal?
- Edge list
- Node list
- Cycle count
- Total weight Correct answer
Explanation: Kruskal returns the total weight of the MST.
2 Total variable
Question
total ____ w
Answer
total += wExplanation: += is right.
3 Summary - Kruskal: match the terms
| Term | Meaning |
|---|---|
init_edges |
Edges |
sort_edges |
Sort |
find |
Root |
kruskal |
MST |