Greedy algorithms build up a solution piece by piece, always choosing the next piece that offers the most obvious benefit. Although such an approach can be disastrous for some computational tasks, there are many for which it is optimal. An example is that of minimum spanning trees.
<aside> 💡 A minimum spanning tree is a subset of the edges of a connected, undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight.
</aside>
Removing a cycle edge cannot disconnect a graph.
The solution must be connected and acyclic: this is the definition of a tree.
A tree on $n$ nodes has $n-1$ edges.
This can be seen by building the tree one edge at a time, starting from an empty graph. Initially, each of the $n$ nodes is disconnected. As edges are added, the connected components (initially nodes by themselves) merge. Each edge units two different components, and exactly $n-1$ edges are added in the fully formed tree. The converse is also true.
Any connected, undirected graph $G = (V,E)$ with $|E|=|V|-1$ is a tree.
To prove this, we just need to show that $G$ is acyclic. While the graph contains a cycle, remove on edge from this cycle. The process terminates on $G'=(V,E')$, $E'\subseteq E$, which is acyclic, and by property 1, connected. Therefore, $G'$ is a tree, whereupon property 2 proves $|E|=|V|-1$, and since $E'=E$, no edges were removed, proving $G$ was acyclic to start with.
An undirected graph is a tree iff there is a unique path between any pair of nodes.
In a tree, any two nodes can only have one path between them, otherwise the union of these paths form a cycle. If a graph has a path between any two nodes, it is connected. If these paths are unique, then the graph is acyclic.
In the process of building an MST, if we have already chosen some edges, how do we decide what to add next?
<aside> 💡 The cut property states that given edges $X$ which are part of an MST $G = (V, E)$, we can pick any subset of nodes $S$ for which $X$ does not cross between $S$ and $V-S$, and let $e$ be the lightest edge across the partition, then $X\cup \{e\}$ is part of some MST.
</aside>
A cut is any partition of the vertices into two groups $S$, and $V-S$. This property implies it is always safe to add the lightest edge across any cut, provided $X$ does not already have an edge across the cut.
Kruskal's MST algorithm starts with the empty graph, then repeatedly selects the next lightest edge from $E$ that doesn't produce a cycle. It is a greedy algorithm as other than taking care to avoid cycles, it always picks the cheapest edge available.
At any given moment, the edges already chosen form a partial solution, a collection of connected components each with a tree structure. The next edge $e$ to be added connects two components $T_1$ and $T_2$. Since $e$ is the lightest edge that will not produce a cycle, it is certain to be the lightest edge between $T_1$ and $V-T_1$, satisfying the cut property.
At each stage, the algorithm chooses an edge to add to its current partial solution, testing each candidate edge $(u, v)$ to see whether $u$ and $v$ lie in different components to ensure acyclicity. Once an edge is chosen, the corresponding components need to be merged. To support this operation, we will model the algorithm's state using a collection of disjoint sets, each of which contains nodes of a particular component.
Initially, each node is a component by itself. We repeatedly test pairs if they belong to the same set. And we call union to merge two sets.