Розглядаючи алгоритм обходу орієнтованого графа в глибину ми звертали увагу на те, що більшість задач, що стосуються графів такого типу, вирішуються з використанням даного алгоритму. Сьогодні розглянемо задачу, яка полягає у визначенні того, чи являється орієнтований граф ациклічним (нагадаємо, що орієнтований граф називають ациклічним, якщо в ньому немає циклів; циклом в орієнтованому графі називається шлях, що веде з вершини в саму себе), і покажемо, яким чином дана задача вирішується з допомогою глибинного обходу графа.
Отже, розглянемо деякий орієнтований граф . Для того, щоб перевірити даний граф на наявність циклів, виконуємо глибинний обхід всіх його вершин. В результаті, отримаємо дерево обходу в глибину. Якщо в побудованому дереві зустрінеться хоча б одне зворотне ребро, то ясно, що орієнтований граф має цикл. Справедливе і обернене твердження, тобто, якщо в орієнтованому графі є цикл, тоді зворотне ребро обов’язково зустрінеться при його обході методом пошуку в глибину. Щоб довести це, припустимо, що орієнтований граф має цикл.
Перевірка орієнтованого графа на наявність циклів
Нехай при обході даного графа методом пошуку в глибину вершині присвоєно найменшу глибину обходу серед усіх вершин, що становлять цикл. Розглянемо ребро , що належить цьому циклу. Оскільки вершина входить в цикл, то вона повинна бути нащадком вершини в побудованому дереві обходу в глибину. Тому ребро не може бути поперечним. Але, виходячи з того, що глибина обходу вершини більша за глибину обходу вершини то ребро також не може бути ні ребром дерева ні прямим ребром. Звідси, ребро є зворотним, як показано на малюнку, що міститься вище.
Перевірка орієнтованого графа на наявність циклів – приклад:
Визначити, чи являється орієнтований граф, який зображено на наступному малюнку, ациклічним.
Орієнтований граф задачі
Для цього, на першому кроці, побудуємо його дерево обходу в глибину (яким чином це реалізується можна переглянути перейшовши за посиланням що міститься вище). В результаті будемо мати.
Дерево обходу в глубину заданого орієнтованого графа
Після цього, переглянувши отримане дерево бачимо, що серед його ребер містяться два, які відносяться до класу «зворотне ребро» (позначаються пунктирною лінією чорного кольору). Це ребра та . Звідси, приходимо до висновку, що заданий орієнтований граф містить два цикли ( і ), що свідчить про те, що він не є ациклічним.