Challenge 4

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.

Exercise 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)).

Show example 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))

Test yourself

What is Kruskal's first step?
- Visit nodes
- Grow tree
- Find cycle
- Sort edges
Show answer

Sort edges — The first step is to sort edges by weight.
Challenge 4: match the terms

(0,1,1)

First added
(1,2,2)

Second
(1,3,4)

Third
(0,2,3)

Skip
Total computation
```
total ____ w
```
Show answer
```
total += w
```

Next lesson: Advanced section exam

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies