Материал: 62_201
За алгоритмом повертаємося у вершину 2. У 2-му рядку таб лиці суміжності елементи 5 і 6 дорівнюють 1, що говорить про наявність ребер (2,5) та (2,6). Порядковий номер вершини 5 менший за порядковий номер вершини 2(1 < 4) і менший за її індекс (1 < 9), тому індекс вершини 2 тепер дорівнюватиме 1, а це означає, що з вершини 2 ми змогли побачити вершину з мен шим порядковим номером, ніж досі. Так само розглянемо і вер шину 6 - наступну видиму вершину з вершини 2. Однак індекс вершини 2 при цьому не покращиться, оскільки вершину 6 ми «зустріли» пізніше, ніж вершину 5 і її порядковий номер 3, що більший за 1 (мал. 70, б).
Переглянувши всі видимі вершини з вершини 2, ми не може мо побачити жодної нової. Це свідчить про те, що ми знову по трапили в тупик. Зменшуємо значення вершини стеку, переходя чи до вершини 6, і розглянемо ребро (6,2) на малюнку 71, а. По тенційно вершина 6 може бути точкою з'єднання. Для цього по винна виконатися умова orderG < ind2. Як бачимо з малюнка 70, б, цього не відбувається (3 > 1), тому перевіряємо виконання умови ind2 < inde. Ця умова для ребра (6,2) виконується, оскільки 1 < 2, тому, згідно з п. 11 описаного вище алгоритму, перевизначаємо індекс вершини 6, надаючи йому значення 1 (мал. 71, а). Тепер переходимо до перегляду 6-го рядка у таблиці суміжності. Оскільки у вершину 6 ми повернулися з вершини 2, де були роз глянуті всі попередні вершини, то у вершині 6 можемо починати розгляд видимих вершин, що слідують за вершиною 2. Новою вершиною, видимою з 6, є вершина 3. Допишемо її у стек і перей демо в неї (мал. 71, б).
Першою видимою вершиною з вершини 3 є вершина 6. Вона не нова, тому перевизначимо індекс поточної вершини 3. Він
8 Р
5 9
-<ЇЗ
7
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
2 |
4 |
0 |
5 |
1 |
3 |
0 |
0 |
1 |
1 |
9 |
4 |
9 |
1 |
9 |
9 |
1 |
2 |
3 |
4 |
•5 |
6 |
7 |
8 |
2 |
4 |
4 |
5 |
1 |
3 |
0 |
0 |
1 |
1 |
9 |
4 |
9 |
1 |
9 |
9 |
а) |
б) |
Мал. 71
122
a: |
|
8 P |
K |
A.' |
•+*: |
|
|
&: |
|
|
|
|
|
7 |
|
|
|
|
|
|
|
|
|
I |
2 |
3 |
4 |
5 |
6' |
7 |
8 |
2 |
4 |
4 |
5 |
1 |
3 |
0 |
0 |
1 |
1 |
3 |
4 |
9 |
1 |
9 |
9 |
1 |
2 |
U |
4 |
5 |
6 |
7 |
8 |
2 |
4 |
4 |
5 |
1 |
3 |
5 |
0 |
1 |
1 |
3 |
4 |
9 |
1 |
9 |
9 |
6)
Мал. 72
зміниться зі значення 9 на значення 3 (мал. 72, а). Продовжую чи перегляд 3-го рядка, ми побачимо нову вершину 7 і допише мо її у стек під порядковим номером 5 (мал. 72, б).
Дивлячись з вершини 7, ми спочатку побачимо вже раніше видиму вершину 3. Тому перевизначимо індекс вершини 7 - він дорівнюватиме значенню 4 (мал. 73, а). Продовжуючи пе регляд 7-го рядка таблиці суміжності, «зустрінемо» нову вер шину 8. Допишемо її у стек під порядковим номером 6 і далі перейдемо до неї (мал. 73, б).
З вершини 8 першою побачимо вершину 3. Оскільки вона бу ла відвідана раніше, то можна зробити спробу перевизначити індекс вершини 8. Згідно з нашим алгоритмом тепер він дорів нюватиме значенню 4 (мал. 74, а). Чи можна покращити зна-
8
7
3^
І |
2 |
3 |
4 |
5 |
£>* |
7 |
8 |
6_ |
І |
2 |
3 |
4 |
5 |
6* |
7 |
8 |
2 |
4 |
4 |
5 |
1 |
3 |
5 |
0 |
_5 |
2 |
4 |
4 |
5 |
1 |
3 |
5 |
6 |
1 |
1 |
3 |
4 |
9 |
1 |
4 |
9 |
1 |
1 |
3 |
4 |
9 |
1 |
4 |
9 |
б) Мал. 73
123
8 
(_
6 |
I 2 3 |
4 |
5 |
6* 7 |
S |
|
І 2 |
3 |
•1 |
5 6 7 8 |
|||||||
|
2 |
4 |
4 |
5 |
1 |
3 |
5 |
6 |
|
2 |
4 |
4 |
5 |
1 |
3 |
5 |
6 |
|
1 |
1 |
3 |
4 |
9 |
1 |
4 |
4 |
|
1 |
1 |
3 |
4 |
9 |
1 |
4 |
4 |
a)
Мал.
чення індексу вершини 8, адже ми не завершили перегляд 8-го рядка таблиці суміжності? Ні, оскільки наступна видима вер шина з вершини 8 є 7. Однак, хоча її порядковий номер 5 мен ший за порядковий номер 6 вершини 8, індекс вершини 8, що вже дорівнює 4, менший за порядковий номер вершини 7.
На цьому перегляд вершин з вершини 8 завершується, і но вих вершин нам не трапилося. Це тупик. Повертаємося у стеку до вершини 7 і розглядаємо ребро (7,8). Для того щоб вершина 7 була точкою з'єднання, необхідно, щоб її порядковий номер не перевищував індекс вершини 8 (order7 =% md8 ). Як видно з малюнка 74, б, у нашій ситуації цього не відбувається. Тому можна стверджувати, що ми потрапили в тупик у середині ком поненти двозв'язності. У цьому разі можна спробувати перевизначити індекс вершини 7, якщо inds < ind1. У нашому разі ця нерівність не виконується (4 = 4), тому все залишається без змін (мал. 74, б).
Із тупика, що утворився у вершині 7, повертаємося у стеку до вершини 3. Розглядаємо ребро (3,7). Але тепер уже вико нується нерівність orderг ^ ind7 (4 ^ 4), тому вершина 3 є точкою з'єднання (мал. 75, а). Повертаємося у вершину 6, що передує вершині 3 у стеку. Ця вершина також тупикова, і тому розгля немо ребро (6,3). Для вершин цього ребра стверджується нерівність order^ < indz (3 < 3), тому і вона є точкою з'єднання (мал. 75, б).
Переглядаючи решту ребер, які існують з вершини 6 і мають номери, більші за 3, знайдемо ребро (6,5). Це існуюче ребро могло б поправити значення індексу вершини 6, якби викона лася умова (orderb < order6) and (orderh < ind6). Однак другий операнд цього складеного логічного виразу у наглому випадку
124
її.1 8„« а: 8 6 #
к |
|
|
|
|
|
|
|
|
к |
|
|
|
|
|
ІК |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
8 |
|
|
|
|
|
|
|
|
8 |
|
|
|
|
|
|
|
|
" 4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
7 |
|
|
|
|
|
|
|
|
7 |
4* |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
З |
|
|
|
|
|
|
|
||
6^ |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
І |
2 3 4 5 6 7 8 |
А |
/ 2 3 4 5 6' 7 8 |
|||||||||||||||
1 |
2 |
4 |
4 |
5 |
1 |
3 |
5 |
6 |
|
2 |
4 |
4 |
5 |
1 |
3 |
|
5 |
6 |
_5 |
1 |
1 |
3 |
4 |
9 |
1 |
4 |
4 |
|
1 |
1 |
3 |
4 |
9 |
1 |
|
4 |
4 |
а) |
|
|
|
|
|
|
|
|
б) |
|
|
|
|
|
|
|
|
|
Мал. 75
набуває значення false, тому ніяких змін для вершини 6 не відбувається.
У стеку залишилося дві вершини 1 і 5. Логічно, що ми повер таємося у вершину 1 і розглядаємо ребро (1,6) (мал. 76, а). Для вершин цього ребра умова orderг =* ind6 не виконується, тому вершина 1 не є точкою з'єднання. Спробуємо скоректувати зна чення її індексу. Для цього повинна виконатися умова ind6 < indv Цього не відбувається, оскільки їхні індекси однакові, тому і ніяких змін також немає.
Потрапивши у вершині 1 в тупик, переходимо до вершини 5 і розглядаємо ребро (5,1) з метою визначення, чи не є верши на 5 точкою з'єднання. Для цього повинна виконатися умова order5 ^ indv Згідно з малюнком 76, a order5 = 1, ind5 = 1, тобто
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
1 |
2 |
3 |
4 |
5 |
6* |
7 |
8 |
2 |
4 |
4 |
5 |
1 |
3 |
5 |
6 |
LsJ |
2 |
4 |
4 |
5 |
1 |
3 |
5 |
6 |
1 |
1 |
3 |
4 |
9 |
1 |
4 |
4 |
1 |
1 |
3 |
4 |
1 |
1 |
4 |
4 |
б)
Мал. 76
125
умова виконується. Однак вершина 5 не є точкою з'єднання, оскільки ребро (5,1) містить стартову вершину, і ми повернули ся у неї, пройшовши усі вершини графа (мал. 76, б). Згідно з на шим алгоритмом виконується умова (top = 1) and (s = []), а це є умовою завершення алгоритму.
Пояснимо момент завершення алгоритму детальніше. Вико нання умови (top = 1) and (s = []) говорить про те, що ми, про йшовши всі вершини графа, повернулися у стартову вершину. Проаналізуємо ситуацію, коли стартова вершина є точкою з'єднання. На якому кроці виконання алгоритму ми зможемо це визначити? Для цього звернемося до малюнка 65. Нехай стартовою вершиною буде вершина 6. Скільки разів ми маємо нагоду розглянути цю вершину протягом виконання алгорит му? Перший раз, коли ми з неї стартуємо і заходимо у компо ненту двозв'язності, що містить вершини 1, 2 та 5. Другий раз - на зворотному шляху, під час переходу до іншої компоненти двозв'язності, що складається із вершин 3, 7 та 8, ми знову пройдемо до вершини 6 і саме в цей момент визначимо, що вона є точкою з'єднання. Таким чином, ми вже побували у вершині 6 двічі і це дало змогу визначити її належність множині точок з'єднання. До речі, слід звернути увагу на те, що в обох цих випад ках на поточний момент ще не всі вершини графа були нами пройдені. Отже, при завершенні алгоритму і поверненні у стар тову вершину втретє необхідність у перевірці її як точки з'єднан ня відпадає. Ознаками цього є те, що порядковий номер верши ни стеку дорівнює 1 і всі вершини заданого графа переглянуті.
Після такого детального розбору алгоритму визначення то чок з'єднання у заданому зв'язному графі можна переходити до його реалізації мовою програмування. По-перше, необхідно перевірити роботу алгоритму, а по-друге, під час реалізації випливають деякі цікаві нюанси, які необхідно врахувати для коректної роботи програми, але які від нас, на перший погляд, приховані в описі алгоритму у словесному його представленні.
Фрагмент програми, що безпосередньо реалізує алгоритм визначення точок з'єднання у заданому зв'язному графі, може виглядати так:
while (top <> 0) and flag do |
{Пошук точок з'єднання виконується,} |
begin |
{поки остаточно не повернемося до початку стеку.} |
|
{Визначення вершини графа і, з якої починається} |
і := stack[top]; |
{пошук існуючого ребра.} |
repeat |
{Пошук вершини/, для якої існує ребро (І,])•} |
І inc(j) |
|
until (a[i,j]=1) or (j>n); |
|
if j > n |
{Якщо ребро не знайдено, то це тупик} |
then |
|
if top > 1 |
{і якщо ми не знаходимося на початку стеку, то} |
126