Материал: 62_201

3.Якщо із поточної вершини існує ребро у нову ще не відві­ дану верпіину /, то перейти до п. 4, у протилежному випадку перейти до п. 5.

4.Запам'ятати вершину /' як нову відвідану у послідовності, визначити ребро (і, j) як складову майбутнього остовного дере­ ва, збільшити лічильник кількості ребер в остовному дереві на 1 (count := count + 1) і визначити вершину j як поточну (і := у). Перейти до п. 3.

5.У послідовності, де зберігаються номери переглянутих вершин, перейти до передостанньої вершини і визначити її як поточну.

6.Якщо у послідовності ще є вершини, до яких можна по­ вернутися, і count < N - 1, то перейти до п. 3.

7.Завершити алгоритм.

Розглянемо виконання описаного алгоритму для прикладу звичайного незваженого неорієнтованого графа (мал. 48).

Почнемо побудову остовного дерева з вершини 7. На ма­ люнках 49 і 50 відображені всі етапи виконання алгоритму по­ будови остовного дерева для заданого графа. Прокоментуємо їх. На перших двох етапах (мал. 49, а, б) нам доводиться після фіксації чергового ребра остовного дерева (у другому рядку ма­ люнка) повертатися у послідовності, що відображається у пер­ шому рядку малюнка, на крок назад, тобто до вершини з номе­ ром 7, оскільки ні з вершини 1, ні з вершини 2 не видно іншої вершини, окрім 7. Наступною видимою вершиною з вершини 7 є вершина 3. Запишемо її у стек (мал. 49, в).

Починаючи з вершини 3 ми можемо перейти до нової вер­ шини 4, а з неї до вершини 5 (мал. 50, а, в), записуючи при цьо­ му ребра остовного дерева у другий рядок кожного малюнка. Однак із вершини 5 неможливо побачити жодної нової верши­ ни, оскільки вершини 4 і 7, які видно із вершини 5, ми вже ба­ чили. Отже, необхідно повернутися у попередню вершину 4

92

(мал. 50, в). Але і з нею відбувається те саме: вершини 3, 5 і 7 нами вже «відвідані». Тому повертаємося ще на крок назад у вершину 3. І тут спостерігається та сама ситуація. Ще один крок назад поверне нас у вершину 7. Згідно з описаним алго­ ритмом, і як це видно з малюнка 49, а та відповідної йому таб­ лиці суміжності (мал. 49, б), з вершини 7 можна побачити ще одну вершину 6. Це і є останнє ребро остовного дерева, яке ми зафіксуємо у другому рядку на малюнку 50, в.

Яку реалізацію описаного алгоритму можна запропонувати мовою Pascal? За традицією спочатку розберемося, які струк­ тури даних необхідно для цього використати. Зрозуміло, що послідовність для запам'ятовування поточних вершин не­ обхідно організувати як стек. Окрім цього треба буде викорис­ тати множину для фіксації номерів вершин, у яких ми вже по­ бували і які вже використані в ребрах, що складають остовне дерево. Отже, фрагмент такої програми може бути таким:

93

t op := 1; stack[1 ] := k; {ініціалізація початку роботи алгоритму.} s := [ k j ; count := 0;

while (top > 0) and (count < n - 1) do{noi±iyK ведеться, поки стек ие порожній}

Існує ще одна ідея алгоритму, який будує остовне дерево. Давайте уявимо собі, що у вершинах заданого графа розміщені ємності з різною фарбою. Якщо дати можливість фарбі з вер­ шини і «перетекти» існуючим ребром (і, j) у вершину/, то вва­ жатимемо, що вершина/ перефарбується у колір вершини і.

Отже, проаналізуємо виконання цього алгоритму на заданому графі (мал. 48, а). Із вершини 7 фарба «перетече» зразу в усі реш­ ту вершин, які в результаті перефарбуються у колір вершини 7, і ми отримаємо остовне дерево. Воно складатиметься з таких ре­ бер: (7,1), (7,2), (7,3), (7,4) (7,5), (7,6). Як бачимо, ми отримали дещо іншу відповідь, але вона також правильна. Мабуть, ви одразу впізнали в запропонованому алгоритмі пошук у ширину! У вигляді фрагмента Pascal-програми він буде таким:

head := 1; tail := 2; queue[1 ] := k; {ініціалізація початку роботи алгоритму.} s := [k]; count :=0;

While (head <> tail) and (count < П - 1) do {Пошук ведеться, поки черга не порожня}

94

I e l s e inc(i) {У протилежному випадку переходимо до наступної вершини.}

end;

if і > П t h e n inc(head) {Якщо у поточної вершини не існує ребер, що ведуть} e n d ; {до нових вершин, то повертаємося до попередньо переглянутої.}

У цьому алгоритмі може бути кілька критеріїв його виконання:

-кількість ребер остовного дерева досягла (N - 1);

-«голова» черги збіглася з її «хвостом»;

-усі вершини мають однаковий колір.

Вибір визначення цих критеріїв за автором реалізації алгорит­ му. Окрім цього, слід зауважити, що кожний із запропонованих алгоритмів має право на існування, а ідея з «перефарбовуванням» вершин може бути застосована в інших алгоритмах на графах.

Оцінка ефективності роботи алгоритму побудови остовного дерева очевидна: оскільки основою його є пошук у глибину, то оцінка також становитиме 0(п + т).

Під час тестування алгоритму можна розглянути графи, які самі є остовними деревами, а також майже повні графи. Це дасть змогу порівняти ефективність роботи алгоритму.

Побудова остовного дерева мінімальної довжини. Алгоритми Прима і Краскала

Цей алгоритм запропонували в кінці 50-х років XX століття незалежно один від одного два автори - Р. Прим і Дж. Краскал. Він полягає у побудові остовного дерева мінімальної довжини для зважених неорієнтованих графів, тобто таких, для кожно­ го ребра яких задане значення довжини (або «ваги»). Нага­ даємо, що матриця суміжності такого графа буде містити еле­ менти, які дорівнюють довжині кожного ребра.

Шукане остовне дерево будується за допомогою «жадібного» алгоритму, тобто на кожному кроці вибирається ребро з най­ меншою довжиною.

Алгоритми Прима і Краскала відрізняються лише на ідейно­ му рівні. Розглянемо їх.

Алгоритм Прима передбачає перегляд вершин заданого гра­ фа, починаючи з будь-якої з них, і наступне приєднання іншої вершини, до якої веде ребро з меншою «вагою». Подальше при­ єднання нової вершини відбувається саме за цим принципом.

Отже, алгоритм можна сформулювати так.

1. Визначити вершину і, з якої починається побудова остов­ ного дерева, як відвідану.

2. Якщо є невідвідані вершини, які ще не приєднані до ос­ товного дерева, то визначити ту з них /, до якої із множини відвіданих вершин і веде найкоротше ребро. У протилежному випадку перейти до п. 4.

95

2 шини 12 3 4 5 6 7

б)

Мал. 51

3.Додати ребро (і, j) до остовного дерева, а вершину у - до множини відвіданих вершин. Перейти до п. 3.

4.Завершити алгоритм.

Розглянемо виконання алгоритму Прима на прикладі графа (мал. 51, а) та його матриці суміжності (мал. 51, б).

На першому кроці виконання алгоритму визначимо верши­ ну, з якої починається побудова остовного дерева. У нашому випадку це є вершина з номером 1. Вилучимо вершину 1 з пер­ шого рядка і додамо до другого як ту, що входить на початку до остовного дерева (мал. 52, а).

Звершини 1 виходить два ребра (1,2) і (1,7). Як видно з малюнка 51, а, меншим серед них є ребро (1,2). Тому на малюнку 52, бзображено саме це ребро як те, що додається на даному кроці до остовно­ го дерева, а вершина 2 вилучається з першого рядка (мал. 52, б) і додається до другого, як та, що вже задіяна в остовному дереві. На наступному кроці (мал. 52, в) шукаємо найближчу вершину з вер­ шини 2, яка ще не задіяна в остовному дереві. Такою є лише одна вершина 7, що знаходиться на відстані 7. Визначаємо нове ребро остовного дерева (2,7), додаємо вершину 7 до переліку відвіданих та вилучаємо з переліку невідвіданих. Тепер перейдемо до верши-

Мал. 52

96