Kruskal's algorithm: различия между версиями
Перейти к навигации
Перейти к поиску
Glk (обсуждение | вклад) (Новая страница: «'''Kruskal's algorithm''' --- алгоритм Краскала. The following algorithm due to Kruskal finds a minimum-weight spanning-tree, ''MWT'', of a weighte…») |
ALEXM (обсуждение | вклад) Нет описания правки |
||
| Строка 4: | Строка 4: | ||
spanning-tree, ''MWT'', of a weighted undirected graph <math>G = (V,E)</math>. | spanning-tree, ''MWT'', of a weighted undirected graph <math>G = (V,E)</math>. | ||
It is known that it operates in polynomial time. | It is known that it operates in polynomial time. | ||
* Relabel the elements of <math>E</math> so that | * Relabel the elements of <math>E</math> so that | ||
if <math>w(e_{i}) > w(e_{j})</math> then <math>i > j</math>''' | |||
* <math>MWT \leftarrow \varnothing</math> | * <math>MWT \leftarrow \varnothing</math> | ||
* ''' for <math>i = 1</math> to <math>|E|</math> do''' | * ''' for <math>i = 1</math> to <math>|E|</math> do''' | ||
if <math>MWT \cup \{e_{i}\}\mbox{ is acyclic }</math> then''' | |||
<math>MWT \leftarrow MWT \cup \{e_{i}\}</math> | |||
Текущая версия от 12:49, 1 марта 2018
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]