Kruskal's algorithm

Kruskal's algorithm --- алгоритм Краскала.

The following algorithm due to Kruskal finds a minimum-weight spanning-tree, MWT, of a weighted undirected graph [math]\displaystyle{ G = (V,E) }[/math]. It is known that it operates in polynomial time.

• Relabel the elements of [math]\displaystyle{ E }[/math] so that

if [math]\displaystyle{ w(e_{i}) \gt w(e_{j}) }[/math] then [math]\displaystyle{ i \gt j }[/math]

• [math]\displaystyle{ MWT \leftarrow \varnothing }[/math]
• for [math]\displaystyle{ i = 1 }[/math] to [math]\displaystyle{ |E| }[/math] do

if [math]\displaystyle{ MWT \cup \{e_{i}\}\mbox{ is acyclic } }[/math] then [math]\displaystyle{ MWT \leftarrow MWT \cup \{e_{i}\} }[/math]