Материал: 62_201
ни 7. Які вершини досяжні з неї та відстань до яких найменша? Та ких вершин є три: 3, 4, 5. Але за нашим алгоритмом вибереться перша з них (у порядку зростання номерів вершин, що перегляда ються). Такою вершиною стане вершина 3 і ребро (7,3) (мал. 52, г).
6 |
І5 |
|
і*г |
i^f. |
|
|
|
|
|
||
5* |
5» |
|
і |
||
|
|
|
|
|
|
5 6 |
|
|
|
г І "1 1 1 |
|
1[2|7|ЗІ4| |
|
112 |
7 3 4 6 |
| 1 | 2 | 7 | 3 | 4 | 6 | 5 | |
|
а) |
|
|
б) |
в) |
|
|
|
|
Мал. 53 |
|
|
Кроки, зображені на малюнках 53, а-в, є аналогічними і очевидними, тому додаткових коментарів не потребують. Отже, на останньому кроці (мал. 53, в) отримано остовне дере во найменшої довжини, і ознакою цього є те, що кількість невідвіданих вершин дорівнює 0.
Реалізуємо описаний і розглянутий на прикладі алгоритм Прима для побудови остовного дерева мовою Pascal:
S := [ 2 . . п ] ; |
{Визначення |
номерів непереглянутих вершин.} |
while S <> [] do |
{Продовження пошуку, поки існують непереглянуті вершини.} |
|
begin |
|
|
min := 65535; |
{Визначення початкового мінімального значення «ваги» ребра.} |
|
for І := 1 to n do |
{Перегляд усіх вершин графа.} |
|
|
{Перегляд усіх вершин, до яких можуть існувати} |
|
for j := 1 to n do |
{ребра з/'-ї вершини.} |
|
if not (і in s) and (j in s) and (d[i, j] < min) and (d[i, j] > 0) {Якщо існує} |
||
then |
|
{ребро з меншою довжиною, то} |
begin |
|
|
min := d[i, j]; I := і; r := j; |
{запам'ятати його.} |
|
end; |
|
|
if r in S |
{Якщо визначене ребро веде у нову непереглянуту вершину, то} |
|
then begin |
|
|
writeln(f out, І, ' ', г); |
{виведення ЙОГО} |
|
S := S - [ г ] ; {і виключення цієї вершини з множини непереглянутих.} end;
end;
В алгоритмі Краскала розглядаються не вершини, а ребра. Ідеєю метода є поступова побудова остовного дерева за рахунок об'єднання окремих піддерев у єдине. Спочатку до порожнього
4 Інформатика, 9-Ю кл. |
97 |
остовного дерева включається ребро з найменшою «вагою». На наступному і решті кроках додаються ребра з найменшою «ва гою» серед тих, що залишились, які ще не включені до остовно го дерева.
Алгоритм можна сформулювати так.
1. Визначити початковий стан остовного дерева як порож ній і вважати, що всі вершини утворюють N піддерев, які не мають жодного ребра. Позначити ці піддерева порядковими номерами відповідних вершин.
2.Якщо кількість ребер в остовному дереві менша за (N — 1), то серед вільних ребер заданого графа, які ще не задіяні в остов ному дереві, визначити ребро з найменшою «вагою». Таким може бути лише ребро, що належить різним піддеревам. У про тилежному випадку перейти до п. 4.
3.Додати нове ребро до остовного дерева, а вершинам, які належать двом піддеревам, що об'єднуються, і до яких нале жать вершини поточного ребра, надати значення порядкового номера одного з цих піддерев.
4.Завершити алгоритм.
Для кращого тлумачення роботи описаного алгоритму роз глянемо той самий граф, що і для алгоритму Прима (мал. 51, а). Для візуалізації покрокового виконання алгоритму Краскала на малюнках будемо відображати як послідовність ребер зада ного графа, упорядковану за зростанням їх «ваги», так і послі довність тих з них, які додаються до остовного дерева, що бу дується. Біля номерів вершин графа вказуватимемо номери піддерев, до яких вони належать, на кожному кроці виконання алгоритму.
1... 2 ,
•З,
55 *
1 |
3 |
5 |
5 |
5 |
5 |
5 |
5 |
7 |
15 |
15 |
25 |
(4,6) |
(5,6) |
(1,2) |
(3,4) |
(3,7) |
(4,5) |
(4,7) |
(5,7) |
(2,7) |
(1,7) |
(3,5) |
(6,7) |
1
(4,6)
а)
Мал. 54
98
I l l
77 |
•3, |
б! |
|
|
|
|
|
|
5b4 . |
|
'44 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
3 |
5 |
5 |
5 |
|
5 |
5 |
5 |
7 |
15 |
15 |
25 |
(4,6) |
(5,6) |
(1,2) |
(3,4) |
(3,7) (4,5) (4,7) |
(5,7) |
(2,7) |
(1,7) (3,5) (6,7) |
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
3 |
|
|
|
|
|
|
|
|
|
|
|
(4,6) |
(5,6) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
6) |
|
|
|
Мал. 54 (продовження) |
|
|
|
|
||||
|
|
|
|
|
|
|
|
|||||
1.1A
7, •з,
б!
ьЧ
7 15 15 25 (4,6)|(5,6)|(1,2)|(3,4)[(3,7)|(4,5)1(4,7)1(5,7)|(2,7)|(1,7)1(3,5)|(6,7)|
1 |
3 |
5 |
|
|
|
|
|
|
|
|
|
(4,6) |
(5,6) |
(1,2) |
|
|
|
|
|
|
|
|
|
а) |
|
|
|
1 ц |
|
,2, |
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
б! |
|
?і |
Г |
|
|
|
|
|
|
|
|
|
, \ |
|
4, |
|
|
|
|
||
|
|
|
|
5* |
|
|
|
|
|
|
|
|
1 |
3 |
5 |
5 |
5 |
5 |
5 |
|
5 |
7 |
15 |
15 |
25 |
(4,6) |
(5,6) |
(1,2) |
(3,4) |
(3,7) |
(4,5) |
(4,7) |
|
(5,7) |
(2,7) |
(1,7) |
(3,5) |
(6,7) |
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
3 |
5 |
5 |
|
|
|
|
|
|
|
|
|
(4,6) |
(5,6) |
(1,2) |
(3,4) |
|
|
|
|
|
|
|
|
|
б) |
|
|
|
|
Мал. 55 |
|
|
|
|
|
|
|
99
|
|
|
|
ї ї * — 5 - |
л |
|
|
|
|
|||
|
|
|
|
|
|
7,'^5~T-*34 |
|
|
|
|
||
|
|
|
|
'З |
^ |
|
5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
5> |
|
* 4 4 |
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
3 |
5 |
5 |
5 |
5 |
5 |
|
5 |
7 |
15 |
15 |
25 |
(4,6) |
(5,6) |
(1,2) |
(3,4) |
(3,7) |
(4,5) |
(4,7) |
(5,7) |
(2,7) |
(1,7) |
(3,5) |
(6,7) |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
3 |
5 |
5 |
5 |
|
|
|
|
|
|
|
|
(4,6) |
(5,6) |
(1,2) |
(3,4) |
(3,7) |
|
|
|
|
|
|
|
|
а)
їм -572,
є:
т-АгЗх
5
|
|
|
|
з |
і |
|
|
|
|
|
|
|
|
|
|
|
|
|
4, |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 |
3 |
5 |
5 |
5 |
5 |
5 |
5 |
7 |
15 |
15 |
25 |
(4,6) |
(5,6) |
(1,2) |
(3,4) |
(3,7) |
(4,5) |
(4,7) |
(5,7) |
(2,7) |
(1,7) |
(3,5) |
(6,7) |
|
|
|
|
|
|
|
|
|
|
|
|
1 |
3 |
5 |
5 |
5 |
7 |
|
|
|
|
|
|
(4,6) |
(5,6) |
(1,2) |
(3,4) |
(3,7) |
(2,7) |
|
|
|
|
|
|
б)
Мал. 56
Отже, на перших п'яти кроках (мал. 54, а - 56, а) ребра вклю чаються до остовного дерева підряд із упорядкованого списку всіх ребер заданого графа. Відповідно протягом включення чер гових ребер до остовного дерева номери їх вершин змінюють свою ідентифікацію щодо номера піддерева, до якого вони вклю чаються. Наприклад, на малюнку 54, а, б вершини 4, 5, 6 покроково включаються до піддерева з номером 4. А на малюнку 55, а вершини 1, 2 утворюють інше піддерево з номером 1.
Починаючи з шостого кроку (мал. 55, б) необхідно оцінюва ти доцільність включення нових ребер до остовного дерева. Ребра (4,5), (4,7), (5,7) не можуть увійти до остовного дерева. Це пов'язано з тим, що всі ці ребра відносять до одного й того самого піддерева. А піддерев на даному кроці ми маємо два:
100
0 '1
>
4,
Мал. 57
(1,2) та (3,4), (3,7), (4,6), (5,6). Отже, нам залишилося з'єднати їх одним ребром з меншою «вагою». Тому серед двох можливих ребер (1,7) «вагою» 15 і (2,7) «вагою» 7 вибираємо другий варіант (мал. 56, б).
Таким чином, на малюнку 56, б ми отримали єдине остовне піддерево, оскільки два піддерева, що існували на попередньо му кроці, об'єдналися в одне. Окрім цього всі вершини остовного дерева мають однаковий ідентифікаційний номер дерева. Підсумувавши отриманий результат, визначимо, що довжина мінімального остовного дерева для заданого графа становить 26.
Проаналізувавши заданий граф, можна помітити, що остов не дерево, побудоване на малюнку 56, б, є не єдиним. Можливий ще такий варіант, який зображений на малюнку 57. Це дово дить той факт, що задача про визначення мінімального остовно го дерева для заданого графа дає єдину правильну відповідь тільки тоді, коли це стосується самого значення довжини цього дерева. Однак стосовно переліку ребер, що складають остовне дерево, не завжди можна отримати однозначну відповідь. Про це треба пам'ятати під час розв'язування графових задач, що передбачають отримання саме такої відповіді.
І ще одне зауваження. Ми використали під час пояснення алгоритму Краскала поняття номерної ідентифікації різних піддерев на різних кроках побудови остовного дерева, надавши номери вершинам заданого графа і надалі змінюючи значення цих номерів, якщо вершина входить до того чи іншого піддере ва. Однак це збігається з ідеєю фарбування вершин графа з по дальшим «перетіканням фарби» у вершини, які приєднуються до піддерева завдяки приєднанню відповідного їм ребра, і їх пе рефарбовуванням у новий колір. Якщо ця ідея більше до вподо би, то можна взяти її на озброєння для кращого розуміння ро боти даного алгоритму.
Саме ідею «перетікання фарби» використаємо у програмі мовою Pascal, що реалізує алгоритм Краскала:
101