Материал: 62_201

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

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

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

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

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

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

1.Визначити вершину графа start, з якої буде вестися пере­ гляд вершин заданого графа, занести її у стек (top := 1), а поряд­ ковий її номер у масиви order та ind.

2.Якщо стек вичерпано (top = 0) і пройдено всі вершини гра­ фа, то перейти до п. 12.

117

3.Визначити вершину і, яка записана у вершині стеку, як поточну.

4.Визначити вершину j, для якої існує ребро (і, j).

5.Якщо не існує ребра (і, j), тобто ми потрапили в тупик, то перейти до п. 8.

6.Якщо вершина / є новою, то записати її у вершину стеку, зробити поточною (і := j) і перейти до п. 3.

7.Якщо вершина j вже була занесена в стек, тобто не є но­ вою, її порядковий номер у стеку менший, ніж у вершини і, з якої ми на неї дивимося (order[j] < order[i]), і менший, ніж но­ мери вершин, які ми бачили з вершини і (order[j] < ind[i]), то необхідно перерахувати індекс вершини і, як тієї, що побачила відвідану вершину з номером, меншим, ніж усі досі видимі з неї (ind[i] := order\J]). Перейти до п. 4.

8.Якщо в стеку залишився один елемент (top = 1), то пере­ йти до п. 12.

9.Перш ніж зменшити значення вершини стеку на 1 (top := top - 1), необхідно розглянути останні дві вершини і тау, записані в ньому, і ребро (i,j), що їм відповідає.

10.Якщо з вершини j було «видно» лише вершини, що ма­ ють порядкові номери більші, ніж вершина і, тобто всі вони бу­ ли пройдені під час обходу графа після неї (order\i\ <= ind[j]), то вершина і є точкою з'єднання. Перейти до п. 3.

11.Якщо з вершини j було «видно» вершини з меншими по­ рядковими номерами, ніж з вершини і (ind[j] < ind[i]), і між ни­ ми існує ребро (i,j), то це означає, що з вершини і можна діста­ тися цих вершин також. Тому необхідно перевизначити індекс вершини і (ind[i] := ind[j]) і перейти до п. 3.

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

Традиційно розглянемо конкретний приклад і виконаємо описаний алгоритм покроково (мал. 65).

Зображатимемо сам граф, номери його вершин (верхній ря­ док у таблиці), стан стеку (stack - зліва від таблиці), масив по­ рядкових номерів вершин у процесі обходу графа (order - дру-

б)

Мал. 65

118

гий рядок у таблиці) та масив індексів цих вершин (ind - третій рядок у таблиці). Початковий стан елементів масиву порядко­ вих номерів є значення 0, а їхніх індексів - 9. Це дасть змогу за допомогою значень порядкових номерів вершин визначати, чи побачена вершина є новою, чи вже зустрічалася нам раніше. А для індексів значення 9 надасть можливість для подальшого покращання цього значення, оскільки вершин з таким поряд­ ковим номером у нашому графі точно не трапиться.

Нехай стартовою вершиною буде вершина 5. На першому кроці у стек буде занесено вершину 5, а її поточним номером буде відповідно 1 (мал. 66, а). З вершини 5 першою ми побачи­ мо вершину 1 (п'ятий рядок таблиці суміжності мал. 65, б). Це нова вершина, оскільки її порядковий номер дорівнює 1, тому допишемо її у стек, а її порядковий номер обходу 2 - у масив порядкових номерів (мал. 66, б).

З вершини 1, згідно з першим рядком таблиці суміжності, ми знову побачимо вершину 5. Оскільки вона не нова і її поряд­ ковий номер менший за порядковий номер вершини 1, то змі­ нимо індекс останньої. Він тепер дорівнюватиме 1 (мал. 67, а). Це означає, що з вершини 1 ми змогли побачити вершину 5, порядковий номер якої 1 менший, ніж у вершини 1 (2). Наступ­ ною вершиною (1-й рядок таблиці суміжності), яку видно з вер­ шини 1, є вершина 6. Вона нова, оскільки в масиві порядкових номерів order6 = 0. Записуємо її у стек і в масиві порядкових номерів надаємо order6 значення 3 (мал. 67, б).

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

119

б) Мал. 67

перевизначити значення індексу вершини 6. Вершина 1 має по­ рядковий номер 2, який менший, ніж порядковий номер поточ­ ної вершини 6 (3), і менший, ніж значення її індексу (9). Тому визначимо індекс вершини 6 значенням 2, і це означатиме, що з вершини 6 ми зможемо бачити вершину з меншим порядко­ вим номером (2), тобто вершину 1 (мал. 68, а).

Продовжуємо перегляд 6-го рядка таблиці суміжності. На­ ступна «видима» вершина з номером 2. Вона нова, і тому запи­ суємо її у стек, а її порядковий номер - у 2-й елемент масиву order (мал. 68, б).

Переходимо до 2-го рядка таблиці суміжності і визначаємо першу в цьому рядку видиму вершину. Нею є нова вершина 4.

120

(мал. 69, а). З вершини 4 можна побачити вершину 2, і тому спочатку необхідно перевизначити її індекс. Вершина 2 з по­ рядковим номером 4 була побачена раніше, ніж вершина 4 з по­ рядковим номером 5, а це означає, що індексом вершини 4 тепер буде значення 4 (мал. 69, б).

Вершина 4 є тупиковою, оскільки жодної нової вершин з неї ми не можемо побачити. Згідно з описаним алгоритмом, ми повинні повернутися до попередньої вершини, яка записана в стеку, тобто до вершини 2, і розглянути ребро (2,4). У разі потрапляння в тупик необхідно визначити, чи порядковий но­ мер вершини 2 не перевищує індекс вершини 4. У нашому ви­ падку цей факт справджується: order2 ^ ind4, (4 = 4), тому вер­ шина 2 є точкою з'єднання (мал. 70, а).

121