НОУ ІНТУЇТ | лекція | Три алгоритму на графах

Пошук в глибину і завдання про лабіринті

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

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

перебуваючи в деякій вершині v, йдемо з неї в довільну ще не відвідану суміжну вершину w, якщо такої вершини немає, то повертаємося в вершину, з якої ми прийшли в v.

Алгоритм пошуку в глибину

Вхід: G = (V, E) - неорієнтований граф, представлений списками смежностей: для кожної список Lv містить перелік усіх суміжних з v вершин.

Вихід: NUM [v] - масив з номерами вершин в порядку їх проходження і безліч (деревних) ребер , За якими здійснюється обхід.

алгоритм ПОГ

1. T = {}; NOMER = 1;
2. для кожної вершини покладемо NUM [v] = 0 і позначимо v як "нову";
3. ПОКИ існує "нова" вершина
4. ВИКОНУВАТИ ПОШУК (v).

Основну роль в цьому алгоритмі грає наступна рекурсивна процедура.

Алгоритм ПОШУК (v):

1. помітити v як "стару"; 2. NUM [v] = NOMER; NOMER = NOMER + 1; 3. ДЛЯ КОЖНОЇ w належить Lv ВИКОНУВАТИ 4. ЯКЩО вершина w "нова" 5. ТО 6. {додати (v, w) до T; 7. ПОШУК (w); 8.}

Теорема 11.2. Алгоритм ПОГ обходить (нумерує) всі вершини графа G = (V, E). Якщо G - зв'язний граф, то S = (V, T) - це остов G, якщо граф G не є зв'язковим, то S = (V, T) - це кістяк ліс для G, тобто об'єднання остовних дерев для кожної з компонент зв'язності G.

Доказ Перше твердження випливає з того, що після закінчення алгоритму ПОГ все вершини графа старі, а це значить, що для кожної з них викликалася процедура ПОШУК, яка в стор.2 привласнила номер.

Зауважимо тепер, що якщо ребро (v, w) потрапляє в T, то виклик процедури ПОШУК (w) відбувається після виклику ПОШУК (v) і тому NUM [v] <NUM [w]. Існування циклу в S означало б, що для деякого ребра з T це властивість порушено (чому?). Отже, в S циклів немає.

Нехай G1 = (V1, E1) - зв'язкова компонента G і - перша її вершина, для якої викликається процедура ПОШУК. Тоді для кожної вершини всередині виклику ПОШУК (v1) відбудеться виклик ПОШУК (w).

Це твердження доводиться індукцією по відстані (довжині найкоротшого шляху) від v1 до w.

Якщо ця відстань дорівнює 1, то і розглядається у виклику ПОШУК (v1) в стор.3. Якщо w в цей момент "стара", то, значить, ПОШУК (w) вже викликався. Якщо ж w "нова", то в стор. 7 відбувається виклик ПОШУК (w).

Припустимо тепер, що ПОШУК (u) викликається для всіх вершин u, що знаходяться на відстані k> = 1 від v1, і нехай вершина знаходиться на рсстояніі (k + 1) від v1. Тоді є шлях довжини (k + 1) від v1 до w. Нехай u - це передостання вершина на цьому шляху. Тоді відстань від v1 до u одно k і на нашу предпроложенію в певний момент виконується виклик ПОШУК (u). Так як , То в цьому виклику вершина w в певний момент розглядається в циклі в стор.3. Як і вище, якщо вона в цей момент "стара", то ПОШУК (w) вже викликався. Якщо ж w ще "нова", то в стор.7 відбувається виклик ПОШУК (w).

Також по індукції помічаємо, що якщо виклик ПОШУК (w) стався всередині виклику ПОШУК (v), то в T є шлях з v в w. Отже, граф S1 = (V1, T1), побудований в процесі виклику ПОШУК (v) є деревом з коренем v.

Дерево S = (V, T), яке будується алгоритмом ПОГ, називається глибинним остовом або глибинним остовне деревом графа G. Ребра, що потрапили в безліч T, називаються прямими, а не потрапили в це безліч ребра з безлічі (E \ T) - зворотними. Кожне зворотне ребро (v, w) з'єднує вершину v з її предком w в глибинному остові (див. Задачу 11.8). Тому в початковому графі G воно визначає цикл: від w до v по ребрах дерева T, а потім назад від v до w по ребру (v, w). Тому алгоритм ПОГ можна використовувати для перевірки наявності циклів в G. Ребро (v, w) не додають до T, тобто є зворотним, тоді і тільки тоді, коли в стор.4 виклику ПОШУК (v) виявляється, що вершина w "стара". Тому, додавши в процедуру ПОШУК (v) останній рядок

9. ІНАКШЕ ДРУК (v, w),

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

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

Визначення 11.3. Ребро (v, w) неорієнтованого графа G = (V, E) називається мостом G, якщо при його видаленні з E число зв'язкових компонент графа збільшується, тобто в графі G '= (V, E \ {(v, w)} зв'язкових компонент більше, ніж в G.

З цього визначення, зокрема, випливає, що ребро є мостом тоді і тільки тоді, коли воно не входить ні в який цикл (чому?). Пошук в глибину дозволяє знаходити всі мости графа. По-перше, зауважимо, що будь-який міст (v, w) є ребром глибинного остова, так як іншого шляху, що зв'язує v і w немає. По-друге, якщо це ребро орієнтоване від v до w, то в глибинному кістяку немає зворотних ребер, що з'єднують w і його нащадки з предками w. Ця умова є і достатнім, так як, якщо таких ребер немає, то видалення (v, w) порушить зв'язок між v і w і вони виявляться в різних компонентах зв'язності. Позначимо через ВЕРХ (w) мінімум з NUM [w] і найменшого з номерів вершин, до яких ведуть зворотні ребра від вершин поддерева Tw. Тоді, враховуючи, що зворотні ребра з'єднують нащадків з предками і що номери предків менше номерів нащадків, запропонований критерій можна переформулювати в наступному вигляді.

Теорема 11.3. Ребро (v, w) глибинного остова D = (V, E) неорієнтованого графа G = (V, E) є мостом G тоді і тільки тоді, коли ВЕРХ (w)> NUM [v] або, що еквівалентно, ВЕРХ (w ) = NUM ​​[w].

Обчислення значення ВЕРХ (w) можна організувати в процесі обходу в глибину, використовуючи наступне співвідношення:

Для цього достатньо в рядок 2 алгоритму ПОГ додати початкове присвоєння ВЕРХ (v): = NUM ​​[v], в рядку 7 приписати після ПОШУК (w) привласнення ВЕРХ (v): = min {ВЕРХ (v), ВЕРХ (w)} , що враховує прямі ребра, і додати рядок

9. ІНАКШЕ ВЕРХ (v): = min {ВЕРХ (v), NUM (w)}

для обліку зворотних ребер.

Знаючи значення ВЕРХ (w), неважко виявити всі мости, використовуючи критерій з теореми 11.3.

Приклад 11.2. Застосуємо алгоритм ПОГ до графу G2, зображеному на Мал. 11.3 .

Мал.11.3.

Граф G2

Його уявлення у вигляді списків суміжності має наступний вигляд:

Алгоритм ПОГ викличе процедуру ПОШУК (1). Ця процедура рекурсивно викличе ПОШУК (6) і т.д. Ось структура всіх які утворюються викликів процедури ПОШУК:

Спочатку йдуть "горизонтальні" виклики, потім повернення справа наліво і виклики "по вертикалі". В результаті вершини G2 отримають наступні номери, що відображають порядок їх проходження:

ребра остова , Побудовані в процесі обходу графа, показані на Мал. 11.4 . Стрілки вказують напрямок обходу. У дужках поруч з номером вершини вказано її номер в масиві NUM, тобто номер в порядку обходу алгоритмом ПОГ.

Мал.11.4.

Остовне "глибинне" дерево S = (V, T) графа G2

В процесі побудови цього дерева були визначені наступні зворотні ребра: (8,6), (10,2), (11,9), (5,2) і (4,3). Неважко перевірити, що додавання будь-якого з цих ребер до T призводить до утворення простого циклу.

Використовуючи розширений варіант ПОГ з обчисленням функції ВЕРХ, ми отримаємо наступний результат:

Так як ВЕРХ (2) = NUM ​​[2] = 5 і ВЕРХ (6) = NUM ​​[6] = 2, то по теоремі 11.3 мостами графа G2 є ребра (1,2) і (1,6) та інших мостів у нього немає.

Алгоритм пошуку в глибину часто використовується як основа для різних алгоритмів обробки графів. Замість рядка 6, в котрому вершина v отримує номер NUM (v), можна вставити виклик будь-якої процедури, яка обробляє інформацію, пов'язану з цією вершиною (наприклад, для завдання про лабіринті це може бути перевірка того, що v є виходом з лабіринту). І тоді отриманий варіант алгоритму забезпечить обробку всіх вершин графа.