Пошук в глибину (або обхід в глибину) є одним з основних і найбільш часто вживаних алгоритмів обходу всіх вершин і ребер графа. Згідно з цим алгоритмом обхід здійснюється за наступним правилом: у графі вибираємо довільну вершину, наприклад
, і починаємо з неї пошук. Початкова вершина
(називається коренем пошуку в глибину) після цього вважається пройденою. На наступному кроці, вибираємо ребро
, інцидентне вершині
(орієнтуємо при цьому його напрямок з
в
), і з його допомогою, переходимо у вершину
. Відмітимо, що ребро
після цих дій вважається переглянутим і називається ребром дерева, а вершина
називається батьківською по відношенню до вершини
.
Пошук в глибину в неорієнтованому графі
У загальному випадку, коли ми перейшли в будь-яку вершину графа, в нашому випадку це вершина , виникають два варіанти можливих дій:
- Якщо всі ребра, інцидентні
, вже переглянуті, то повертаємося до батьківської вершини для
і продовжуємо пошук з цієї вершини. Вершина
з цього моменту називатиметься повністю сканованою.
- Якщо існують не переглянуті ребра, інцидентні
, то вибираємо одне з таких ребер, наприклад,
і орієнтуємо його з
в
. Ребро
з цього моменту вважатиметься переглянутим. При цьому, необхідно розглянути два випадки: якщо
раніше не була пройдена, то використовуючи ребро
переходимо у вершину
і продовжуємо пошук з неї. В цьому випадку ребро
називається ребром дерева, а вершина
– батьком вершини
; якщо
раніше була пройдена, то продовжуємо пошук іншого не пройденого ребра, інцидентного
. В цьому випадку ребро
називається зворотним ребром.
Зауваження: під час пошуку в глибину, коли вершину проходять вперший раз, їй зіставляється ціле число
, якщо
є
-ю по порядку проходження вершиною і яке називається глибиною
. Ясно, що глибина вказує порядок, в якому проходять вершини при пошуку в глибину.
Обхід графа в глибину завершується, коли ми повертаємося в корінь і всі вершини графа пройдені. Якщо після повернення в корінь залишаються не пройдені вершини, можна вибрати одну з них і повторювати процес, і робити так до тих пір, поки не пройдемо всі вершини графа.
З всього сказаного вище можна зробити висновок, що пошук в глибину розбиває ребра графа на ребра дерева і зворотні ребра. Легко помітити, що ребра дерева утворюють остов графа
. Також хочеться зазначити, що пошук в глибину вводить орієнтацію на ребра графа
. Одержуваний в результаті орієнтований граф ми будемо позначати через
. Ребра дерева з орієнтацією утворюватимуть орієнтований остов
. Цей орієнтований остов будемо називати деревом пошуку в глибину. Відмітимо, що спосіб проходження графа з допомогою даного дереве не є єдиним, так як ребра, інцидентні вершині, можуть вибиратись для розгляду в довільному порядку.
Обхід графа в глибину – приклад:
Використовуючи розглянутий алгоритм побудувати дерево пошуку в глибину наступного неорієнтованого графа:
Неорієнтований граф задачі
Отже, починаючи з довільно обраної вершини, наприклад вершини номер «1» рухаємося по першому зустрічному нам ребру . Так як вершину «2» ми ніколи раніше не відвідували, залишаємося в «2» і проходимо по першому не пройденому ребру, інцидентному «2», а саме
. Тепер у вершині «3» першим не пройденим ребром являється ребро
. Проходимо його і виявляємо, що вершина «1» вже відвідувалася раніше. Тому повертаємося в «3» і помічаємо ребро
як зворотне (пунктирною лінією). Повернувшись в вершину «3», шукаємо інше не пройдене ребро і йдемо по першому зустрічному з них, скажімо
. Так як «4» – нова вершина, залишаємося в ній і шукаємо не пройдене ребро. В даному випадку таким являється ребро
. Оскільки вершина «2» відвідувалася раніше, позначати ребро
пунктирною лінією і повертаємося в «4». Через те, що не пройденних ребер, інцидентних «4», не залишилось, поверненні в «3».
Побудова дерева обходу в глубину для неорієнтованого графа
У «3» виявляємо не пройдене ребро і проходимо його. Оскільки «5» – нова вершина, залишаємося в ній і шукаємо не прйдене інцидентне їй ребро, яким являється ребро
. Так як «1» – вже пройдена вершина, помічаємо ребро
пунктирною лінією. Тепер вершина «5» повністю переглянута, що свідчить про те, що необхідно повернутись у батьківську по відношенню до неї, тобто у вуршину «3». У «3» немає ребер, що залишилися не пройденими, тому, аналогічним чином, рухаємося назад в «2» і, нарешті, в «1». Всі ребра, інцидентні «1», пройдені, що означає кінець процедури.