120
правок
Изменения
добавленн пример
2) Заведем систему непересекающихся множеств (DSU) и инициализируем ее множеством <tex>V</tex>.<br>
3) Перебирая ребра <tex>uv \in EG</tex> в порядке увеличения веса, смотрим, принадлежат ли <tex>u</tex> и <tex>v</tex> одному множеству. Если нет, то объединяем множества, в которых лежат <tex>u</tex> и <tex>v</tex>, и добавляем ребро <tex>uv</tex> к <tex>F</tex>.<br>
==Пример==
Отсортируем рёбра по их весам и рассмотрим их в порядке возрастания.
{| border = 1 cellspacing = 2 cellpadding = 5 class = "wikitable"
| Рёбра ''(в порядке их просмотра)'' || ae || cd || ab || be || bc || ec || ed
|-
| Веса рёбер ||<tex>1</tex> || <tex>2</tex> || <tex>3</tex> || <tex>4</tex> || <tex>5</tex> || <tex>6</tex> || <tex>7</tex>
|}
{| border = 1 cellspacing = 2 cellpadding = 5 class = "wikitable"
! Изображение !! Описание
|-
|[[Файл:Mst_kruskal_1.png|200px]]
|Первое ребро, которое будет рассмотрено - '''ae''', так как его вес минимальный.<br/>
Добавим его к ответу, так как его концы соединяют вершины из разных множеств ('''a''' - красное и '''e''' -зелёное).<br/>
Объединим красное и зелёное множество в одно (красное), так как теперь они соединены ребром.
|-
|[[Файл:Mst_kruskal_2.png|200px]]
|Рассмотрим следующие ребро - '''cd'''.<br/>
Добавим его к ответу, так как его концы соединяют вершины из разных множеств ('''c''' - синие и '''d''' - голубое).<br/>
Объединим синие и голубое множество в одно (синие), так как теперь они соединены ребром.
|-
|[[Файл:Mst_kruskal_3.png|200px]]
|Дальше рассмотрим ребро '''ab'''.<br/>
Добавим его к ответу, так как его концы соединяют вершины из разных множеств ('''a''' - красное и '''b''' - розовое).<br/>
Объединим красное и розовое множество в одно (красное), так как теперь они соединены ребром.
|-
|[[Файл:Mst_kruskal_4.png|200px]]
|Рассмотрим следующие ребро - '''be'''.<br/>
Оно соединяет вершины из одного красного множества, поэтому перейдём к следующему ребру '''bc'''<br/>
Добавим его к ответу, так как его концы соединяют вершины из разных множеств ('''b''' - красное и '''c''' - синие).<br/>
Объединим красное и синие множество в одно (красное), так как теперь они соединены ребром.
|-
|[[Файл:Mst_kruskal_5.png|200px]]
|Теперь рёбра '''ec''' и '''ed''' соединяют вершины из одного красного множества.<br/>
Всё рёбра были рассмотрены, поэтому алгоритм завершает работу.<br/>
Полученный граф - минимальное остовное дерево
|}
==Асимптотика==
