= Kruskal's algorithm
{c}
{wiki}
= Kruskal algorithm
{c}
{synonym}
Process <edges> in increasing weight, accepting an <edge> exactly when its endpoints lie in different current <connected components of a graph>. A rejected <edge> can never cross a later component's boundary, since components only merge. Thus each accepted <edge> is lightest across the <cut of a graph> given by one current component. The <minimum spanning tree cut property> proves that the final <spanning tree> is minimum.
Back to article page
