Материал: 62_201

for І := 1 to n do COlor[i] := і; {Ініціалізація визначення кольорів усіх вершин графа.} SOrt( 1, m); {Сортування всіх ребер заданого графа за зростанням їхньої довжини.}

Для коректної роботи фрагмента наведеної програми необ­ хідно зробити такі описи змінних:

type t = record

х, у: byte; len: word; end;

var: rib: array [1.. 5000] oft;

color: array[1..100] of word; d, n, m, i, j, et: word;

f j n , f_out: text;

Які висновки можна зробити із порівняння двох наведених підходів до побудови остовного дерева мінімальної довжини щодо оцінювання ефективності їх роботи?

По-перше, в алгоритмі Прима ми працюємо з таблицею суміжності, а в алгоритмі Краскала - з масивом ребер. Саме то­ му за браком пам'яті в алгоритмі Краскала не запам'ятовуєть­ ся таблиця суміжності, а під час покрокового введення вхідної інформації зразу ж будується масив ребер заданого графа. Роз­ мірність цього масиву при грубій оцінці становить (п*п) div 2.

102

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

По-друге, в алгоритмі Краскала передбачене ще й сортуван­ ня масиву ребер. Правда, при невеликій кількості вершин це не вимагає багато часу.

Однак, по-третє, слід зазначити, що, хоча перші дві характе­ ристики можуть бути сприйняті як недоліки алгоритму Крас­ кала, оцінка цього методу виглядає краще. В алгоритмі Прима нам доводиться переглядати вершини заданого графа п3 разів: у зовнішньому циклі множина вершин графа повинна спо­ рожніти, а в тілі цього циклу є два вкладених цикли, що також переглядають усі п вершин. В алгоритмі Краскала на сортуван­ ня масиву ребер іде n*log п операцій, а на перегляд усіх ребер - не більше ніж (n2 div 2)*п. Отже, n*log п + (п2 div 2)*п < п3.

І по-четверте, зробимо зауваження щодо оцінювання двох алгоритмів. Незалежно від наявності ребра між вершинами (і, /) алгоритм Прима переглядає всі елементи відповідної таб­ лиці суміжності, а алгоритм Краскала працює лише з наявни­ ми ребрами. Тому у разі невеликої кількості ребер у графі з великою кількістю вершин ефективнішим буде використання алгоритму Краскала.

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

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

Завдання

1.Розробити та реалізувати у вигляді програми алгоритм побу­ дови остовного дерева для заданого неорієнтованого незваженого графа.

2.Розробити та реалізувати у вигляді програми алгоритм побу­ дови мінімального остовного дерева для заданого неорієнтова­ ного зваженого графа з використанням алгоритму Прима.

103

3.Розробити та реалізувати у вигляді програми алгоритм побу­ дови мінімального остовного дерева для заданого неорієнтованого зваженого графа з використанням алгоритму Краскала.

4.Виконати завдання 1-3 для графа з кількістю вершин N ^ 10. Результат виконання програми вивести у файл.

5.Виконати завдання 1-3 для графа з кількістю вершин N = 100. Результат виконання програми вивести у файл.

6.Зробити аналіз результатів виконання програм для завдань 4 та 5.

1.Що розуміється під терміном «остовне дерево» для заданого гра­ фа? Наведіть приклад і обґрунтуйте термін «дерево» для даного випадку.

2.Із скількох ребер складається остовне дерево? Обґрунтуйте свою відповідь?

3.Чи можна побудувати остовне дерево для незв'язного графа? Обґрунтуйте свою відповідь.

4.Сформулюйте алгоритм побудови остовного дерева для зада­ ного графа і продемонструйте його покрокове виконання на власному прикладі.

5.На якому алгоритмі базується алгоритм побудови остовного де­ рева?

6.Чи завжди існує лише один варіант остовного дерева для зада­ ного графа? Обґрунтуйте свою відповідь.

7.Запишіть фрагмент Pascal-програми, що реалізує алгоритм по­ будови остовного дерева для заданого зв'язного графа.

8.Чи можна використати алгоритм пошуку в ширину для побудови остовного дерева для заданого зв'язного графа? Якщо так, то запропонуйте його реалізацію мовою Pascal.

9.Що розуміється під остовним деревом мінімальної довжини?

10.Які алгоритми побудови остовного дерева мінімальної довжини відомі і кому належить їх авторство?

11.Сформулюйте алгоритм Прима побудови остовного дерева мінімальної довжини.

12.Продемонструйте покрокове виконання алгоритму Прима на власному прикладі.

13.Запишіть реалізацію алгоритму Прима у вигляді фрагмента Pascal-програми.

14.Сформулюйте алгоритм Краскала побудови остовного дерева мінімальної довжини.

15.Продемонструйте покрокове виконання алгоритму Краскала на власному прикладі.

16.Запишіть реалізацію алгоритму Краскала у вигляді фрагмента Pascal-програми.

17.У чому полягають відмінності алгоритмів Прима і Краскала для побудови остовного дерева мінімальної довжини?

18.Яким чином адаптувати ідею перефарбовування вершин графа для тлумачення алгоритму Краскала?

104

Визначення найкоротшого шляху в графі. Алгоритм Дейкстри

Отже, ми дізналися, як визначити мінімальне остовне дере­ во в заданому навантаженому графі. Логічно запитати: а як визначити найкоротший шлях між двома вершинами такого графа? Саме таку задачу ми зараз і розв'яжемо. У цього алго­ ритму, який призначений для розв'язання поставленої задачі, є автор - відомий голландський учений, спеціаліст в царині комп'ютерних наук, один із класиків програмування, алго­ ритмів Едсгер Дейкстра (1930-2002).

Отже, задано зважений неорієнтований граф. Визначити найкоротший шлях від вершини st до вершини fin. Представи­ мо граф як у графічному вигляді (мал. 58, а), так і у вигляді таблиці суміжності (мал. 58, б).

б)

Мал. 58

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

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

105

Припустимо, що ми знаходимося на fe-му кроці виконання нашої задачі. Нехай ми відвідали деяку кількість вершин х, а з них побачили відповідну кількість вершин у. Якщо подивитися на малюнок 58, а, то, відвідавши вершину 1, побачимо вершини 2 і 7, а відвідавши вершину 2, не побачимо жодних нових вер­ шин. Після відвідування вершини 7, зможемо побачити абсо­ лютно всі вершини нашого графа. Але на яких відстанях від вершини 1 вони будуть? Ось з цього моменту і починає працюва­ ти така логіка: якщо до поточного кроку вершина j була на су­ марній найменшій відстані dtj від вершини і, то після того, як буде відвідана нова вершина І, може статися так, що шлях між вершинами і та / через вершину І буде коротшим від значення <2у. Тобто справедлива така формула: dtj = min(dii, dtl + d,X На­ приклад, на нашому графі з вершини 1 до вершини 7 можна напряму дістатися, пройшовши відстань 15, а через верши­ ну 2 - 12. Тож як краще? Зрозуміло, що другий варіант перева­ жує, оскільки d12 + d27 < d17.

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

Сформулюємо алгоритм Дейкстри, а потім виконаємо його покроково для нашого прикладу.

1.Визначити стартову вершину як поточну: і = st.

2.Якщо відвідані всі вершини графа, то перейти до п. 7.

3.Серед усіх видимих на поточному кроці вершин визначи­ ти ту, до якої існує найменша відстань, і визначити її як поточ­ ну і.

4.Перерахувати відстані до всіх видимих і відвіданих вер­ шин через вершину і і у разі отримання менших відстаней замі­ нити ними попередні значення, запам'ятавши номер вершини і, що покращила результат.

5.Надати поточній вершині і статус відвіданої.

6.Перейти до п. 2.

7.Вивести шлях від фінішної вершини до стартової і, у разі необхідності, обчислити найкоротшу відстань між цими вер­ шинами.

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

Розглянемо виконання описаного алгоритму покроково для наведеного на малюнку 58 прикладу. Стартовою вважатимемо вершину з номером 1, а фінішною - вершину з номером 6. Відстань до ще невидимих вершин на поточному кроці познача­ тимемо символом «°°». У першому рядку на малюнках познача­ тимемо номер вершини, у другому - поточну відстань від стар­ тової вершини до і-ї, у третьому - номер вершини, з якої було зроблено останнє перерахування найменшої відстані.

106