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

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

Як і при пошуку в ширину, виявивши (вперше) вершину v, суміжну з u, ми відзначаємо цю подію, вставляючи в поле π [u] значення u. Виходить дерево або кілька дерев, якщо пошук повторюється з декількох вершин.

Говорячи про пошук в глибину, ми завжди припускаємо, що так і робиться (пошук повторюється). Ми отримуємо підграф передування (predecessor subgraph), який має вигляд: Gv = (V, EV), де:

Підграф передування являє собою ліс пошуку в глибину (depth-first forest), що складається з дерев пошуку в глибину (deep-first trees). Алгоритм пошуку в глибину також використовує кольори вершин. Кожна з вершин спочатку біла. Будучи виявленої (discovered), вона стає сірою. Вона стане чорною, коли буде повністю оброблена, тобто коли список суміжних з нею вершин буде переглянутий. Кожна вершина потрапляє рівно в одне дерево пошуку глибину, так що ці дерева не перетинаються.

Крім цього, пошук в глибину ставить на вершинах мітки часу (timestamps). Кожна вершина має дві мітки: в d [v] записано, коли ця вершина була виявлена , а в f [v] - коли була закінчена обробка списку суміжних з v вершин. Ці мітки часу використовуються в багатьох алгоритмах на графах і корисні для аналізу властивостей пошуку в глибину.

В наведеній далі процедурі DFS (Depth-First Search - пошук в глибину) мітки часу d [v] і f [v] є цілими числами від 1 до 2 |V|. Вершина u буде білою до моменту d [u], сірою між d [u] та f [u] і чорною після f [u].

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

DFS $ (G) $

1for (для) всіх вершин $ u \ in V [G] $

2 \ hspace {lcm} do $ color [u] \ leftarrow $ білий

3 \ hspace {2cm> $ \ pi [u] \ leftarrow NIL $

4 $ time \ leftarrow 0 $

5for (для) всіх вершин $ u \ in V [G] $

6 \ hspace {lcm} do if $ color [u] = $ білий

7 \ hspace {2cm> then DFS-Visit $ (u) $

Рис. 1. 3a. Виконання алгоритму DFS для орієнтованого графа

Після перегляду кожне ребро стає або сірим (якщо воно включається в дерево пошуку) або пунктирним (зворотні ребра помічені буквою В (back), перехресні - буквою С (cross), прямі - буквою F (forward)). У кожної вершини показані часи початку і кінця обробки.

DFS-Visit (u)

1 $ color [u] \ leftarrow $ біла вершина $ u $ була білою

2 $ d [u] \ leftarrow time \ leftarrow time + l $

3 \ textsc {for} (для) всіх $ v \ in Adj [u] $ обробити ребро $ (u, v) $

4 \ hspace {lcm} \ textsc {do if} $ color [v] = $ білий

5 \ hspace {2cm} \ textsc {then} $ \ pi [v] \ leftarrow u $

6 \ hspace {3cm} DFS-Visit $ (v) $

7 $ color [u] \ leftarrow $ вершина оброблена

8 $ f [u] \ leftarrow time \ leftarrow time + l $

На рисунку 1. 3b. показана робота процедури DFS на графі

У рядках 1-3 всі вершини фарбуються в білий колір. в поле π поміщається NIL. У рядку 4 встановлюється початковий (нульовий) час. У рядках 5-7 викликається процедура DFS-Visit для всіх вершин (які залишилися білими до моменту виклику - попередні виклики процедури могли зробити їх чорними). Ці вершини стають корінням дерев пошуку в глибину.

В момент виклику DFS-Visit (m) вершина u - біла. У рядку 1 вона стає сірою. У рядку 2 час її виявлення заноситься в d [u] (до цього лічильник часу збільшується на 1). У рядках 3-7 проглядаються суміжні з u вершини. Процедура DFS-Visit викликається для тих з них, які виявляються білими до моменту виклику. Після перегляду всіх суміжних з u вершин ми робимо вершину u чорною та записуємо в f [u] час цієї події.

Підрахуємо загальне число операцій при виконанні процедури DFS. Цикли в рядках 1-3 і 5-7 вимагають О (С) часу (крім викликів DFS-Visit). Процедура DFS-Visit викликається рівно один раз для кожної вершини (їй передається біла вершина, і вона відразу ж робить її сірої). Під час виконання DFS-Visit (u) цикл в рядках 3-6 виконується | Adj [u] |. Оскільки | Adj [v] | = Q (E), час виконання рядків 3-6 процедури DFS-Visit становить θ (E). В сумі виходить час θ (С + Е).

Перш за все зазначимо, що підграф передування (складений з дерев пошуку в глибину) в точності відповідає структурі рекурсивних викликів процедури DFS-Visit. Саме, u = π [v] тоді і тільки тоді, коли стався виклик DFS-Visit (u) під час перегляду списку суміжних з u вершин.

Інша важлива властивість полягає в тому, що часи виявлення і закінчення обробки утворюють правильну дужкову структуру (parenthesis structure). Позначаючи виявлення вершини та дужки з поміткою u, а закінчення її обробки - закривається з тією ж позначкою, та перелік подій буде правильно побудованим вираженням.

Щоб довести ці та інші властивості, ми повинні міркувати по індукції. При цьому, доводячи необхідну властивість рекурсивної процедури DFS-Visit, ми припускаємо, що рекурсивні виклики цієї процедури володіють обраним властивістю.

Переконаємося спочатку, що виклик DFS-Visit (m) для білої вершини і робить чорною цю вершину і всі білі вершини, доступні з неї по білим шляхам (в яких всі проміжні вершини також білі), і залишає сірі та чорні вершини без змін.

Справді, рекурсивні виклики в рядку 6 виконуються лише для білих вершин, які є суміжними з u. Якщо якась вершина w була зафарбована в ході цих викликів, то (по індуктивному припущенню) вона була доступна по білому шляху з однієї з білих вершин, суміжних з u, тому доступна по білому шляху з u.

Навпаки, якщо вершина w доступна по білому шляху з u, то вона доступна по білому шляху з якоїсь білої вершини v, суміжній з u (подивимося на перший крок шляху). Будемо вважати, що v - перша з таких вершин (у порядку перегляду в рядку 3). В цьому випадку всі вершини білого шляху з v в w залишаться білими до моменту виклику DFS-Visit (u), оскільки вони недоступні за білим шляхам з попередніх v вершин (інакше w була б також доступна). За індуктивному припущенню w стане чорною після виклику DFS-Visit (u).

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

Аналогічні міркування по індукції дозволяють встановити, що виклик DFS-Visit (m) міняє поля π [v] для всіх забарвлюваних вершин v, відмінних від u, тим самим формуючи з них дерево з коренем в u, а також додає до описаного вище протоколу з дужок та позначками правильного дужкового виразу, зовнішні дужки якого мають позначку u, а всередині знаходяться дужки з позначками, відповідними забарвлюваним вершинам.

При пошуку в глибину в орієнтованому або неорвієнтованому графі G = (V, Е) для будь-яких двох вершин u та v виконується рівно одне з наступних трьох тверджень:

відрізки / [u]] і [[u], / [u]] не перетинаються.

відрізок [d [u], f [u]] цілком міститься всередині відрізка [d [v], f [v]] ні - нащадок v в дереві пошуку в глибину.

відрізок [d [v], f [v]] цілком міститься всередині відрізка [d [u], f [u]] та v - нащадок u в дереві пошуку в глибину.

⇐ Предыдущая 1 2 345 Следующая ⇒