120
правок
Изменения
Нет описания правки
T.addEdge(minEdge[k]) // добавляем ребро если его не было в T
return T;
|}
==Пример==
{| class = "wikitable"
! Изображение !! Множество рёбер !! Описание
|-
|[[Файл:Mst_bor_1.png|200px]]
|
|Переберём все вершины и отметим для каждой вершины инцидентное ей ребро минимального веса.
{| width="100%"
|Вершина || '''a''' || '''b''' || '''c''' || '''d''' || '''e'''
|-
|Ребро минимального веса || '''ae''' || '''ab''' || '''cd''' || '''cd''' || '''ae'''
|}
|-
|[[Файл:Mst_bor_2.png|200px]]
|
|Объединим каждую полученную компоненту связности в одну вершину.<br/>
Полученные вершины ''abe'' и ''cd'' соединяют рёбра '''bc''', '''ac''', '''ec''' и '''ed'''.<br/>
Выберем среди них ребро с минимальным весом - '''ac''' и положим его между полученными вершинами.<br/>
|-
|[[Файл:Mst_bor_3.png|200px]]<br/>[[Файл:Mst_bor_4.png|200px]]
|<center>'''ae''' '''ab''' '''cd'''</center>
|Повторим алгоритм борувки на полученном графе, в результате чего он будет сжат в одну вершину.
|-
|<center>[[Файл:Mst_bor_5.png|80px]]</center>
|<center>'''ae''' '''ab''' '''cd''' '''ac'''</center>
|Граф сжат в одну вершину.<br/>Теперь нужно заменить множество рёбер заданного графа на полученное в алгоритме.
|-
|[[Файл:Mst_bor_6.png|200px]]
|
|Полученный граф - минимальное остовное дерево заданного графа.
|}
Общее время работы алгоритма получается <tex>O(E\log{V})</tex>.
==См. также==
* [[Алгоритм Прима]]
* [[Алгоритм Краскала]]
* [[Алгоритм двух китайцев]]
== Ссылки ==
* [http://rain.ifmo.ru/cat/view.php/vis/graph-spanning-trees/mst-2006 Визуализатор алгоритма]
* [http://www.csee.wvu.edu/~ksmani/courses/fa01/random/lecnotes/lecture11.pdf Minimum Spanning Trees]
* [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%91%D0%BE%D1%80%D1%83%D0%B2%D0%BA%D0%B8 Алгоритм Борувки— Википедия]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Остовные деревья ]]
