Cycle check

Skip an edge if it would form a cycle.

Cycle check

Before adding an edge, we check whether its endpoints are in the same set. If so, the edge would form a cycle and is skipped.

This check is done with the union-find data structure. Each node starts as its own set; sets merge as edges are added.

Total weight

The weight of each added edge is added to the total. When n-1 edges are added, the MST is complete and the total weight is returned.

Kruskal's output is a single number: the total weight of the MST. This is the lowest cost to form the tree.

Exercise kruskal function

Write kruskal(edges, n). find and union are given; sort edges, add those that do not form cycles, return the total. Print 19 with print(kruskal(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 kruskal(edges, n):
    # Find 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(kruskal(init_edges(), 4))

Test yourself

Cycle check: match the terms

find

Find root
union

Merge sets
parent

Parent array
cycle

Skip
What is the total weight of the MST in the example graph?
- 15
- 20
- 19
- 25
Show answer

19 — 4+5+10=19.

Cycle condition

if find(parent, u) ____ find(parent, v):

Show answer

if find(parent, u) != find(parent, v):

Next lesson: Summary - Kruskal

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies