Summary - Kruskal

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.

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

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

Test yourself

What is the output of Kruskal?
- Edge list
- Node list
- Cycle count
- Total weight
Show answer

Total weight — Kruskal returns the total weight of the MST.
Total variable
```
total ____ w
```
Show answer
```
total += w
```
Summary - Kruskal: match the terms

init_edges

Edges
sort_edges

Sort
find

Root
kruskal

MST

Next lesson: Prim idea

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies