Поиск цикла в графе: DFS, три цвета, DSU и алгоритм Кана

Как найти цикл в неориентированном и ориентированном графе: DFS с родителем, DSU, три цвета, алгоритм Кана, восстановление самого цикла и разбор Course Schedule. Код на Python.

13 мин чтенияалгоритмы · графы · python

Коротко

ГрафМетодВремяЧто даёт
НеориентированныйDFS с родителемO(V+E)O(V + E)есть ли цикл и сам цикл
НеориентированныйDSU (Union-Find)O(E⋅α(V))O(E \cdot \alpha(V))первое ребро, замыкающее цикл, работает на потоке рёбер
ОриентированныйDFS, три цветаO(V+E)O(V + E)есть ли цикл и сам цикл
ОриентированныйАлгоритм КанаO(V+E)O(V + E)есть ли цикл и вершины, которые «застряли»
  • В неориентированном графе цикл — это ребро в уже посещённую вершину, если это не ребро, по которому мы пришли.
  • В ориентированном графе одного visited мало: цикл — это ребро в вершину, которая ещё на стеке рекурсии (серая).
  • Чтобы вернуть сам цикл, храните parent и при обнаружении обратного ребра пройдите по родителям вверх.
  • Course Schedule — это вопрос «есть ли цикл в ориентированном графе зависимостей».

Здесь речь о графах общего вида. Если у каждой вершины ровно одно исходящее ребро (связный список, функция next), есть решение за O(1)O(1) памяти — алгоритм Флойда, он разобран в статье про цикл в связном списке. А как превращать ациклический граф в порядок вершин, подробно описано в топологической сортировке. Эта статья — про сам цикл: как его заметить, как достать и где на этом спотыкаются.

Почему для двух видов графов разные алгоритмы

Возьмём «ромб»: рёбра 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 не попасть.

Проверка без обхода: считаем рёбра

Полезный факт для собеседования. Лес (граф без циклов) из VV вершин и CC компонент содержит ровно V−CV - C рёбер. Каждое лишнее ребро создаёт цикл. Значит:

цикл есть  ⟺  E>V−C\text{цикл есть} \iff E > V - C

Для связного графа (C=1C = 1): цикл есть тогда и только тогда, когда E≥VE \ge V. Это мгновенный ответ в задачах вроде Graph Valid Tree (LeetCode 261): граф — дерево, если E=V−1E = V - 1 и он связен. Компоненты всё равно придётся посчитать обходом или 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 с цветами или Кан на обратном графе
Очень глубокий граф (10510^5 вершин в цепочке) на PythonКан или итеративный DFS

Восстановление самого цикла

На собеседовании после «есть ли цикл» почти всегда звучит follow-up: «а выведите его». Идея одна для обоих видов графов: запоминаем parent[to] = v при переходе по ребру дерева DFS. Когда находим обратное ребро v → to, вершина to — предок v на текущем пути. Поднимаемся от v по parent до to — это и есть цикл.

Ориентированный граф

Сразу итеративная версия: Python по умолчанию ограничивает глубину рекурсии примерно тысячей вызовов, а на цепочке из 2⋅1052 \cdot 10^5 вершин рекурсивный 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) — E=V−1E = V - 1 плюс связность или «нет цикла» плюс связность.
  • Detect Cycles in 2D Grid (LeetCode 1559) — неориентированный DFS с родителем по клеткам сетки одной буквы.
  • Find the Duplicate Number (LeetCode 287) — граф, где из каждой вершины ровно одно ребро i → nums[i]. Цикл в таком «функциональном» графе ищется алгоритмом Флойда без дополнительной памяти, как в связном списке.

Сложность

МетодВремяПамять
DFS с родителемO(V+E)O(V + E)O(V+E)O(V + E) на список смежности, O(V)O(V) на стек
DSUO(E⋅α(V))O(E \cdot \alpha(V))O(V)O(V)
Три цветаO(V+E)O(V + E)O(V+E)O(V + E)
Алгоритм КанаO(V+E)O(V + E)O(V+E)O(V + E)
Восстановление цикла+O(V)+O(V) на подъём по parentO(V)O(V)

α\alpha — обратная функция Аккермана, на практике не больше 4–5. Каждая вершина и каждое ребро в DFS и Кане обрабатываются константное число раз, поэтому все методы линейны.

Типичные ошибки

  1. Один visited в ориентированном графе. Ложный цикл на ромбе. Нужны три цвета или отдельный on_stack.
  2. Забыли перекрасить в чёрный. Если оставить вершину серой после выхода, любое следующее ребро в неё станет «циклом». Обратная ошибка — сделать вершину сразу чёрной при входе — пропускает настоящие циклы.
  3. Пропуск родителя в ориентированном графе. Условие to != parent нужно только в неориентированном. В ориентированном 0 → 1 → 0 — настоящий цикл длины 2, и пропускать ребро в родителя нельзя.
  4. Пропуск родителя по вершине при кратных рёбрах. Для ответа «да/нет» сходит, для восстановления цикла ломается. Храните номер ребра.
  5. DFS только из вершины 0. Граф может быть несвязным; запускайте обход из каждой непосещённой вершины.
  6. DSU для ориентированного графа. Не работает: общая компонента не означает обратного пути.
  7. Считать остаток Кана циклом. В остатке ещё и всё, что достижимо из цикла.
  8. Рекурсия на Python. На глубоких графах — RecursionError. sys.setrecursionlimit помогает не всегда: можно упереться в размер стека потока. Надёжнее итеративный DFS или Кан.
  9. Перепутанное направление в Course Schedule. [a, b] — это b → a. На ответ в 207 не влияет, в 210 даёт перевёрнутый порядок.

Как это звучит на собеседовании

Хороший ответ укладывается в пару фраз до кода: «Граф ориентированный, поэтому visited недостаточно — буду красить в три цвета, цикл — это ребро в серую вершину. Обход O(V+E)O(V + E). Если граф глубокий, перепишу на Кана: считаю обработанные вершины, если меньше VV — цикл».

Дальше обычно спрашивают одно из трёх: «а если граф неориентированный» (родитель или DSU), «а выведите цикл» (parent и подъём вверх) или «а дайте порядок» (топологическая сортировка). Если вы заранее знаете, чем ориентированный случай отличается от неориентированного и почему ромб ломает наивный код, все три вопроса закрываются за пару минут.

Потренироваться в спокойной обстановке

Все задачи