Kruskal's Algorithm

A way of finding a MST by sorting all edges by their weights and adding them to our constructed MST as long as it doesn’t form a cycle with previous edges

Topics

• Union Find Problem

Pseudocode

• Sort all edges by their weights
• For edge $e_i$ in list of sorted edges
  • Add $e_i$ to the MST
  • If $e_i$ forms a cycle with the MST (this can be done in $O(\log V)$ time by applying the union find problem. Consider each connected tree to be a set and if we find the nodes forming $e_i$ belong to the same set, then a cycle is formed. If not, there is no cycle, and we then union the two connected trees)
    • Discard it
  • $i$++

$O(E\log V)=O(E\log E)$

• $E$ is the number of edges
• $V$ is the number of vertices
• The equality occurs because if $E=V$ or $E=V^2$, then the log makes the constant go away