= Kruskal's algorithm worked example
{c}
Consider this original <connected graph> on <vertices> $A,B,C,D,E$. Its undirected <edges>, already in increasing weight order, are
$$
\begin{array}{c|rrrrrrr}
\text{edge}&AB&BC&AC&CD&DE&CE&BE\\\hline
\text{weight}&1&2&3&4&5&6&7.
\end{array}
$$
Here $AB$ means the unordered pair $\{A,B\}$; the weights are dimensionless costs. Accept $AB$ and $BC$, with total $3$. Reject $AC$: its endpoints already have the <graph path> $A,B,C$, so it would close the <graph cycle> $A,B,C,A$. Accept $CD$ and $DE$, reaching all five <vertices> with four <edges>. The resulting <minimum spanning tree> is
$$
T=\{AB,BC,CD,DE\},\qquad w(T)=1+2+4+5=12.
$$
Stop here: $CE$ and $BE$ need not be examined. If processing continued, both would be rejected because their endpoints are already in the same <connected component of a graph>.
\Image[/kruskal-chosen-and-rejected-edges.png]
{title=Five sorted <edge> decisions produce a <minimum spanning tree> of cost 12}
{description=Original five-<vertex> example. Green <edges> are accepted, the red dashed <edge> is rejected, and grey <edges> are unexamined. The third decision rejects $AC$ without changing the accepted <forest>.}
Taking the three cheapest <edges> $AB,BC,AC$ instead gives a <graph cycle> on $A,B,C$, leaving $D,E$ isolated: it is neither a <forest> nor a <spanning tree>. Even taking the four cheapest <edges> adds only $CD$ and leaves $E$ isolated. A cheap infeasible selection cannot compete with a <minimum spanning tree>. For this small <graph>, checking all $\binom{7}{4}=35$ four-<edge> subsets gives a direct certificate: among those that are <spanning trees>, exactly one has minimum cost $12$, namely $T$. The general <algorithm> avoids this exhaustive search.
Back to article page
