Kruskal's algorithm
Материал из WEGA
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]
