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. \begin{enumerate}

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

Glk 05:45, 26 мая 2011 (UTC) 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

Glk 05:45, 26 мая 2011 (UTC) if [math]\displaystyle{ MWT \cup \{e_{i}\}\mbox{ is acyclic } }[/math] then 05:45, 26 мая 2011 (UTC)Glk 05:45, 26 мая 2011 (UTC)[math]\displaystyle{ MWT \leftarrow MWT \cup \{e_{i}\} }[/math] \end{enumerate}