Завдання
1. Розробити і реалізувати у вигляді програми алгоритм пошу-ку в ширину.
2. Виконати завдання 1 для графа з кількістю вершин N = 5, в якому досліджувані вершини є досяжними. Результат вико-нання програми вивести у файл.
3. Виконати завдання 1 для графа з кількістю вершин N = 5, в якому досліджувані вершини є недосяжними. Результат ви-конання програми вивести у файл.
4. Виконати завдання 2-3 для N = 100, вивівши результат ви-конання програми у файл.
Пошук у глибину
Якщо під час пошуку в ширину ми захоплювали усі нові вершини, що нам було видно з поточної вершини, у яку переміщувалися на кожному наступному кроці, то під час пошуку в глибину дещо змінимо нашу стратегію. А полягатиме вона ось у чому.
На кожному кроці алгоритму, знаходячись у наступній поточній вершині, будемо бачити лише одну нову, досі не «видиму», вершину і переходити до неї.
Розглянемо той самий граф, що й у попередньому випадку (мал. 1, а), і його таблицю суміжності (мал. 1, б). Будемо знову шукати шлях від вершини 1 до вершини 7. Під час по-шуку будемо так само, як і в попередньому алгоритмі, будува-ти дерево пошуку, послідовність переглянутих і нових «видимих» вершин та множину «відвіданих» вершин. На малюнку 9, а, б, в зображено перший крок нашого алгоритму, який повністю збігається з першим кроком алгоритму пошуку в ширину.
а) б)
Мал.9
Наступний крок буде таким: згідно з таблицею суміжності першою новою вершиною, яку ми бачимо з вершини 1, є вершина 2. Перейдемо до неї, додавши її у дерево пошуку, в по-слідовність «відвіданих» вершин і у множину (мал. 10, а, б, в)
 |
а) б) в)
 |
г) 10 д) е)
Перейшовши тепер у вершину 2, згідно з таблицею суміж-ності першою новою «видимою» вершиною є вершина З, оскільки вершину 1 ми вже відвідали. Додамо цю нову вершину до нашого дерева пошуку, в послідовність та множину (мал. 10, г, д, є) і перейдемо у послідовності до неї.
Якщо на наступному кроці алгоритму ми подивимося з вер-шини 3, то зможемо побачити вершини у такій послідовності (третій рядок таблиці суміжності): 1, 2, 4, 5. Серед них першою новою вершиною є вершина 4. Додамо її до переглянутих і пе-рейдемо до неї (мал. 11, а, б, в).
Що нового ми побачимо з вершини 4? Згідно з малюнком 11, а, б, ми побачимо вершини 1 і 3. Але жодна з них не є новою. Невже ми потрапили в тупик? Мабуть, ні, оскільки з попереднього методу пошуку в ширину ми дійшли до шуканої вершини. Можливо, ми пішли не тим шляхом і треба спробу-вати повернутися назад? Попередньою вершиною була вершина 3, і ми повернемося саме до неї (мал. 12, б)
|
а) б)
|
мал.11
|
|
б)
мал.12
Подивимося на заданий граф: чи є з вершини 3 інший шлях, відмінний від верпіини 4? Так, це шлях через вершину 5. І ця вершина є наступною новою вершиною, яку ми можемо поба-чити з вершини 3. Перейдемо до неї, записавши її у дерево по-шуку, замінивши у послідовності нею вершину 4 та дописавши її у множину (мал. 13, о, б, в).
Застосуємо нашу стратегію до останньої «переглянутої» вер-шини 5. З неї ми бачимо вершини 2, 3, 7. Але серед них вершина 7 є новою і одночасно шуканою. Саме тому дописуємо її в усі три інформаційні схеми (мал. 14, а, б, в) та вважатимемо пошук
завершеним
б)
|
|
мал.13
|
Ми знайшли відповідь на запитання за допомогою алгоритму пошуку в глибину: у заданому графі вершина 7 є досяжною з вершини 1 і шлях до неї міститься у послідовності, зобра-женій на малюнку 14, б.
Дивлячись на малюнок 11, а, де зображено досліджуваний граф, можна переконатися, що це справді шлях від вершини 1 до вершини 7. Однак отримана відповідь не збігається з відпо-віддю, одержаною за допомогою алгоритму пошуку в ширину. У чому ж справа? Ми повернемося до цього питання трохи зго-дом, порівнюючи ці два методи, а зараз визначимося з питан-ням реалізації цього алгоритму.
Як видно з покрокового виконання описаного алгоритму, ми весь час працюємо з таблицею суміжності, беручи звідти інфор-мацію про одну нову «видиму» вершину із поточної вершини графа. Ця нова вершина записується у послідовність, яка оброб-ляється за алгоритмом роботи зі стеком: ми дописуємо нову інформацію в кінець цієї послідовності і, у разі потрапляння у тупик, повертаємося до її передостаннього елемента, не роз-глядаючи надалі останній записаний елемент послідовності. І на останок: для запобігання повернення у тупикові вершини інфор-мацію про всі відвідані вершини зберігатимемо у множині.
Ми розглянули алгоритм пошуку в глибину на прикладі графа, де шукана вершина є досяжною із заданої, і отримали пози-тивну відповідь стосовно існування шляху між цими двома вершинами. А в іншій ситуації як дізнатися, що шлях відсутній? Згадаємо, як ми діяли у випадку, коли потрапляли у тупик. Ми поверталися до попередньої «переглянутої» вершини і намагалися знайти іншу нову, ще не «побачену», вершину. Логічно, що коли такої немає, то ми повернемося до попередньої віднос-но неї і будемо шукати вихід із цієї вершини і т. д. У разі відсутності шляху між двома заданими вершинами ми завершимо перегляд усіх записаних у стек вершин, повертаючись кожного разу до попередньої, спорожнивши тим самим стек. Отже, ознакою відсутності шляху в графі між двома заданими вершинами є те, що на деякому кроці алгоритму стек стане порожнім. Сформулюємо описаний алгоритм пошуку в глибину у словесній формі.
1. Вказати номер вершини k, з якої починається пошук за-даної шуканої вершини І. •
2. Почати перегляд вершин заданого графа з вершини k, записавши її у стек: і := k.
3. Якщо існує нова вершина з найменшим порядковим номером, яку можна побачити з вершини і, то зафіксувати її, записавши у стек і збільшивши при цьому індекс вершини стеку і на 1: і := і + 1. У протилежному випадку перейти до п. 5.
4. Якщо нова «побачена» вершина, записана у стек, є шука-ною, то перейти до п. 7.
5. Якщо з поточної вершини графа, яка записана у вершині стеку, не видно жодної нової вершини, то відкинути цю вершину, перейшовши до попередньої у стеку, зменшивши для цього значення індексу вершини стеку на 1: і := і - 1. Якщо після цьо-го стек став порожнім, тобто і = 0, то перейти до п. 9.
6. Перейти до перегляду наступної «побаченої» вершини і (п. 3).
7. Вивести інформацію про те, що шукану вершину / досяг-нуто і шлях до неї від вершини k існує.
8. Перейти до п. 10.
9. Вивести інформацію про те, що шукана вершина І недо-сяжна від вершини k і шлях до неї відсутній.
10. Завершити алгоритм.
Тепер ми вже готові до порівняння двох пошукових методів на графах у ширину та в глибину.
Спочатку відповімо на таке слушне запитання: чому у наведе-ному прикладі графа ми отримали різні відповіді, хоча кожна з них є правильною? А це відбулося тому, що для методів обрані різні стратегії: під час пошуку в ширину ми послідовно перегля-даємо усі видимі вершини і таким чином якнайшвидше досягне-мо шуканої вершини, а під час пошуку в глибину на кожному кроці ми переглядаємо лише одну нову вершину і тому можемо піти у хибному напрямі. Отже, можна зробити висновок, що алгоритм пошуку в ширину завжди визначає найкоротший шлях між двома заданими вершинами графа.
Який з методів кращий? Однозначно на це запитання відпо-вісти неможливо. Стосовно реалізації методів, можливо, по-шук у глибину простіший, оскільки одразу в стеку отримуємо шуканий шлях, та й при організації роботи зі стеком виникає менше помилок. Однак цей метод не завжди визначає найко-ротший шлях між заданими вершинами. І відповідь про відсутність шляху в разі використання пошуку в ширину може бути отримана швидше, ніж під час пошуку в глибину. Однак реалізація алгоритму пошуку в ширину вимагає організації та-кої структури даних, як черга, і більш складної стратегії визна-чення шляху між двома заданими вершинами.
Логічним є запитання про те, де можна застосовувати ці ал-горитми. По-перше, це пряме їх використання щодо визначен-ня шляху між двома заданими вершинами графа. По-друге, при допомозі пошукових алгоритмів на графах можна визнача-ти їх зв'язність. По-третє, і головне, саме на цих алгоритмах базуватимуться деякі з наступних алгоритмів, які ми надалі розглядатимемо у даному розділі.
Оцінка ефективності роботи алгоритму пошуку в глибину така сама, як і для пошуку в ширину, і становить 0(п + т).
Тестування обох алгоритмів повинно передбачати досліджен-ня як зв'язних, так і незв'язних графів. У групі зв'язних графів слід розглянути такі, у яких кількість вершин значно більша від кількості ребер, а також такі, у яких кількість ребер значно пе-реважає кількість вершин. Отримані результати для обох алго-ритмів необхідно порівняти щодо кількості виконаних кроків.