AlgoScope

Kruskal

Sort the edges by weight and take each one that joins two different components, which union-find answers.

Minimum spanning tree, algorithm, intermediate
Edge 1 to 2 weight 1 is taken.43124265001222334455
Edge 1 to 2 weight 1 is taken.43124265001222334455

Minimum Spanning Tree: Kruskal, cheapest edges first

Decision, step 2 of 9

Edge 1-2, weight 1. 1 is in component 1 and 2 in component 2, different, so take it: they merge and the total is 1.

Cost

Best
O(E log E)
Average
O(E log E)
Worst
O(E log E)
Space
O(V)

Leads to

Topics that need this one first.

Taught by the same lesson

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