Minimum spanning tree

Find a minimum spanning tree of a graph.

Minimum spanning tree

In a weighted graph, the tree connecting all nodes with the smallest total weight is called the minimum spanning tree (MST). A tree with n nodes has n-1 edges.

Kruskal's algorithm sorts edges by weight and adds those that do not form a cycle, building the MST.

Edge list

Kruskal works with an edge list. Each edge is a (u, v, w) triple: from u to v with weight w. The graph is undirected.

We will find the MST in an example graph with five edges. Edges are defined in raw form before sorting.

Exercise init_edges function

Write init_edges(). Return the edge list. Print it with print(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)]
print(init_edges())

Test yourself

How many edges does an MST with 4 nodes have?
- 3
- 2
- 4
- 5
Show answer

3 — n-1 = 4-1 = 3 edges.

Smallest edge

min_edge = (____, 3, 4)

Show answer

min_edge = (2, 3, 4)

Minimum spanning tree: match the terms

(2,3,4)

Smallest
(0,3,5)

Second
(0,1,10)

Fourth
(1,3,15)

Largest

Next lesson: Edge sorting

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies