Edge sorting

Sort edges by weight and add greedily.

Edge sorting

Kruskal's first step is to sort edges by weight in ascending order. This way, the lowest-weight edges are tried first.

Sorting is the basis of the greedy approach. At each step, the lowest-weight available edge is picked.

Greedy choice

We walk through the sorted edge list and add each edge to the MST if it does not form a cycle. Union-find is used for cycle detection.

This greedy approach guarantees the MST is optimal. Each step makes the locally best choice.

Exercise sort_edges function

Write sort_edges(edges). Sort edges by weight in ascending order, return them. Print with print(sort_edges(init_edges())).

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 sort_edges(edges):
    # Sort edges by weight
    return sorted(edges, key=lambda e: e[2])
print(sort_edges(init_edges()))

Test yourself

Sort key

sorted(edges, key=lambda e: ____)

Show answer

sorted(edges, key=lambda e: e[2])

In which direction is the sorting done?
- Descending
- Ascending
- Random
- By node index
Show answer

Ascending — Edges are sorted in ascending order.
Edge sorting: match the terms

sorted

Sort
lambda

Key
e[2]

Weight
edges

Source

Next lesson: Cycle check

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies