Graph Theory37 sections · 1633 units
Open in Course

Kruskal's Algorithm - Idea

(Sort edges, add greedily)

Kruskal's algorithm builds the MST by greedily adding the cheapest edge that does not create a cycle. Start with an empty set of edges. Sort all edges by weight. Add edges one by one, skipping any edge that would form a cycle.

The core concept: always pick the globally cheapest edge that keeps the forest acyclic. Eventually, you will connect all nodes. How do you detect cycles? That is where Union-Find comes in.