Workspace

Problem workspace

3 day streakD

Kruskal’s Algorithm

MediumGraphsSpanning trees

The challenge

Build a minimum spanning forest of an undirected weighted graph by choosing globally cheap edges while avoiding cycles.

List each undirected edge once. Use Union-Find to decide whether endpoints are already connected.

Example

The connected graph has minimum total weight 8. The B–F edge is accepted before A–B, which is then rejected as a cycle.

Use the walkthrough below to inspect the input and each state change.

See Kruskal, step by step

Follow the edges. Watch the state change.

Undirected · 6 vertices · 7 edgesA = 0, B = 1, …
Weighted graphUndirected graph with 6 vertices. Start with one component per vertex. Sort all edges by weight. Accept an edge only when its endpoints are in different components. The edge list and state table below provide the graph in text.4121831Aset 1Bset 2Cset 3Dset 4Eset 5Fset 6
CurrentVisited / acceptedUnvisitedLabels identify components or colors
Component representative
ABCDEF
ABCDEF
Step 01 / 9

Start with one component per vertex.

Sort all edges by weight. Accept an edge only when its endpoints are in different components.

edges.sort(key=weight)

Forest

Total weight: 06 component(s)
View input edges

A — B (4) · A — F (1) · F — B (2) · B — C (1) · F — E (8) · C — D (3) · D — E (1)

Put it into code

The cheapest edge connecting different components is safe to accept.

Vertices are numbered 0 to V − 1. C++ uses C++17 or later.

# Undirected edges are listed once as (u, v, weight).
class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.components = n

    def find(self, u):
        while u != self.parent[u]:
            self.parent[u] = self.parent[self.parent[u]]
            u = self.parent[u]
        return u

    def union(self, u, v):
        a, b = self.find(u), self.find(v)
        if a == b:
            return False
        if self.size[a] < self.size[b]:
            a, b = b, a
        self.parent[b] = a
        self.size[a] += self.size[b]
        self.components -= 1
        return True

def kruskal(n, edges):
    dsu = DSU(n)
    forest, total = [], 0
    for u, v, weight in sorted(edges, key=lambda e: e[2]):
        if dsu.union(u, v):
            forest.append((u, v, weight))
            total += weight
    return forest, total  # V - components accepted edges.

A good place to start

Explore a pattern

A little guidance

Start with a pattern, read through a problem, and mark it solved when the idea clicks. Save anything you want to revisit.

New tutorials are added one at a time. Your bookmarks and solved checkmarks stay in this browser.

Explore the roadmap