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

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

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

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

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

Після того, як з алгоритмом розібрались, перейдемо до розгляду особливостей отриманого дерева обходу в глибину. Як уже зазначалося вище, в додаток до ребер дерева в ньому присутні ще три типи ребер. Це зворотні, прямі і поперечні ребра.

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

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

Побудувати дерево пошуку в глибину для орієнтованого графа наступного вигляду:

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

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

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

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

Але виходячи з того що серед його вершин містяться ще не пройдені, то вибравши одну з них, наприклад, вершину під номером «5», продовжимо обхід в глибину з неї. В результаті, для заданого орграфа, отримаємо наступне дерево пошуку в глибину (ребра  і  являються ребрами дерева, а ребра  і  – поперечними).

Дерево пошуку в глубину заданого орієнтованого графа

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