120
правок
Изменения
Нет описания правки
==Пример==
Задан неориентированный связный граф, требуется построить в нём минимальное остовное дерево.<br/>Создадим новый граф, содержащий все вершины из заданного графа, но не содержащий рёбер.<br/>Этот новый граф будет ответом, в него будут добавлены рёбра из заданного графа по ходу выполнения алгоритма.<br/>Отсортируем рёбра заданного графа по их весам и рассмотрим их в порядке возрастания.{| border = 1 cellspacing = 2 cellpadding = 5 class = "wikitable"
| Рёбра ''(в порядке их просмотра)'' || ae || cd || ab || be || bc || ec || ed
|-
|}
{| border = 1 cellspacing = 2 cellpadding = 5 class = "wikitable"
! Изображение !! Описание
|-
|[[Файл:Mst_kruskal_4.png|200px]]
|Рассмотрим следующие ребро - '''be'''.<br/>
Оно соединяет вершины из одного красного множества, поэтому перейдём к следующему ребру '''bc'''<br/>
Добавим его к ответу, так как его концы соединяют вершины из разных множеств ('''b''' - красное и '''c''' - синие).<br/>
Объединим красное и синие множество в одно (красное), так как теперь они соединены ребром.
|-
|[[Файл:Mst_kruskal_5.png|200px]]
|Теперь рёбра Рёбра '''ec''' и '''ed''' соединяют вершины из одного красного множества.,<br/>поэтому после их рассмотра они не будут добавлены в ответ<br/>
Всё рёбра были рассмотрены, поэтому алгоритм завершает работу.<br/>
Полученный граф - минимальное остовное дерево
==См. также==
* [[Алгоритм Прима]]
* [[Алгоритм Борувки]]
==Ссылки==
* [http://rain.ifmo.ru/cat/view.php/vis/graph-spanning-trees/mst-2005 Визуализатор 1]
* [http://rain.ifmo.ru/cat/view.php/vis/graph-spanning-trees/mst-2006 Визуализатор 2]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Остовные деревья ]]
