Алгоритмы
Cycle Detection: Обнаружение циклов
Цели урока
- Понять практическую важность обнаружения циклов
- Различать подходы для ориентированных и неориентированных графов
- Освоить DFS с тремя цветами для ориентированных графов
- Реализовать поиск цикла в неориентированном графе через DFS и Union-Find
- Применять алгоритм Флойда для linked list с O(1) памятью
Предварительные знания
- DFS (поиск в глубину)
- Представление графов (списки смежности)
- Linked list (базовое понимание)
Обнаружение циклов критично для многих систем.
- Выявление deadlock'ов в операционных системах
- Валидация зависимостей (npm, pip)
- Топологическая сортировка (возможна только для DAG)
- Floyd's algorithm - классика собеседований (LeetCode 141, 142)
Черепаха и заяц Флойда и алгоритм Брента
Алгоритм поиска цикла 'черепаха и заяц' приписывают Роберту Флойду, который применял идею двух указателей с разной скоростью ещё в 1960-х годах; широкую известность приём получил после книги Кнута 'The Art of Computer Programming'. Медленный указатель проходит один шаг, быстрый два, и если есть цикл, они неизбежно встретятся. В 1980 году Ричард Брент предложил свой вариант в статье 'An Improved Monte Carlo Factorization Algorithm', который на практике работает быстрее и используется, в частности, в ро-методе Полларда для факторизации чисел.
Зачем искать циклы?
Обнаружение циклов - одна из фундаментальных задач в computer science. Циклы могут быть **проблемой** (deadlock, бесконечный цикл) или **полезной информацией** (обратные связи в системе).
**Метафора: детектив и дорожная карта**
Детектив отслеживает передвижение подозреваемого по городу. Он едет от места к месту. Задача - понять: вернётся ли он когда-нибудь в место, где уже был? Если да - это цикл в маршруте.
Топологическая сортировка (порядок выполнения задач) возможна ТОЛЬКО если в графе зависимостей НЕТ циклов. Такой граф называется DAG (Directed Acyclic Graph).
Другой важный случай - **linked list**. Если в списке есть цикл, попытка пройти до конца приведёт к бесконечному циклу. Нужен способ обнаружить это за O(1) памяти.
Почему топологическая сортировка невозможна при наличии цикла в графе зависимостей?
Цикл создаёт логическое противоречие: A должно быть после B, но B должно быть после A. Нет корректного линейного порядка.
Типы графов и методы поиска циклов
Методы поиска циклов **различаются** для ориентированных и неориентированных графов. Это не вопрос оптимизации - это принципиально разные задачи!
**Неориентированный граф**: ребро A -B означает можно пройти в обе стороны (дорога). Цикл - путь, который возвращается в начальную вершину.
**Ориентированный граф**: ребро A→B означает одностороннюю связь (зависимость, ссылка). Цикл - путь по НАПРАВЛЕНИЮ стрелок, возвращающийся в начало.
Ключевое отличие: в неориентированном графе ребро A -B это ДВА направления. Нужно следить, чтобы не считать возврат по тому же ребру за цикл!
В ориентированном графе ситуация сложнее. Нужно различать **три состояния** вершины, а не два (посещён/не посещён). Почему - разберём далее.
В неориентированном графе с вершинами A, B, C и рёбрами A -B, B -C есть цикл?
Для цикла в неориентированном графе нужен путь, возвращающийся в начало БЕЗ использования одного ребра дважды. A→B→A использует ребро A -B дважды - это не цикл.
Циклы в ориентированном графе: DFS с тремя цветами
Для поиска цикла в **ориентированном** графе нам нужны **три состояния** вершин. Это не оптимизация - с двумя состояниями алгоритм даёт неправильный ответ!
**Метафора: расследование детектива**
Расследуются связи между людьми. Каждый человек может быть в трёх статусах: 1) Ещё не допрошен (БЕЛЫЙ), 2) Сейчас допрашивается, ждут ответов о его связях (СЕРЫЙ), 3) Допрос завершён, все связи проверены (ЧЁРНЫЙ).
**Ключевое понимание**: цикл - это когда мы находим путь К САМИМ СЕБЕ во время текущего обхода. Если вершина уже обработана (ЧЁРНАЯ), значит она не является нашим предком - циклв нет.
ПРАВИЛО: Цикл существует ⟺ мы находим ребро в СЕРУЮ вершину. Серая вершина = наш предок в текущем пути DFS = мы нашли путь назад к себе.
Реализация алгоритма:
Типы рёбер в DFS: Tree edge (в белую), Back edge (в серую) = ЦИКЛ, Forward edge (в чёрную, потомок), Cross edge (в чёрную, не потомок). Только back edge создаёт цикл.
При DFS мы нашли ребро к вершине с цветом BLACK. Что это означает?
BLACK = полностью обработана = не является нашим предком в текущем пути DFS. Это либо forward edge (потомок), либо cross edge (другая ветка). Цикл - только при ребре в GRAY.
Циклы в неориентированном графе
В **неориентированном** графе всё проще: достаточно **двух состояний** (visited/not visited). Но есть нюанс - нужно отслеживать, откуда мы пришли.
Почему два состояния достаточно? В неориентированном графе нет cross edges! Если мы видим посещённую вершину (и это не parent) - мы нашли цикл.
Подвох с мультиграфом (несколько рёбер между вершинами): A═══B. При проверке u !== parent мы пропустим ОДНО ребро к A, но второе ребро создаёт цикл! Для мультиграфа нужно считать индексы рёбер.
**Альтернатива: Union-Find**
Union-Find (Disjoint Set Union) - отличный способ обнаружить цикл при **инкрементальном** построении графа. Добавляем рёбра по одному: если оба конца уже в одной компоненте - ребро создаст цикл!
Union-Find идеален для Kruskal's MST: добавляем рёбра в порядке веса, пропускаем те, что создают цикл. Также используется в алгоритмах кластеризации и connected components.
Почему для неориентированного графа достаточно двух состояний вершин (visited/not visited)?
В неориентированном графе cross edges невозможны (ребро соединило бы вершины в одно поддерево при первом обходе). Поэтому visited + не-parent = гарантированный цикл.
Floyd's Cycle Detection: Черепаха и Заяц
**Алгоритм Флойда** (Tortoise and Hare - Черепаха и Заяц) - гениальный способ обнаружить цикл в **linked list** за O(n) времени и **O(1) памяти**!
**Метафора: бегуны на круговой трассе**
Два бегуна на трассе. Один бежит в 2 раза быстрее другого. Если трасса **линейная** (с финишем), быстрый просто добежит до конца первым. Но если трасса **круговая**, быстрый рано или поздно **догонит** медленного - они окажутся в одной точке!
**Почему это работает математически?**
**Бонус: как найти НАЧАЛО цикла?**
После обнаружения встречи есть короткий трюк: сбрасываем slow на head, и двигаем оба указателя по 1 шагу. Они встретятся ровно в начале цикла!
Алгоритм Флойда работает не только для linked list. Он применим к любой функции f(x), где нужно найти цикл в последовательности x, f(x), f(f(x)), ... Используется в pollard's rho для факторизации!
Алгоритм Флойда обнаруживает только один цикл. Если циклов несколько - нужен DFS
Floyd's работает на связном пути от начала: детектирует первый достижимый цикл. Для нескольких циклов в общем графе - DFS или union-find по всем рёбрам
Классическая задача Флойда предполагает единственный путь (linked list, functional graph). В общих ориентированных графах несколько независимых циклов требуют обхода всех узлов
Какова пространственная сложность алгоритма Floyd's Cycle Detection?
Алгоритм использует только два указателя (slow и fast) - константная память O(1), независимо от размера списка или цикла.
Итоги
- Ориентированные графы: DFS с тремя цветами (WHITE, GRAY, BLACK)
- Back edge (ребро в серую вершину) = цикл
- Неориентированные графы: visited + parent достаточно
- Union-Find: удобен для инкрементального построения
- Floyd's Tortoise and Hare: O(1) память для linked list
Вопросы для размышления
- Как модифицировать алгоритм Флойда, чтобы найти начало цикла, а не только его наличие?
Связи с другими алгоритмами
Обнаружение циклов связано с топологической сортировкой и SCC
- Топологическая сортировка — Возможна только для DAG (без циклов)
- SCC (Tarjan) — Сильно связные компоненты содержат циклы
- Pollard's rho — Использует Floyd's алгоритм для факторизации
Связанные уроки
- alg-13-dfs — Раскраска при DFS находит циклы в орграфах
- alg-18-topological — Топологический порядок существует тогда и только тогда, когда нет цикла
- ds-18-union-find — Union-Find находит цикл при добавлении рёбер
- alg-26-two-pointers — Черепаха и заяц Флойда находят цикл в функциональных графах
- ds-16-graphs-intro