Kruskal's Algorithm

External

• https://www.coursera.org/learn/algorithms-greedy/lecture/PLdBf/kruskals-mst-algorithm

Internal

• The Minimum Spanning Tree Problem
• Greedy Algorithms
• Graph Concepts
• Union-Find

Overview

Kruskal's algorithms is a greedy algorithm that computes the minimum cost spanning tree for an undirected connected graph. It has a different approach than Prim's algorithm, in that it does not grow the connected explored territory one node at a time, but it grows the trees in parallel with a lot of simultaneous little pieces, unconnected at first, which eventually merge into the minimum cost spanning tree. It does that by sorting the edges in the ascending order of their cost, and picking edges in that order, one by one, careful not to create cycles.

Correctness Proof

https://www.coursera.org/learn/algorithms-greedy/lecture/U3ukN/correctness-of-kruskals-algorithm