43224315423ABCDEFGH
AlgoPlus//graph / kruskal
Read the theory

Kruskal's MST

Sort edges, greedily accept those that don't form a cycle.

Stability
—
In-Place
—
Space Complexity
—
Avg Time
—
Legend
Current
Frontier
Visited
Path / MST
AI Tutor Workspace
—
In a nutshell
Kruskal's algorithm also builds a minimum spanning tree, but edge-first. Sort every edge from cheapest to most expensive and add them in that order, skipping any edge that would join two vertices already connected (which would make a cycle). A union-find structure checks that instantly. The accepted edges merge separate pieces into one tree of least total cost.
Ready
Press play to begin the cinematic walkthrough.
Sort all edges; greedily accept the cheapest edge that doesn't form a cycle, using union-find.
Key terms
Go deeper in the lesson
Read the full theory, intuition & complexity for Kruskal's MST.
Code Simulator
▼
1
def kruskal(graph):
2
    mst = []
3
    edges = sorted(graph.edges, key=lambda e: e.w)
4
    uf = UnionFind(graph.nodes)
5
    for u, v, w in edges:
6
        if uf.union(u, v):  # No cycle -> Accept
7
            mst.append((u, v, w))
Why Python? · Readable first, fast second

Dynamically typed and interpreted — every comparison and swap is dispatched by the interpreter at run time, so tight loops run roughly 10–100× slower than compiled C/C++. Unbeatable for learning the idea with the least code; not what you reach for when the inner loop is the bottleneck.