Використання обходу в глибину для пошуку циклу
[Ред] Алгоритм
Будемо вирішувати завдання за допомогою пошуку в глибину.
У разі орієнтованого графа зробимо серію обходів. Тобто з кожної вершини, до якої ми ще жодного разу не приходили, запустимо пошук в глибину, який при вході в вершину буде фарбувати її в сірий колір, а при виході з неї - в чорний. І, якщо алгоритм намагається піти в сіру вершину, то це означає, що цикл знайдений.
У разі неорієнтованого графа. одне ребро не повинно зустрічатися в циклі двічі за визначенням. Тому необхідно додатково перевіряти, що поточний розглядається з вершини Ребров не є багаторазовим тим ребром, по якому ми прийшли в цю вершину.
Зауважимо, що, якщо в графі є вершини з петлями, то алгоритм буде працювати коректно, так як при запуску пошуку в глибину з такої вершини, знайдеться ребро, що веде в неї ж, а значить ця петля і буде циклом.
Для відновлення самого циклу досить при запуску пошуку в глибину з чергової вершини додавати цю вершину в стек. Коли пошук в глибину знайшов вершину, яка лежить на циклі, будемо послідовно виймати вершини з стека, поки не зустрінемо знайдену ще раз. Все вийняті вершини будуть лежати на шуканому циклі.
Асимптотика пошуку циклу збігається з асимптотикою пошуку в глибину -.
Момент знаходження циклу: сині ребра - вже пройдені, червоне ребро веде в сіру, вже пройдену, вершину.
[Ред] Доказ
Нехай дано граф. Запустимо. Розглянемо виконання процедури пошуку в глибину від деякої вершини. Так як всі сірі вершини лежать в стеці рекурсії, то для них вершина досяжна, так як між сусідніми вершинами в стеці є ребро. Тоді, якщо з даної вершини існує ребро в сіру вершину, то це означає, що з вершини існує шлях в і з вершини існує шлях в складається з одного ребра. І так як обидва ці шляхи не перетинаються, то цикл існує.
Доведемо, що якщо в графі існує цикл, то його завжди знайде. Нехай - перша вершина належить циклу, розглянута пошуком в глибину. Тоді існує вершина, що належить циклу і має ребро в вершину. Так як з вершини в вершину існує білий шлях (вони лежать на одному циклі), то по лемі про білих шляхах під час виконання процедури пошуку в глибину від вершини, вершина буде сірою. Так як з є ребро в, то це ребро в сіру вершину. Отже знайшов цикл.