Kruskal’s Algorithm
Kruskal’s algorithm finds a safe edge to add to the growing forest by finding, of all the edges that connect any two trees in the forest, an edge with the lowest weight.
- Thus, Kruskal is an example of greedy algorithm.
- Disjoint set data structure to maintain the forest.
- Steps
- Create trees, one for each vertex.
- Sort the edges in increasing order
- Pick the smallest edge
- If the two ends are not in the same set (so that it’s safe and do not introduce cycle), add the edge to the forest.
- Continue.