AlgoScope

Edge List

A flat list of (u, v, weight) triples, the natural input for Kruskal, which sorts it by weight.

Data structures, data structure, beginner
Kruskal's algorithm. Edges are considered from cheapest to dearest.43124265001122334455
Kruskal's algorithm. Edges are considered from cheapest to dearest.43124265001122334455

Minimum Spanning Tree: Kruskal, cheapest edges first

Start, step 1 of 9

Kruskal: sort the 8 edges by weight, 1-2 (1), 1-3 (2), 3-4 (2), 0-2 (3), 0-1 (4), 2-3 (4), 2-5 (5), 4-5 (6), and take each one unless its ends are already connected. Each vertex shows its component. Two vertices with the same number are already joined, so an edge between them would close a cycle.

Cost

Edge lookup
O(E)
Add edge
O(1)
Sort edges
O(E log E)
Space
O(E)

Taught by the same lesson

Minimum Spanning Tree covers these too, in the same run.