Както и да е, този алгоритъм също не е особено труден за разбиране и само трябва да се приложи няколко пъти. Той влиза към т.нар. "greedy" (алчни) алгоритми, защото на всяка стъпка взема най-доброто възможно решение.
---
ОПИСАНИЕ:
Прим е предложил алгоритъм за намиране на минимално покриващо дърво чрез поредица от разширения на едно дърво. Началното дърво се състои от единствен произволен връх.
На всяка стъпка дървото се разширява по „алчен” начин – към него се добавя най-близкият връх, който не принадлежи на дървото, т.е., който е свързан с връх от дъвото чрез ребро с най-малко тегло.
Алгоритъмът приключва когато всички върхове се включат в дървото. Изпълняват се n-1 итерации ('n' е броят върхове/възли), тъй като на всяка се включва по едно ребро.
АЛГОРИТЪМ:
(взето от книгата на Преслав Наков, "Програмиране = ++Алгоритми")
1) Започваме строенето на МПД от произволен връх s: в началото дървото ще бъде T(H,D), H = {s}, D = Ø.
2) Повтаряме n–1 пъти:
2.1) Избираме реброто (i, j) ∈ Е, такова че:
- i ∈ H , j ∈ V \ H;
- f(i, j) е минимално.
2.2) Добавяме върха j към H и реброто (i, j) към D.
P.S: Ако горните знаци ви изглеждат плашещо, погледнете тук и тук за някои пояснения.
ПРИМЕР:
Нека използваме графа от примера за алгоритъма на Крускал:
Първата стъпка е просто да си изберем начален връх.
Аз ще започна с 5, защото ми беше номера в класа едно време. 😀 Но може да е който и да е от другите.
Една кратка забележка - това не е "част от алгоритъма", но аз предпочитам да имам списъка от ребрата пред себе си, защото ако просто гледаш нарисувания граф или матрицата на съседство, има голям шанс да се объркаш и да изпуснеш някое от тях.
И за да стана още по-досаден, предпочитам да имам списъка на ребрата в сортиран възходящ ред (пишейки това изречение осъзнавам, че май наистина алгоритъмът на Крускал ми харесва повече - no offense, Прим).
Ето я и таблицата, взета от предишния ми пост:
Ребро
|
Тегло
|
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
|
Съветвам ви, ако имате таблицата със сортираните ребра пред себе си, да задрасквате тези, които вече са добавен към МОД (това не е необходимо, но ще улесни значително търсенето на следващото ребро).
За да сме по-практични ще превърнем таблицата в едно просто множество с всички ребра и теглата им:
R = { 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, следователно ще имаме общо 8 итерации на алгоритъма.
Така, след като сме избрали 5, създаваме две множества, H и D. H ще съдържа върховете, които сме включили към МОД, а D ребрата, които сме използвали, за да постигнем това (т.е. ребрата на МОД). В началото H съдържа само избрания от нас връх (в случая 5), а D е празно множество ( Ø ).
H = { 5 }
D = Ø
Сега трябва да намерим ребро, в което участва 5, с минимално тегло. Лесно виждаме от таблицата, че това е реброто 5-8. Тъй като в реброто участва и 8, добавяме 8 към H, а 5-8 към D:
H = { 5, 8 }
D = { 5-8 }
(итерация 1)
R = { 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) }
Сега ни трябва ребро, в което участва някой от елементите на H и теглото му отново е минимално. Гледайки таблицата, най-добрият вариант е 6-5 (тъй като 5 е елемент на H). Добавяме 6 към H и 6-5 към D:
H = { 5, 8, 6 }
D = { 5-8, 6-5 }
(итерация 2)
R = { 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) }
Продължаваме смело напред. Следващото ребро, което отговаря на изискванията ни, е 6-9 (6 е част от H и теглото е минимално). Добавяме 9 към H, а 6-9 към D:
H = { 5, 8, 6, 9 }
D = { 5-8, 6-5, 6-9 }
(итерация 3)
R = { 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) }
За жалост реброто 1-2 не съдържа върхове, които са в H, но пък 7-6 съдържа 6! Добавяме 7 към H и 7-6 към D:
H = { 5, 8, 6, 9, 7 }
D = { 5-8, 6-5, 6-9, 7-6 }
(итерация 4)
R = { 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) }
Сега сравнително лесно можем да видим, че следващото ребро ще е 3-6 (6 е част от H, теглото е минимално и преди него няма други ребра, които да използват връх от H). Добавяме 3 към H и 3-6 към D:
H = { 5, 8, 6, 9, 7, 3 }
D = { 5-8, 6-5, 6-9, 7-6, 3-6 }
(итерация 5)
R = { 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) }
Вече схванахте идеята, надявам се. Следващото ребро ще е 2-3. Добавяме 2 към H и 2-3 към D:
H = { 5, 8, 6, 9, 7, 3, 2 }
D = { 5-8, 6-5, 6-9, 7-6, 3-6, 2-3 }
(итерация 6)
R = { 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) }
Лесно забелязваме, че следващото ребро е 1-2, защото току що добавихме 2 към H и теглото е минимално. Добавяме 1 към H и 1-2 към D:
H = { 5, 8, 6, 9, 7, 3, 2, 1 }
D = { 5-8, 6-5, 6-9, 7-6, 3-6, 2-3, 1-2 }
(итерация 7)
R = { 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) }
Следващото и последно ребро (спомнете си, че алгоритъмът прави n-1 итерации) ще е 1-4. Добавяме 4 към H и 1-4 към D:
H = { 5, 8, 6, 9, 7, 3, 2, 1, 4 }
D = { 5-8, 6-5, 6-9, 7-6, 3-6, 2-3, 1-2, 1-4 }
(итерация 8)
R = { 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) }
Това беше последната итерация.
Крайният резултат се съдържа в множеството D - това са ребрата на МОД. Теглата им са същите като тези в множеството R и горната таблица.
---
Това е за днес! Ако видите някоя неточност, моля кажете ми. 😉
Няма коментари:
Публикуване на коментар