= Kruskal safe edge
{c}
An <edge> is safe for the current accepted <forest> $F$ if some <minimum spanning tree> contains both $F$ and that <edge>. The <loop invariant> is that some <minimum spanning tree> contains every accepted <edge>. It holds initially for the empty <edge> set. Suppose the next accepted <edge> $e$ joins a current <connected component of a graph> $S$ to its complement. No earlier rejected <edge> crosses this <cut of a graph>: once its endpoints are in one <connected component of a graph>, subsequent merges never separate them. Thus $e$ is a lightest <edge> across that <cut of a graph>.
For the short exchange argument, take a <minimum spanning tree> $T$ containing $F$. If $e$ is absent, adding it creates a <fundamental cycle>. This <graph cycle> contains another <edge> $f$ crossing the same <cut of a graph>. No <edge> of $F$ crosses the <cut of a graph>, so $f$ is not in $F$. Replace $f$ by $e$: the result is a <spanning tree> containing $F$ and $e$, with no greater total weight because $w(e)\leq w(f)$. It is therefore also a <minimum spanning tree>. This is the <minimum spanning tree cut property> in the form needed for tied weights.
In the example, $CD$ is safe after rejecting $AC$: the current <connected component of a graph> $\{A,B,C\}$ has crossing <edges> $CD,CE,BE$ of weights $4,6,7$. Its cheapest connection is $CD$. The rejected $AC$ is also the unique heaviest <edge> of the <graph cycle> $A,B,C,A$, so the <minimum spanning tree cycle property> excludes it from every optimum.
Negative and zero <edge> weights are allowed: the comparisons and exchange argument still apply. Ties can give several <minimum spanning trees>, though they need not; any order among equal-weight <edges> remains valid. Distinct <edge> weights guarantee a unique <minimum spanning tree>. To see why, take the lightest <edge> $e$ belonging to exactly one of two proposed optima, say $T$. Deleting $e$ from $T$ gives a <cut of a graph>; the other optimum has a <graph path> across it, containing an <edge> $f$ absent from $T$. Hence $w(e)<w(f)$, and replacing $f$ by $e$ improves that other optimum, a contradiction. For disconnected input, process all <edges> to obtain a <minimum spanning forest>, one <minimum spanning tree> per original <connected component of a graph>; no <spanning tree> of the whole <graph> exists.<Algorithms, 4th edition by Robert Sedgewick and others/KruskalMST.java>[Robert Sedgewick and Kevin Wayne, Algorithms, 4th edition, companion KruskalMST.java, class documentation and constructor: arbitrary signed weights, ties, disconnected input and sorted processing]{ref}
Back to article page
