AlgorithmO #3 — Алгоритъм на Крускал (минимално покриващо дърво на граф)

(Първо публикувано на 05.01.2017)

Тъй като имам предстоящ изпит именно върху алгоритмите, които представям… защо да не се възползвам от възможността да затвърдя знанията си като ви споделя това, което научих? 😁

ОПИСАНИЕ:

Алгоритъмът на Крускал се използва за намиране на минимално покриващо дърво на граф (още наричано “минимално обхващащо дърво” или МОД). МОД представлява дърво, в което са включени всички върхове на графа и от всеки връх има ребро към друг, а теглото на ребрата, които ги свързват, е минимално.

АЛГОРИТЪМ:

Версия 1:

1) Сортираме ребрата по реда на нарастване на теглата

2) Разглеждаме всеки връх като дърво от 1 възел

3) Преглеждаме ребрата по сортирания ред

• Ако поредното ребро съединява 2 отделни дървета, то включваме реброто в МОД и обединяваме 2-те дървета в едно.

4) Повтаряме стъпка 3 до получаването на единствено дърво.

Версия 2:

(взето от книгата на Преслав Наков, “Програмиране = ++Алгоритми”)

1) Създаваме n множества, като в i-тото множество поставяме i-тия връх от графа.

2) Сортираме ребрата на графа във възходящ ред (по теглата им).

3) Създаваме празно дърво T(V, Ø). След приключване на алгоритъма T ще бъде търсеното покриващо дърво.

4) Последователно (n–1 пъти) добавяме ребро (i,j) ∈ Е към T, така че да бъде изпълнено:

• теглото f(i, j) да бъде възможно най-малко (разполагаме със сортиран по теглата списък на ребрата от графа)

• върховете i и j да се намират в различни множества

След всяко добавено ребро (i,j) обединяваме множествата, в които се намират i и j.

ПРИМЕР:

Нека имаме следния граф:

Нека първо ви покажа как ща намерим МОД с първата версия на алгоритъма.

Така, първото нещо, което трябва да направим, е да си направим списък с ребрата в графа и техните тегла. Нека използваме таблица, за да е по-прегледно:

Чудесно, сега нека ги сортираме във възходящ ред спрямо теглото (стъпка 1):

Следващата стъпка е да създадем 9 отделни дървета от по 1 възел (за всеки възел от графа):

Сега следва забавната част! Разглеждаме всяко едно ребро по сортирания ред.

Първо 5–8. 5 и 8 са в отделни дървета, следователно това ребро ще бъде част от МОД!

5–8 ✅

Продължаваме по същия начин със следващите ребра.

1–2 ✅
6–9 ✅
7–6 ✅
1–4 ✅
2–3 ✅
3–6 ✅
4–3 ❌

Опа, 4–3 няма да е част от МОД. Защо? Нека да видим как изглежда МОД преди да стигнем до реброто 4–3:

4–3 няма да е част от МОД, тъй като не свързва 2 отделни дървета (както се вижда, 4 има връзка с 1, а пък 1 с 2 и накрая 2 с 3. Следователно 3 и 4 вече са в едно и също дърво.

Добре, нека да продължим напред!

6–5 дали става? Ами, 5 има връзка само с 8, следователно 6 се намира в друго дърво. Значи 6–5 е валидно ребро.

6–5 ✅

Следва 5–9. 5 има връзка с 6, а пък 6 с 9, така че двата възела са част от едно дърво и няма да добавяме реброто към МОД.

5–9 ❌

Аналогично за 2–5 (2 има връзка с 3, а 3 с 6 и 6 с 5… да, става малко объркващо, но двата възела са част от едно и също дърво).

2–5 ❌

Продължаваме с 4–7. Тук връзката е дълга и широка (4–1 => 1–2 => 2–3 => 3–6 => 6–7), но резултатът е пак същият. Това ребро отново няма да е част от МОД.

4–7 ❌

Остана и последното ребро, 4–6. Двата възела се намират в едно и също дърво (4–1 => 1–2 => 2–3 => 3–6). Не го добавяме към МОД.

И така, в крайна сметка, горното дърво се оказва МОД на графа:

Ребрата му са следните: (5–8), (1–2), (6–9), (7–6), (1–4), (2–3), (3–6), (6–5)

Теглата са същите като в таблицата горе.

—

Добре, нека решим същата задача по другия начин.

Алгоритъмът ни казва, че трябва да направим “n” множества, т.е колкото са възлите в графа. В случая са 9, затова правим 9 множества (с по 1 елемент — стойността във възела):

{ 1 }
{ 2 }
{ 3 }
{ 4 }
{ 5 }
{ 6 }
{ 7 }
{ 8 }
{ 9 }

Тъй като ще ни трябва, ето я таблицата със сортираните ребра… once again:

Започваме с първото ребро, 5–8. Двата върха не са в едно множество, следователно това ребро ще е част от МОД (5–8 ✅). Съединяваме множествата { 5 } и { 8 }:

{ 1 }
{ 2 }
{ 3 }
{ 4 }
{ 5, 8 }
{ 6 }
{ 7 }
{ 9 }

Продължаваме с 1–2. Абсолютно същото като предишния случай (1–2 ✅). Съединяваме множествата { 1 } и { 2 }:

{ 1, 2 }
{ 3 }
{ 4 }
{ 5, 8 }
{ 6 }
{ 7 }
{ 9 }

Схванахте идеята, но все пак… 6–9? Да, става (6–9 ✅):

{ 1, 2 }
{ 3 }
{ 4 }
{ 5, 8 }
{ 6, 9 }
{ 7 }

Ами 7–6? Да, отново са в различни множества, така че добавяме това ребро към МОД (7–6 ✅):

{ 1, 2 }
{ 3 }
{ 4 }
{ 5, 8 }
{ 6, 9, 7 }

1–4? Валидно (1–4 ✅)! Добавяме към МОД:

{ 1, 2, 4 }
{ 3 }
{ 5, 8 }
{ 6, 9, 7 }

Аналогично за 2–3 (2–3 ✅):

{ 1, 2, 4, 3 }
{ 5, 8 }
{ 6, 9, 7 }

3–6? Отново към МОД (3–6 ✅). Спомнете си, че съединяваме множествата (а не просто добавяме единия елемент към множеството), така че сега ще имаме едно дълго множество:

{ 1, 2, 4, 3, 6, 9, 7 }
{ 5, 8 }

И така, стигнахме до по-интересната част. 4–3 не става (4–3 ❌), защото 4 и 3 са в едно множество. Но това не важи за 6–5 (6–5 ✅), защото 6 и 5 са в различни множества. Съединяваме двете множества:

{ 1, 2, 4, 3, 6, 9, 7, 5, 8 }

Така, получихме едно дълго множество, което съдържа всички възли. Това означава, че сме приключили с намирането на ребрата, които ще са част от МОД. 5–9, 2–5, 4–7 и 4–6 няма да са част от него (5–9 ❌, 2–5 ❌, 4–7 ❌, 4–6 ❌).

В крайна сметка, МОД ще включва следните ребра:

(5–8), (1–2), (6–9), (7–6), (1–4), (2–3), (3–6), (6–5)

Резултатът е абсолютно същият. Въпрос на избор е коя “версия” на алгоритъма ще ползвате!

—

Това е за днес. Ако видите някоя неточност, моля кажете ми (аз също все още се уча)! Peeeeace.