Тема 6. Запитання по темі “Основи теорії графів”

Запитання по темі “Основи теорії графів”

1.     Що називається графом? З яких елементів він складається?

2.     Поясніть такі поняття: інцидентність, суміжність, петля, нуль-граф. Наведіть приклади.

3.     Які графи називаються повними, плоскими, просторовими? Наведіть приклади.

4.     Як визначається степінь вершини?

5.     Коли можна стверджувати, що існує шлях між двома заданими вершинами? Як визначається довжина шляху?

6.     Які вершини називаються зв'язними? Який граф називається зв'язним? Наведіть приклади.

7.     Який шлях називається циклом? Який цикл називається простим? Наведіть приклади.

8.     Який граф називається деревом, а який лісом? Наведіть приклади.

9.     Які графи називаються орієнтованими, зваженими? Наведіть приклади.

10.  Які графи називаються ейлеровими, гамільтоновими? Наведіть приклади.

11.  Які є способи представлення графів? Наведіть приклади різних графів та їх представлення. Порівняйте ці способи.

12.   Вміти реалізувати ці способи представлення графів.

13.  Який пошуковий метод називається пошуком у ширину в графі? Поясніть покроково роботу цього методу на конкретному прикладі.

14.   Які структури даних необхідно використати під час реалізації у вигляді програми алгоритму пошуку в ширину?

15.  Опишіть алгоритм пошуку в ширину у словесній формі.

16.  Чим відрізняється стратегія організації пошуку в глибину від по­шуку в ширину?

17.  Прокоментуйте роботу алгоритму пошуку в глибину в покроковому режимі виконання на конкретному прикладі.

18.  Якими є ознаки існування і відсутності шляху між двома верши­нами заданого графа в алгоритмі пошуку в глибину?

19.  Сформулюйте словесний алгоритм пошуку в глибину.

20.     Які структури даних потрібно використати для пошуку в глибину.

21.  Порівняйте два пошукових методи на графах, відзначивши пози­тивні і негативні сторони кожного з них.

22.  Які існують критерії наявності ейлерового шляху в заданому графі? Наведіть приклади ейлерових графів.

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

24.  Покроково виконайте алгоритм пошуку ейлерового шляху або циклу в графі на власному прикладі.

25.  Які структури даних необхідно використати для реалізації алго­ритму пошуку ейлерового шляху в заданому графі у вигляді Pascal-програми?

26.  Яким є алгоритм пошуку гамільтонового шляху в заданому графі?

Тема 5. Ейлерів та гамільтонів графи

Ейлерів та гамільтонів графи

Розглянемо ейлерові графи.

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

Ейлерів шлях у неорієнтованому графі - це шлях, що проходить кожне ребро рівно один раз. Ейлерів цикл у графі – це цикл, що містить всі ребра графа. Граф, що має ейлеровий цикл, називається ейлеревим графом.

У дитинстві часто розв'язують такі головоломки: як, не відриваючи олівця від аркуша паперу, намалювати гео­метричну фігуру (наприклад, фігури на малюнку 1). Виявляється, що для деяких фігур ця задача може бути розв'язана, а для деяких - ні. Це пов'яза­но з тим, чи є задана фігура ейлеровим графом, тільки у цьому разі фігуру можна намалювати.

Ейлером було доведено, що задача пошуку ейлерового шля­ху має зміст тільки тоді, коли в графі є лише дві вершини з непарним степенем (k = 2) або коли всі вершини мають парний степінь {тоді кількість вершин з непарнпм степенем k = 0). У першому випадку будь-яка з дох вершин є стартовою при обході, а друга - кінцевою. У другому випадку ейлерів шлях існує і є замкненим, тобто утворює цикл, а обхід у ньому можна починати з будь-якої вершини.

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

На малюнку 1 зображено три різних графи, в яких присутні ейлерові шляхи та цикли. У першому і третьому графах усі вершини мають парні степені, тому існує ейлерів цикл, який можна почати у будь-якій з вершин цих графів, обійти всі їх ребра по одному разу і повернутися у стартову вершину. Другий граф має дві вершини зі степенем 3, тому у ньому існує не цикл, а шлях, який можна почати з будь-якої з цих двох вершин з непарним степенем, обійти всі ребра графа по одному разу і завершити обхід другій вершині, що має непарний степінь.

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

Алгоритм пошуку ейлерового шляху на графі можна сфсрмулювати таким чином:

1.      Для  кожної  вершини  графа  обчислити  степінь, перевірити наявність у ньому ейлерового шляху.

2.      У разі існування ейлерового шляху в заданому графі запам'ятати стартову вершину. Вважати її поточною.

3.      Якщо існують вершини, «видимі» з поточної вершини, продовжити пошук (перейти на п. 4). У протилежному випадку перейти на п. 5.

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

5.      Якщо для поточної вершини відсутні «видимі» вершини і усі ребра для неї знищені у процесі проходу по них, потрібно запам'ятати цю вершину як складову ейлерового шляху і повернутися до попередньої розглянутої вершини у разі, коли  така існує, надавши їй статус поточної, і перейти до п. 3.

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

Даний алгоритм ґрунтується на двох основних моментах:

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

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

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

У другому пункті, зазначеному вище, ми передбачаємо всі вання інших ходів у графі, які дають змогу нам пройти тими ребрами, що залишилися. Це відбудеться, якщо виникне ситуація, коли в поточної вершини всі ребра «спалені», тобто ми вже пройшлися усіма ребрами, що проходять через цю вершину. Тобто, можна включити до ейлерового шляху і продовжити пошук. А для цього в нас лишається тільки один вихід: повернутися крок назад у попередню вершину, в якій побували перед цим знайти таку можливість, рухаючись графом з неї. Якщо і в цій вершини всі ребра «спалені», то робимо ще один крок назад і т.д. Якщо в графі ще залишилося хоча б одне «неспалене» ребро, то це означає, що ми обов'язково знайдемо вершину, з якої можемо цим ребром пройти, включивши його до нашого шляху.

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

Розглянемо конкретний приклад і виконаємо його покроково, використовуючи наведений алгоритм. Для прикладу візьмемо граф та відповідну йому таблицю суміжності (малюнок 2). Аналіз цього графа показує, що в ньому існує ейлерів шлях, оскільки дві вершини 1 і 2 мають непарні степені.

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

З таблиці суміжності бачимо, що першою вершиною, у яку можемо попасти з вершини 1, є вершина 2. «Спалимо» peбро (1,2), замінивши у таблиці суміжності відповідні значення елементів на 0 (а[1,2] = а[2,1] = 0), і запишемо номер цієї вершини в нашу поточну послідовність.

Ми маємо ще другу послідовність, у якій будемо формувати результат, а саме ейлерів шлях, тобто будемо записувати туди номери тих вершин, для яких на по­точний момент «спалені» вже всі ребра. Поки що такої ситу­ації в нас ще не виникало. Перейдемо до другої вершини і подивимось по другому рядку таблиці суміжності, у яку вершину можна перейти на наступному кроці. Такою є вершина 3. Виконаємо такі ж дії, як на попередньому кроці: а[2,3] = а[3,2] = 0. Вершину 3запишемо у першу послідовність.

З вершини 3 ми бачимо вершину 1. Перейдемо до неї, записавши її наступною в послідовність і «спаливши» ребро ( а[3,1] = а[1,3] = 0).

Поки що тупикових ситуацій немає. З вершини 1 ми можемо перейти до вершини 4, що слідує з першого рядка таблиці суміжності. «Спалюємо» ребро (1,4) і записуємо в першу послідовність номер вершини 4.

Розглянемо вершину 4, тобто четвертий рядок таблиці суміжності. Бачимо, що не всі ребра цієї вершини «спалені» і ми можемо перейти до вершини 2.

Виникає колізія: переходячи до другого ряді таблиці суміжності, ми не маємо можливості далі кудись рухатися, усі ребра «спалені»! Таким чином ми визначили першу вершину з номером 2, для якої існує ейлерів шлях у заданої графі, що починається з вершини 1, але він не містить усіх ребер графа. Це означає, що пошук можна продовжувати далі. Переносимо номер вершини 2 у другу послідовність, а в першій послідовності повертаємося до попередньої вершини 4. Але й у вершині 4 немає жодного не «спаленого» ребра. Тоді запишемо і цю вершину в другу послідовність і зробимо один крок назад у першій послідовності.

Вихід знайдено: вершина 1 має ще не «спалені» ребра і вершина, у яку ми можемо перебратися, - це вершина 5. Запишемо номер цієї вершини в нашу першу послідовність після вершини 1 і спалимо ребро (1,5).

Перейдемо до вершини 5. З таблиці суміжності видно, що наступним ребром, яким можна рухатись, є ребро (5,6). Перейдемо у вершину 6 ребром (5,6).

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

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

Розглянувши детально алгоритм визначення ейлерового шляху в заданому графі, спробуємо його реалізувати на мові Pascal.

Спочатку визначимо, які структури даних потрібно застосувати для реалізації алгоритму. По-перше, це двовимірний масив для фіксації наявності ребер між заданими вершинами графа, елементами якого є значення 0 та 1. По-друге, одновимірний масив, у якому обробляються елементи з найбільшим індексом. Протягом виконання алгоритму цей індекс буде і збільшуватися, і зменшуватися. Ми використаємо таку структуру даних, що реалізує роботу з одновимірним масивом таким чином, - це стек. І ще один одновимірний масив, у якому дописуватимуться елементи - номери вершин заданого графа,  що формують ейлерів шлях у ньому.

Отже, можна запропонувати такий варіант реалізації алгоритму пошуку ейлерового шляху в заданому графі:

top := 1; rez__top := 0;

while top <> 0 do

  begin

   While (a[i, j] <> 1) and (j <= n) do inc(j); {Пошук існуючого ребра вершини і}

   if (j <= n)

      then begin

                           inc(top);stack[top]:=j;

                  a[I,j] := 0; a[j, i] := 0;

              end

     else begin

                   inc(rez_top); rez[rez_top] := stack[top];

                   dec(top)

              end;

   i:=stack[top];j:=1;

end;

Для визначення існування ейлерового шляху в заданому графі можна провести підрахунок степенів вершин цього графа під час введення початкових даних:

Count:=0;

for і := 1 to n do

 begin

St := 0;                                                {Ініціалізація визначення степеня вершини.}

for j := 1 to n do

    begin

     read( a[i, j]);                                  {Введення елементів таблиці суміжності.}

     if а[i, j] = 1 then inc(st)                    {Підрахунок степеня поточної вершини.}

  end;

  if o dd(st) then             {Якщо степінь поточної вершини непарний, то враховуємо}

                    begin inc(count); b := і end;       {цю вершину і запам'ятовуємо її номер.}

  end;

if count = 0 then Stack[top] := 1;        {Якщо всі вершини графа парні, то почи­наємо пошук із 1-ї вершини.}

if count = 2 then stack[top] := b;        {Якщо існує 2 непарні вершини, то почи­наємо пошук з однієї з них.}

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

У наведеному прикладі графа отриманий ейлерів шлях не є єдиним. Наприклад, шлях 123165142 також є ейлеровим. Але ми й не ставили задачу знайти всі ейлерові шляхи, а визначали: чи існує такий шлях. Цю задачу ми розв'язали.

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

Тепер перейдемо до визначення гамільтонових шляхів у за­даних графах.

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

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

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

Алгоритм пошуку гамільтонового шляху в заданому графі можна сформулювати так.

1.      Згенерувати поточну перестановку вершин заданого графа.

2.      Розглянути першу пару послідовних вершин у перестановці.

3.      Якщо ребро між поточною парою вершин перестановки відсутнє, то перейти до п. 6.

4.      Якщо існує наступна пара послідовних вершин у графі, то перейти до п. 3.

5.      Якщо для всіх пар послідовних вершин існують ребро у графі, то перейти до п. 7.

6.      Якщо існує наступна перестановка вершин заданого графа, то перейти до п. 1. У протилежному випадку перейти де ...

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

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

Описаний алгоритм реалізуємо у вигляді фрагмента Pascal-прoгpaми:

flag := false;

i:=1;

repeat

  j := 1;

  while (d[a[j],a[j+1]]=1) and )j<n) do inc(j);

 if j=n then                                             

              begin

    for j := 1 to n do write(a[j],’ ‘);

                  writeln; flag := true;

end;

   inc(i);

   perestanovka;                     {Визначення наступної перестановки вершин графа}

until (i>= n) or flag;      {Завершення пошуку: коли відповідь знайдена або відсутня}

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

Виконавши описаний вище алгоритм для графа, зображено­го на малюнку 2, отримаємо результат: 324156

Якщо дещо модифікувати наведений фрагмент програми і визначити всі можливі гамільтонові шляхи у розглянутому прикладі графа, то отримаємо таку відповідь:

324156 324165 423156 423165 61324 561423 651324 651423

Отже, наведений приклад графа є не тільки ейлеровим, а ще й гамільтоновим.

Алгоритм побудови гамільтонового шляху або циклу має оцінку ефективності його роботи як О(п).

Для тестування наведених алгоритмів необхідно поряд із зв'язними графами розглянути і незв'язні. Це дасть змогу пе­ревірити коректність розроблених алгоритмів щодо аналізу визначення ейлерових та гамільтонових шляхів. Серед зв'яз­них графів необхідно розглянути як повні графи, так і неповні.

Завдання

1.   Розробити та реалізувати у вигляді програми алгоритм ви­значення заданого графа як ейлерового.

2.   Розробити та реалізувати у вигляді програми алгоритм ви­значення ейлерового циклу у графі.

3.   Виконати завдання 1—2 для графа з кількістю вершин N <= 10, в якому всі вершини мають парні степені.

4.   Виконати завдання 1-2 для графа з кількістю вершин N <= 10, в якому є дві вершини з непарними степенями.

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

6.    Виконати завдання 1-2 для графа з кількістю вершин N = 100, в якому є дві вершини з непарними степенями.

7.    Розробити та реалізувати у вигляді програми алгоритм визначення гамільтонового циклу у графі.

8.    Виконати завдання 7 для графа з кількістю вершин N =5.

9.     Виконати завдання 7 для графа з кількістю вершин N > 5.

Тема 4. Пошук в глибину

Пошук у глибину

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

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

Розглянемо той самий граф, що і при пошуку в ширину, і його таблицю суміжності. Знову шукатимемо шляхит від вершини 1 до вершини 7. Так само буватимемо дерево пошуку, послідовність переглянутих і нових «видимих» вершин та множину «відвіданих» вершин. На малюнку 1 зображено перший крок нашого алгоритму, який повністю збігається з першим кроком алгоритму пошуку в ширину.  

Згідно з таблицею суміжності першою новою вершиною, яку ми бачимо з вершини 1, є вер­шина 2. Перейдемо до неї, додавши її у дерево пошуку, в по­слідовність «відвіданих» вершин і у множину (Малюнок 2).

Перейшовши тепер у вершину 2, згідно з таблицею суміж­ності першою новою «видимою» вершиною є вершина З, оскільки вершину 1 ми вже відвідали. Додамо цю нову верши­ну до нашого дерева пошуку, в послідовність та множину (Малюнок 3) і перейдемо у послідовності до неї.

Якщо на наступному кроці алгоритму ми подивимося з вер­шини 3, то побачимо вершини у такій послідовності (третій рядок таблиці суміжності): 1, 2, 4, 5. Серед них першою новою вершиною є вершина 4. Додамо її до переглянутих і пе­рейдемо до неї (Малюнок 4).

З вершини 4 ми побачимо вершини 1 і 3, але жодна з них не є новою. Далі шляху немає, тому повертаємось назад. Оскільки попередньою вершиною була вершина 3, тому повернемось до неї (Малюнок 5).

Подивимося чи є з вершини 3 інший шлях, відмінний від вершини 4? Це шлях через вершину 5. Вона є наступною новою вершиною, яку ми бачимо з вершини 3. Перейдемо до неї, записавши її у дерево пошуку, замінивши нею вершину 4 у послідовності та дописавши її у множину (Малюнок 6).

З вершини 5 бачимо вершини 2, 3, 7. Новою є  вершина 7, одночасно вона є шуканою. Тому дописуємо її в дерево пошуку, послідовність та множину (Малюнок 7).

Отже, у заданому графі вершина 7 є досяжною з вершини 1 і шлях до неї міститься у послідовності (Малюнок 7).

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

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

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

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

1.   Вказати номер вершини k, з якої починається пошук заданої шуканої вершини z.

2.      Почати перегляд вершин заданого графа з вершини k, записавши її у стек: і := k.

3.      Якщо існує нова вершина з найменшим порядковим номером, яку можна побачити з вершини і, то зафіксувати її, записавши у стек і збільшивши при цьому індекс вершини стеку і на 1: і := і + 1. У протилежному випадку перейти до п. 5.

4.      Якщо нова «побачена» вершина, записана у стек, є шуканою, то перейти до п. 7.

5.      Якщо з поточної вершини графа, яка записана у вершині стеку, не видно жодної нової вершини, то відкинути цю вершину, перейшовши до попередньої у стеку, зменшивши для цього значення індексу вершини стеку на 1: і := і - 1. Якщо після цього стек став порожнім, тобто і = 0, то перейти до п. 9.

6.      Перейти до перегляду наступної «побаченої» вершини і (п. 3).

7.      Вивести інформацію про те, що шукану вершину z досягнуто і шлях до неї від вершини k існує.

8.      Перейти до п. 10.

9.      Вивести інформацію про те, що шукана вершина z недосяжна від вершини k і шлях до неї відсутній.

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

Наведемо фрагменти алгоритму пошуку в глибину у вигляді Pascal-програми:

Описуємо масив для послідовності вершин   var a:array[1..100] of byte;

Вводимо матрицю суміжності d розмірністю n*n.

top:=1; a[1]:=k;                                                                    {Ініціалізація роботи алгоритму.}

flag := false; s:=[k];

while (top > 0) and not flag do {Поки стек не порожній і не знайдено шукану}
                                                                                            {вершину,}

begin

i:=1;                                                        {починаємо пошук нової «видимої» вершини.}

While (і <= n) and not flag do             {Пошук нової «видимої» вершини з к-ї вершини.}

begin

if (d[a[top], i] = 1) and not (і in S)                    {Якщо існує нова «видима» вершина,}

then begin

         inc(top); a[top] := i;                                                  {то записуємо її у стек і}

         s:=s+[i];                                                                               {заносимо у множину.}

          if i = z then flag := true; {Якщо нова вершина є шуканою, то фіксуємо це.}

     end
else inc(і)                              {Інакше переходимо до нової «побаченої» вершини.}

end;

if not false then dec(top)                                     {Якщо відсутні нові «видимі» вершини,}

end;                                                                               {то повертаємося до попередньої.}

Для виведення знайденого шляху між двома заданими вершинами графа можна використати такий фрагмент:

if flag then begin                                                                  {Якщо шлях знайдено, то}

           writeln('YES');                                           {виводимо інформацію про це і}

           while top <>0 do

               begin                                                          {виводимо послідовність}

                        write(a[top],' '); dec(top)                                     {елементів стеку.}

                   end

           end

   else write('NO');                      {Виведення інформації про відсутність шляху.}

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

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

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

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

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

Завдання

1.      Розробити і реалізувати у вигляді програми алгоритм пошуку в глибину.

2.      Виконати завдання 1 для графа з кількістю вершин N =5, в якому досліджувані вершини є досяжними.

3.      Виконати завдання 1 для графа з кількістю вершин N =5, в якому досліджувані вершини є недосяжними.

4.       Виконати завдання 2-3 для N = 100.