---
ОПИСАНИЕ:
Алгоритъмът на Крускал се използва за намиране на минимално покриващо дърво на граф (още наричано "минимално обхващащо дърво" или МОД). МОД представлява дърво, в което са включени всички върхове на графа и от всеки връх има ребро към друг, а теглото на ребрата, които ги свързват, е минимално.
АЛГОРИТЪМ:
Версия 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-2
|
1
|
|
1-4
|
2
|
|
4-7
|
14
|
|
4-6
|
16
|
|
7-6
|
1
|
|
4-3
|
4
|
|
2-3
|
3
|
|
2-5
|
13
|
|
3-6
|
3
|
|
6-5
|
12
|
|
6-9
|
1
|
|
5-9
|
13
|
|
5-8
|
1
|
Чудесно, сега нека ги сортираме във възходящ ред спрямо теглото (стъпка 1):
|
Ребро
|
Тегло
|
|
5-8
|
1
|
|
1-2
|
1
|
|
6-9
|
1
|
|
7-6
|
1
|
|
1-4
|
2
|
|
2-3
|
3
|
|
3-6
|
3
|
|
4-3
|
4
|
|
6-5
|
12
|
|
5-9
|
13
|
|
2-5
|
13
|
|
4-7
|
14
|
|
4-6
|
16
|
Следващата стъпка е да създадем 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
|
1
|
1-2
|
1
|
6-9
|
1
|
7-6
|
1
|
1-4
|
2
|
2-3
|
3
|
3-6
|
3
|
4-3
|
4
|
6-5
|
12
|
5-9
|
13
|
2-5
|
13
|
4-7
|
14
|
4-6
|
16
|
Започваме с първото ребро, 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.
Няма коментари:
Публикуване на коментар