Kruskal's Algorithm

Kruskal's Algorithm
Runtime	Sort + E cycle? + (V - 1) adding-edge
Class	Minimum Spanning Tree, Greedy Algorithm

Approach: Greedy

The approach is to try to add the smallest edges as long as they do not create a cycle; add an edge to the tree that is minimum across the cut of $T$ vs. $V-T$

Given the MST of $V_{n-m}=v_{1},v_{2},\ldots ,v_{n-m}$, the MST of $V$ should be that of $V_{n-1}$ plus the edge that connects to $v_{n}$ that is the shortest.

$OPT(n)=OPT(n-1)+min((v_{i},v_{n})\in E)$

Analysis

Sort edges + E (cycle?) + (V - 1) adding edge

Sorting takes E log E

For weighted disjoint set, checking cycle takes log V, and adding edge takes log V

For fast-find, where all members have the same ID, fast-set-id needs O(1) and union needs O(n)