Пошук циклу у графі

Нехай дано орієнтований або неорієнтований граф без петель і кратних ребер. Потрібно перевірити, чи є він ациклічним, а якщо не є, то знайти будь-який цикл.

Вирішимо цю задачу за допомогою пошуку в глибину за O (M).

Алгоритм

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

Сам цикл можна відновити проходом по масиву предків.

Див. також

• Пошук в глибину