1. Процедура пошуку в глибину

Анотація: Процедура пошуку в глибину. DFS-дерево. Глибинна нумерація. Побудова каркаса. Шарніри.

Процедура пошуку в глибину

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

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

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

Головна відмінність від пошуку в ширину полягає в тому, що при пошуку в глибину в якості активної вибирається та з відкритих вершин, яка переглянуло останньої. Для реалізації такого правила вибору найбільш зручною структурою зберігання безлічі відкритих вершин є стек: відкриваються вершини складаються в стек в тому порядку, в якому вони відкриваються, а в якості активної вибирається остання вершина. Схематично це показано на Мал. 5.1 .

Позначимо стек для відкритих вершин через , Інші позначення зберігають той же сенс, що і в попередньому розділі. через позначається верхній елемент стека (тобто останній елемент, доданий до стека). Тоді процедура обходу однієї компоненти зв'язності методом пошуку в глибину зі стартовою вершиною може бути записана наступним чином (DFS - Depth First Search).

Procedure DFS (a)

1. відвідати вершину
2. 
3. while do
4. 
5. if є недосліджене ребро
6. then досліджувати ребро
7. if вершина нова
8. then відвідати вершину
9. 
10. else видалити з

Ще раз звернемо увагу на основна відмінність цієї процедури від аналогічної процедури пошуку в ширину. При пошуку в ширину вершина, ставши активною, залишається нею, поки не буде повністю досліджена її околиця, після чого вона стає закритою. При пошуку в глибину, якщо в околиці активної вершини виявляється нова вершина , то поміщається в стек і при наступному повторенні циклу while стане активною. При цьому залишається в стеку і через якийсь час знову стане активною. Інакше кажучи, ребра, інцидентні вершині , Будуть досліджені не підряд, а з перервами.

Алгоритм обходу всього графа - той же, що і в разі пошуку в ширину (алгоритм 1 "Пошук в ширину" ), Тільки потрібно чергу замінити стеком, а процедуру BFS - процедурою DFS.

Властивості 1 і 2 пошуку в ширину, відмічені в попередньому розділі, зберігаються і для пошуку в глибину. Залишається вірною і оцінка трудомісткості , Але її доказ вимагає дещо інших міркувань, так як кожна вершина тепер може ставати активної кілька разів. Однак кожне ребро розглядається тільки два рази (один раз для кожної инцидентной йому вершини), тому в операторі if в рядку 5 гілка then (рядки 6-9) повторюється раз. У цьому ж операторі гілка else (рядок 10) повторюється раз, так як кожна вершина може бути видалена з стека тільки один раз. В цілому виходить , Причому залишаються справедливими зроблені в "Пошук в ширину" зауваження про умови, при яких має місце ця оцінка.