Поиск цикла в графе: DFS, три цвета, DSU и алгоритм Кана
Как найти цикл в неориентированном и ориентированном графе: DFS с родителем, DSU, три цвета, алгоритм Кана, восстановление самого цикла и разбор Course Schedule. Код на Python.
Коротко
| Граф | Метод | Время | Что даёт |
|---|---|---|---|
| Неориентированный | DFS с родителем | есть ли цикл и сам цикл | |
| Неориентированный | DSU (Union-Find) | первое ребро, замыкающее цикл, работает на потоке рёбер | |
| Ориентированный | DFS, три цвета | есть ли цикл и сам цикл | |
| Ориентированный | Алгоритм Кана | есть ли цикл и вершины, которые «застряли» |
- В неориентированном графе цикл — это ребро в уже посещённую вершину, если это не ребро, по которому мы пришли.
- В ориентированном графе одного
visitedмало: цикл — это ребро в вершину, которая ещё на стеке рекурсии (серая). - Чтобы вернуть сам цикл, храните
parentи при обнаружении обратного ребра пройдите по родителям вверх. - Course Schedule — это вопрос «есть ли цикл в ориентированном графе зависимостей».
Здесь речь о графах общего вида. Если у каждой вершины ровно одно исходящее ребро (связный список, функция next), есть решение за памяти — алгоритм Флойда, он разобран в статье про цикл в связном списке. А как превращать ациклический граф в порядок вершин, подробно описано в топологической сортировке. Эта статья — про сам цикл: как его заметить, как достать и где на этом спотыкаются.
Почему для двух видов графов разные алгоритмы
Возьмём «ромб»: рёбра 0–1, 0–2, 1–3, 2–3.
0
/ \
1 2
\ /
3
Если рёбра неориентированные, это цикл 0–1–3–2–0. Если ориентированные и все идут вниз (0→1, 0→2, 1→3, 2→3), цикла нет: из 3 никуда не уйти, вернуться в 0 нельзя.
При этом DFS в обоих случаях делает одно и то же: из 0 идёт в 1, из 1 в 3, возвращается и идёт в 2, а из 2 видит уже посещённую вершину 3. В неориентированном графе это действительно цикл. В ориентированном — просто второй путь в ту же вершину. Отсюда главное различие:
- неориентированный граф: любое ребро в посещённую вершину, кроме ребра к родителю, замыкает цикл;
- ориентированный граф: цикл замыкает только ребро в вершину, из которой мы ещё не вышли.
Неориентированный граф
DFS с родителем
Идём в глубину и помечаем вершины. Если из вершины v видим посещённую to, есть два варианта: либо to — это вершина, из которой мы пришли в v (ребро уже пройдено, просто в обратную сторону), либо это настоящий цикл.
def has_cycle_undirected(n, edges): graph = [[] for _ in range(n)] for i, (u, v) in enumerate(edges): graph[u].append((v, i)) graph[v].append((u, i)) visited = [False] * n def dfs(v, parent_edge): visited[v] = True for to, eid in graph[v]: if eid == parent_edge: continue # то же самое ребро, по которому пришли if visited[to]: return True if dfs(to, eid): return True return False return any(not visited[v] and dfs(v, -1) for v in range(n)) print(has_cycle_undirected(3, [(0, 1), (1, 2)])) # False print(has_cycle_undirected(3, [(0, 1), (1, 2), (2, 0)])) # True
Обратите внимание: пропускаем не вершину-родителя, а номер ребра, по которому пришли. В учебниках чаще пишут if to == parent: continue — для ответа «да/нет» это тоже работает, но с кратными рёбрами и восстановлением цикла начинаются сюрпризы (о них ниже). Номер ребра снимает вопрос целиком: два ребра 0–1 — это два разных ребра, и вместе они образуют цикл длины 2. Петля 0–0 тоже корректно ловится: вершина видит саму себя уже посещённой.
Внешний цикл по всем вершинам нужен, потому что граф может быть несвязным: цикл может прятаться в компоненте, куда из вершины 0 не попасть.
Проверка без обхода: считаем рёбра
Полезный факт для собеседования. Лес (граф без циклов) из вершин и компонент содержит ровно рёбер. Каждое лишнее ребро создаёт цикл. Значит:
Для связного графа (): цикл есть тогда и только тогда, когда . Это мгновенный ответ в задачах вроде Graph Valid Tree (LeetCode 261): граф — дерево, если и он связен. Компоненты всё равно придётся посчитать обходом или DSU, но условие помогает отсечь очевидные случаи до всякого обхода.
DSU: цикл на потоке рёбер
Второй способ — система непересекающихся множеств. Обрабатываем рёбра по одному: если концы ребра уже в одной компоненте, то путь между ними есть, и новое ребро замыкает цикл. Иначе объединяем компоненты.
def has_cycle_dsu(n, edges): parent = list(range(n)) def find(x): while parent[x] != x: parent[x] = parent[parent[x]] # сжатие путей (halving) x = parent[x] return x for u, v in edges: ru, rv = find(u), find(v) if ru == rv: return True parent[ru] = rv return False
Когда DSU удобнее DFS:
- рёбра приходят по одному, и нужно сказать, какое именно ребро первым создало цикл;
- граф не нужно строить целиком: хватает массива
parent; - нет рекурсии, а значит, нет проблем с глубиной стека.
Классика — Redundant Connection (LeetCode 684): в дерево добавили одно ребро, найдите его. Это ровно тот момент, когда find(u) == find(v):
def find_redundant_connection(edges): parent = list(range(len(edges) + 1)) # вершины нумеруются с 1 def find(x): while parent[x] != x: parent[x] = parent[parent[x]] x = parent[x] return x for u, v in edges: ru, rv = find(u), find(v) if ru == rv: return [u, v] parent[ru] = rv return [] print(find_redundant_connection([[1, 2], [1, 3], [2, 3]])) # [2, 3] print(find_redundant_connection([[1, 2], [2, 3], [3, 4], [1, 4], [1, 5]])) # [1, 4]
Ограничение DSU: он подходит только для неориентированных графов. Для ориентированных «концы в одной компоненте» ничего не говорит о цикле: в ромбе 0→1→3 и 0→2→3 ребро 2→3 соединяет вершины одной компоненты, а цикла нет. Ранги, union by size и прочие оптимизации разобраны в статье про DSU.
Ориентированный граф
Почему одного visited мало
Самая частая ошибка — перенести неориентированный код в ориентированный граф:
def has_cycle_wrong(n, edges): graph = [[] for _ in range(n)] for u, v in edges: graph[u].append(v) visited = [False] * n def dfs(v): visited[v] = True for to in graph[v]: if visited[to] or dfs(to): # ошибка: visited ≠ «на текущем пути» return True return False return any(not visited[v] and dfs(v) for v in range(n)) print(has_cycle_wrong(4, [(0, 1), (0, 2), (1, 3), (2, 3)])) # True, а цикла нет
На ромбе этот код находит «цикл», которого нет: вершина 3 посещена через 1, и ребро 2→3 считается замыкающим. Нам нужно знать не «были ли мы в вершине когда-нибудь», а «находится ли она на текущем пути от корня DFS».
Три цвета
Каждая вершина в одном из трёх состояний:
- белая — ещё не посещали;
- серая — вошли, но ещё не вышли: вершина на стеке рекурсии;
- чёрная — полностью обработана, все потомки просмотрены.
Ребро в серую вершину ведёт назад по текущему пути — это и есть цикл. Ребро в чёрную безопасно: из чёрной вершины уже всё просмотрено, и если бы оттуда был путь обратно в текущую, мы бы нашли его раньше.
WHITE, GRAY, BLACK = 0, 1, 2 def has_cycle_directed(n, edges): graph = [[] for _ in range(n)] for u, v in edges: graph[u].append(v) color = [WHITE] * n def dfs(v): color[v] = GRAY for to in graph[v]: if color[to] == GRAY: return True # обратное ребро if color[to] == WHITE and dfs(to): return True color[v] = BLACK return False return any(color[v] == WHITE and dfs(v) for v in range(n)) print(has_cycle_directed(4, [(0, 1), (0, 2), (1, 3), (2, 3)])) # False print(has_cycle_directed(3, [(0, 1), (1, 2), (2, 0)])) # True
Можно хранить вместо цветов два множества — visited и on_stack: это то же самое, просто серые вершины — это visited ∩ on_stack. Главное — не забыть убрать вершину из on_stack при выходе.
Алгоритм Кана
Подход с другой стороны: вместо поиска цикла пытаемся построить топологический порядок. Берём вершины без входящих рёбер, «удаляем» их вместе с исходящими рёбрами, повторяем. Если удалось удалить все вершины — цикла нет. Если остались вершины, у которых входящая степень так и не стала нулевой, — цикл есть.
from collections import deque def has_cycle_kahn(n, edges): graph = [[] for _ in range(n)] indeg = [0] * n for u, v in edges: graph[u].append(v) indeg[v] += 1 queue = deque(v for v in range(n) if indeg[v] == 0) processed = 0 while queue: v = queue.popleft() processed += 1 for to in graph[v]: indeg[to] -= 1 if indeg[to] == 0: queue.append(to) return processed < n
Плюсы Кана: нет рекурсии, код одинаково выглядит на любом языке, и попутно получается топологический порядок, если он нужен. Подробнее про сам порядок, его единственность и варианты — в статье о топологической сортировке.
Тонкость, о которой часто спрашивают: оставшиеся вершины — это не только цикл. Возьмём 0→1→2→3→1 и ещё 3→4. Цикл — 1→2→3, но вершина 4 тоже не обработается: в неё ведёт ребро из цикла, и её входящая степень никогда не обнулится.
def kahn_leftover(n, edges): graph = [[] for _ in range(n)] indeg = [0] * n for u, v in edges: graph[u].append(v) indeg[v] += 1 queue = deque(v for v in range(n) if indeg[v] == 0) while queue: v = queue.popleft() for to in graph[v]: indeg[to] -= 1 if indeg[to] == 0: queue.append(to) return [v for v in range(n) if indeg[v] > 0] print(kahn_leftover(5, [(0, 1), (1, 2), (2, 3), (3, 1), (3, 4)])) # [1, 2, 3, 4]
Остаток — это циклы плюс всё, что достижимо из них. Если нужен именно цикл, его придётся достать отдельно (см. ниже).
Что выбрать
| Ситуация | Выбор |
|---|---|
| Нужен только ответ «есть / нет» | любой, Кан проще без рекурсии |
| Нужен порядок вершин, если цикла нет | Кан |
| Нужен сам цикл | DFS с цветами и parent |
| Нужно понять, какие вершины «безопасны» (не ведут в цикл) | DFS с цветами или Кан на обратном графе |
| Очень глубокий граф ( вершин в цепочке) на Python | Кан или итеративный DFS |
Восстановление самого цикла
На собеседовании после «есть ли цикл» почти всегда звучит follow-up: «а выведите его». Идея одна для обоих видов графов: запоминаем parent[to] = v при переходе по ребру дерева DFS. Когда находим обратное ребро v → to, вершина to — предок v на текущем пути. Поднимаемся от v по parent до to — это и есть цикл.
Ориентированный граф
Сразу итеративная версия: Python по умолчанию ограничивает глубину рекурсии примерно тысячей вызовов, а на цепочке из вершин рекурсивный DFS падает с RecursionError. В стеке храним пару «вершина, индекс следующего соседа», чтобы продолжить с того же места.
WHITE, GRAY, BLACK = 0, 1, 2 def find_cycle_directed(n, edges): graph = [[] for _ in range(n)] for u, v in edges: graph[u].append(v) color = [WHITE] * n parent = [-1] * n for start in range(n): if color[start] != WHITE: continue color[start] = GRAY stack = [(start, 0)] while stack: v, i = stack.pop() if i == len(graph[v]): color[v] = BLACK # все соседи просмотрены — выходим continue stack.append((v, i + 1)) to = graph[v][i] if color[to] == WHITE: color[to] = GRAY parent[to] = v stack.append((to, 0)) elif color[to] == GRAY: cycle = [v] while cycle[-1] != to: cycle.append(parent[cycle[-1]]) return cycle[::-1] return [] print(find_cycle_directed(5, [(0, 1), (1, 2), (2, 3), (3, 1), (3, 4)])) # [1, 2, 3] print(find_cycle_directed(4, [(0, 1), (0, 2), (1, 3), (2, 3)])) # []
Разберём первый пример. DFS из 0: 0 серая → 1 серая → 2 серая → 3 серая. Из 3 первое ребро ведёт в 1, а 1 серая. Значит, 3 → 1 — обратное ребро. Поднимаемся: 3, parent[3] = 2, parent[2] = 1 — дошли. После разворота получаем [1, 2, 3], то есть цикл 1 → 2 → 3 → 1.
Неориентированный граф
Та же схема, только вместо цветов — visited, и пропускаем ребро к родителю по его номеру.
def find_cycle_undirected(n, edges): graph = [[] for _ in range(n)] for i, (u, v) in enumerate(edges): graph[u].append((v, i)) graph[v].append((u, i)) parent = [-1] * n parent_edge = [-1] * n visited = [False] * n for start in range(n): if visited[start]: continue visited[start] = True stack = [(start, 0)] while stack: v, i = stack.pop() if i == len(graph[v]): continue stack.append((v, i + 1)) to, eid = graph[v][i] if eid == parent_edge[v]: continue if visited[to]: cycle = [v] # to — предок v, поднимаемся к нему while cycle[-1] != to: cycle.append(parent[cycle[-1]]) return cycle[::-1] visited[to] = True parent[to] = v parent_edge[to] = eid stack.append((to, 0)) return [] edges = [(0, 1), (1, 2), (2, 3), (3, 4), (4, 1), (4, 5)] print(find_cycle_undirected(6, edges)) # [1, 2, 3, 4]
Почему подъём по parent всегда доходит до to? В неориентированном DFS нет перекрёстных рёбер: любое ребро вне дерева соединяет предка и потомка. Потомок обрабатывает такое ребро раньше предка (мы же сначала уходим вглубь), поэтому первым его замечает нижний конец, и to действительно окажется выше по пути.
Вот здесь и стреляет if to == parent: continue. Пусть есть два ребра 0–1. Вершина 1 пропустит оба, потому что оба ведут к родителю. Цикл заметит уже вершина 0, увидев посещённую 1, — но 1 её потомок, а не предок, и подъём по parent от 0 уйдёт за корень дерева, так и не встретив 1. С номером ребра вершина 1 пропустит только своё ребро дерева и найдёт цикл [0, 1] по второму.
Цикл из остатка алгоритма Кана
Если вы уже запустили Кана и хотите достать цикл без второго DFS, можно идти назад по входящим рёбрам внутри остатка. У каждой оставшейся вершины есть хотя бы одно входящее ребро из другой оставшейся вершины (иначе её степень обнулилась бы). Значит, двигаясь назад, мы никогда не застрянем и рано или поздно повторим вершину.
def cycle_from_kahn(n, edges): left = set(kahn_leftover(n, edges)) if not left: return [] prev = {} for u, v in edges: if u in left and v in left: prev.setdefault(v, u) # любое входящее ребро внутри остатка v = next(iter(left)) pos = {} path = [] while v not in pos: pos[v] = len(path) path.append(v) v = prev[v] return path[pos[v]:][::-1] # шли против рёбер — разворачиваем print(cycle_from_kahn(5, [(0, 1), (1, 2), (2, 3), (3, 1), (3, 4)])) # [2, 3, 1]
Цикл 2 → 3 → 1 → 2 тот же, что и раньше, просто начинается с другой вершины. Обратите внимание: стартовать можно даже с вершины 4, которая в цикл не входит, — движение назад всё равно приведёт в цикл.
Course Schedule (LeetCode 207)
Есть numCourses курсов и список prerequisites, где пара [a, b] означает «чтобы пройти курс a, нужно сначала пройти b». Можно ли пройти все курсы?
Курсы — вершины, зависимости — рёбра b → a. Пройти всё можно ровно тогда, когда в этом графе нет цикла: если a требует b, а b (через цепочку) требует a, начать не с чего.
Первое, на чём ошибаются, — направление ребра. Пара [a, b] — это b → a, а не a → b. Для ответа «да/нет» направление на самом деле не важно (развёрнутый граф имеет циклы там же), но в Course Schedule II, где нужен порядок, перепутанное направление даёт порядок задом наперёд.
Решение через Кана
from collections import deque def can_finish(num_courses, prerequisites): graph = [[] for _ in range(num_courses)] indeg = [0] * num_courses for course, pre in prerequisites: graph[pre].append(course) indeg[course] += 1 queue = deque(c for c in range(num_courses) if indeg[c] == 0) taken = 0 while queue: c = queue.popleft() taken += 1 for nxt in graph[c]: indeg[nxt] -= 1 if indeg[nxt] == 0: queue.append(nxt) return taken == num_courses print(can_finish(2, [[1, 0]])) # True print(can_finish(2, [[1, 0], [0, 1]])) # False
Интерпретация понятна без слов «граф» и «цикл»: берём курсы, у которых не осталось невыполненных требований, проходим их, снимаем требования с зависящих курсов. Если в какой-то момент брать нечего, а курсы остались — они ждут друг друга.
Решение через три цвета
То же на JavaScript — пригодится, если собеседование идёт на JS:
function canFinish(numCourses, prerequisites) { const graph = Array.from({ length: numCourses }, () => []) for (const [course, pre] of prerequisites) graph[pre].push(course) const color = new Array(numCourses).fill(0) // 0 белый, 1 серый, 2 чёрный const dfs = (v) => { color[v] = 1 for (const to of graph[v]) { if (color[to] === 1) return false if (color[to] === 0 && !dfs(to)) return false } color[v] = 2 return true } for (let v = 0; v < numCourses; v++) { if (color[v] === 0 && !dfs(v)) return false } return true } console.log(canFinish(2, [[1, 0]])) // true console.log( canFinish(2, [ [1, 0], [0, 1], ]) ) // false console.log( canFinish(4, [ [1, 0], [2, 0], [3, 1], [3, 2], ]) ) // true
Последний пример — тот самый ромб: курс 3 требует 1 и 2, оба требуют 0. Наивный visited здесь вернул бы false, три цвета дают правильный true.
Follow-up: покажите конфликт
Если пройти нельзя, пользователю полезно знать почему. Достаточно применить find_cycle_directed из раздела выше к рёбрам pre → course:
def explain_conflict(num_courses, prerequisites): edges = [(pre, course) for course, pre in prerequisites] cycle = find_cycle_directed(num_courses, edges) if not cycle: return None return ' -> '.join(map(str, cycle + [cycle[0]])) print(explain_conflict(4, [[1, 0], [2, 1], [3, 2], [1, 3]])) # 1 -> 2 -> 3 -> 1
Ответ читается как «курс 1 открывает 2, 2 открывает 3, а 3 нужен для 1». Это ровно то, что выводят сборщики и менеджеры пакетов при циклической зависимости.
Если просят вернуть сам порядок прохождения (Course Schedule II, LeetCode 210), это уже топологическая сортировка — она разобрана отдельно.
Родственные задачи
Find Eventual Safe States (LeetCode 802)
Вершина безопасна, если любой путь из неё заканчивается в тупике, то есть не ведёт в цикл. Это прямо цвета: вершина безопасна, если её DFS завершился чёрным цветом без встречи серой. Альтернатива — Кан на графе с развёрнутыми рёбрами: безопасные вершины — те, что обработаются.
WHITE, GRAY, BLACK = 0, 1, 2 def eventual_safe_nodes(graph): color = [WHITE] * len(graph) def safe(v): if color[v] != WHITE: return color[v] == BLACK # серая — мы в цикле color[v] = GRAY for to in graph[v]: if not safe(to): return False # остаётся серой навсегда color[v] = BLACK return True return [v for v in range(len(graph)) if safe(v)] print(eventual_safe_nodes([[1, 2], [2, 3], [5], [0], [5], [], []])) # [2, 4, 5, 6]
Хитрость в том, что вершина, ведущая в цикл, так и остаётся серой, и при повторном запросе сразу считается небезопасной.
Ещё задачи на ту же идею
- Redundant Connection (LeetCode 684) — DSU, разобрано выше. Версия II (LeetCode 685) с ориентированным деревом заметно сложнее: там надо учитывать вершину с двумя родителями.
- Graph Valid Tree (LeetCode 261) — плюс связность или «нет цикла» плюс связность.
- Detect Cycles in 2D Grid (LeetCode 1559) — неориентированный DFS с родителем по клеткам сетки одной буквы.
- Find the Duplicate Number (LeetCode 287) — граф, где из каждой вершины ровно одно ребро
i → nums[i]. Цикл в таком «функциональном» графе ищется алгоритмом Флойда без дополнительной памяти, как в связном списке.
Сложность
| Метод | Время | Память |
|---|---|---|
| DFS с родителем | на список смежности, на стек | |
| DSU | ||
| Три цвета | ||
| Алгоритм Кана | ||
| Восстановление цикла | на подъём по parent |
— обратная функция Аккермана, на практике не больше 4–5. Каждая вершина и каждое ребро в DFS и Кане обрабатываются константное число раз, поэтому все методы линейны.
Типичные ошибки
- Один
visitedв ориентированном графе. Ложный цикл на ромбе. Нужны три цвета или отдельныйon_stack. - Забыли перекрасить в чёрный. Если оставить вершину серой после выхода, любое следующее ребро в неё станет «циклом». Обратная ошибка — сделать вершину сразу чёрной при входе — пропускает настоящие циклы.
- Пропуск родителя в ориентированном графе. Условие
to != parentнужно только в неориентированном. В ориентированном0 → 1 → 0— настоящий цикл длины 2, и пропускать ребро в родителя нельзя. - Пропуск родителя по вершине при кратных рёбрах. Для ответа «да/нет» сходит, для восстановления цикла ломается. Храните номер ребра.
- DFS только из вершины 0. Граф может быть несвязным; запускайте обход из каждой непосещённой вершины.
- DSU для ориентированного графа. Не работает: общая компонента не означает обратного пути.
- Считать остаток Кана циклом. В остатке ещё и всё, что достижимо из цикла.
- Рекурсия на Python. На глубоких графах —
RecursionError.sys.setrecursionlimitпомогает не всегда: можно упереться в размер стека потока. Надёжнее итеративный DFS или Кан. - Перепутанное направление в Course Schedule.
[a, b]— этоb → a. На ответ в 207 не влияет, в 210 даёт перевёрнутый порядок.
Как это звучит на собеседовании
Хороший ответ укладывается в пару фраз до кода: «Граф ориентированный, поэтому visited недостаточно — буду красить в три цвета, цикл — это ребро в серую вершину. Обход . Если граф глубокий, перепишу на Кана: считаю обработанные вершины, если меньше — цикл».
Дальше обычно спрашивают одно из трёх: «а если граф неориентированный» (родитель или DSU), «а выведите цикл» (parent и подъём вверх) или «а дайте порядок» (топологическая сортировка). Если вы заранее знаете, чем ориентированный случай отличается от неориентированного и почему ромб ломает наивный код, все три вопроса закрываются за пару минут.