Обхід графа в глибину

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

Пошук в глибину в неорієнтованому графі

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

1. Якщо всі ребра, інцидентні , вже переглянуті, то повертаємося до батьківської вершини для  і продовжуємо пошук з цієї вершини. Вершина  з цього моменту називатиметься повністю сканованою.
2. Якщо існують не переглянуті ребра, інцидентні , то вибираємо одне з таких ребер, наприклад,  і орієнтуємо його з  в . Ребро  з цього моменту вважатиметься переглянутим. При цьому, необхідно розглянути два випадки: якщо  раніше не була пройдена, то використовуючи ребро  переходимо у вершину  і продовжуємо пошук з неї. В цьому випадку ребро  називається ребром дерева, а вершина  – батьком вершини ; якщо  раніше була пройдена, то продовжуємо пошук іншого не пройденого ребра, інцидентного . В цьому випадку ребро  називається зворотним ребром.

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

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

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

Обхід графа в глибину – приклад:

Використовуючи розглянутий алгоритм побудувати дерево пошуку в глибину наступного неорієнтованого графа:

Неорієнтований граф задачі

Отже, починаючи з довільно обраної вершини, наприклад вершини номер «1» рухаємося по першому зустрічному нам ребру . Так як вершину «2» ми ніколи раніше не відвідували, залишаємося в «2» і проходимо по першому не пройденому ребру, інцидентному «2», а саме . Тепер у вершині «3» першим не пройденим ребром являється ребро . Проходимо його і виявляємо, що вершина «1» вже відвідувалася раніше. Тому повертаємося в «3» і помічаємо ребро  як зворотне (пунктирною лінією). Повернувшись в вершину «3», шукаємо інше не пройдене ребро і йдемо по першому зустрічному з них, скажімо . Так як «4» – нова вершина, залишаємося в ній і шукаємо не пройдене ребро. В даному випадку таким являється ребро . Оскільки вершина «2» відвідувалася раніше, позначати ребро  пунктирною лінією і повертаємося в «4». Через те, що не пройденних ребер, інцидентних «4», не залишилось, поверненні в «3».

Побудова дерева обходу в глубину для неорієнтованого графа

У «3» виявляємо не пройдене ребро і проходимо його. Оскільки «5» – нова вершина, залишаємося в ній і шукаємо не прйдене інцидентне їй ребро, яким являється ребро . Так як «1» – вже пройдена вершина, помічаємо ребро  пунктирною лінією. Тепер вершина «5» повністю переглянута, що свідчить про те, що необхідно повернутись у батьківську по відношенню до неї, тобто у вуршину «3». У «3» немає ребер, що залишилися не пройденими, тому, аналогічним чином, рухаємося назад в «2» і, нарешті, в «1». Всі ребра, інцидентні «1», пройдені, що означає кінець процедури.

Блок-схема алгоритму обходу графа в глибину