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.

Correctness Proof

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