1. DFS-дерево Пошук в глибину можна застосувати для знаходження компонент зв'язності графа або для побудови...
2. побудова каркаса

DFS-дерево

Пошук в глибину можна застосувати для знаходження компонент зв'язності графа або для побудови каркаса точно таким же чином, як пошук в ширину. Поняття прямого і зворотного ребра визначаються так само, як в попередньому розділі і так само доводиться, що прямі ребра при пошуку в глибину утворюють каркас графа. Для зв'язкового графа каркас, одержуваний пошуком в глибину, називається DFS-деревом. DFS-дерево розглядається як кореневе дерево з коренем у стартовій вершині . Це дерево має особливі властивості, на використанні яких засновані численні застосування методу пошуку в глибину. Розглянемо найбільш важливе з цих властивостей.

Щодо будь-якого кореневого остовного дерева все ребра графа, що не належать дереву, можна розділити на дві категорії. Ребро назвемо поздовжнім, якщо одна з його вершин є предком інший, в іншому випадку ребро назвемо поперечним. У прикладі на Мал. 5.2 ребра каркаса виділені жирними лініями, корінь - чорним кружком. Зворотні ребра показані тонкими лініями, з них поздовжніми є ребра , , , А поперечними - ребра , , .

Теорема 1. нехай - зв'язний граф, - DFS-дерево графа . тоді щодо всі зворотні ребра є поздовжніми.

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

нехай тепер - зворотне ребро. Кожна з вершин і в ході роботи алгоритму коли-небудь виявиться в стеці. Припустимо, виявиться там раніше, ніж . Розглянемо крок алгоритму, на якому поміщається в стек. У цей момент ще перебуває в стеці. Дійсно, вершина виключається з стека тільки тоді, коли в її околиці немає невідвіданих вершин. Але безпосередньо перед приміщенням в стек вершина є новою і належить околі вершини . Таким чином, вершина лежить на шляху, що належить дереву і з'єднує вершини і . Але це означає, що вершина є предком вершини в дереві і, отже, ребро - поздовжнє.

Таким чином, каркас, зображений на Мал. 5.2 , Не міг бути побудований методом пошуку в глибину. До речі, він не міг бути побудований і за допомогою пошуку в ширину (чому?).

глибинна нумерація

Зважаючи на важливість цього методу опишемо ще два варіанти алгоритму пошуку в глибину. Перший з них - рекурсивний, і, як зазвичай, рекурсія дає можливість представити алгоритм в найбільш компактній формі. Для того щоб алгоритм виконував якусь корисну роботу, будемо нумерувати вершини в тому порядку, в якому вони зустрічаються при обході. Номер, який отримують вершиною , Позначається через і називається її глибинним номером. спочатку вважаємо для всіх . Це нульове значення зберігається до тих пір, поки вершина не стає відкритою, в цей момент їй присвоюється її справжній глибинний номер. Таким чином, немає необхідності в будь-якої спеціальної структурі для запам'ятовування нових вершин - вони відрізняються від всіх інших нульовим значенням . Мінлива зберігає поточний номер. Рекурсивна процедура DFSR обходить одну компоненту зв'язності, а алгоритм 1 обходить весь граф і привласнює вершин глибинні номера.

Алгоритм 1. Пошук в глибину з обчисленням глибинних номерів - рекурсивний варіант

1. for do
2. 
3. for do
4. if then

Procedure

1. 
2. 
3. for do
4. if then

побудова каркаса

Наступний варіант алгоритму пошуку в глибину відрізняється тим, що не використовує стека для зберігання відкритих вершин. Стек потрібен для того, щоб в момент, коли околиця активної вершини досліджена і необхідно зробити "крок назад", можна було визначити вершину, в яку потрібно повернутися. Але це та вершина, яка є батьком вершини в DFS-дереві. Тому, якщо рішення задачі передбачає побудову DFS -дерева, то це дерево можна використовувати і для організації "зворотних рухів" в процесі обходу. Описуваний нижче алгоритм будує каркас довільного графа, кожна компонента зв'язності цього каркаса є DFS-деревом відповідної компоненти зв'язності графа. через позначається батько вершини в цьому DFS-дереві, при цьому для кореня дерева (стартової вершини) вважаємо . Тут і далі в описах алгоритмів інструкція "відкрити (закрити) вершину" означає, що вершина якимось чином позначається як відкрита (закрита).

Алгоритм 2. Пошук в глибину з побудовою каркаса

1. позначити всі вершини як нові
2. for do
3. if вершина нова then

Procedure

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