Cycle check
- Algorithms course
- Advanced
- Lesson 39/56
- 4 min
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.
Practice 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)).
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 kruskal(edges, n):
# Find 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 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))Expected output
19
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Cycle check: match the terms
| Term | Meaning |
|---|---|
find |
Find root |
union |
Merge sets |
parent |
Parent array |
cycle |
Skip |
2 What is the total weight of the MST in the example graph?
- 15
- 20
- 19 Correct answer
- 25
Explanation: 4+5+10=19.
3 Cycle condition
if find(parent, u) ____ find(parent, v):if find(parent, u) != find(parent, v):Explanation: != is right.