Пошук циклу у графі
Нехай дано орієнтований або неорієнтований граф без петель і кратних ребер. Потрібно перевірити, чи є він ациклічним, а якщо не є, то знайти будь-який цикл.
Вирішимо цю задачу за допомогою пошуку в глибину за O (M).
Алгоритм
Зробимо серію пошуків в глибину в графі. Тобто з кожної вершини, до якої ми ще жодного разу не приходили, запустимо пошук в глибину, який при вході в вершину буде фарбувати її в сірий колір, а при виході - у чорний. І якщо пошук в глибину намагається піти в сіру вершину, то це означає, що ми знайшли цикл (якщо граф неорієнтований, то випадки, коли пошук в глибину з якоїсь вершини намагається піти в предка, не рахуються).
Сам цикл можна відновити проходом по масиву предків.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.