Clone Graph: глубокое копирование графа через DFS и BFS с хеш-таблицей, Copy List with Random Pointer
Разбор Clone Graph и Copy List with Random Pointer: DFS и BFS со словарём «оригинал → копия», решение за O(1) памяти через переплетение списка, deepcopy и типичные ошибки.
Коротко
| Вопрос | Ответ |
|---|---|
| Что нужно | Построить полностью независимую копию структуры, в которой узлы ссылаются друг на друга, в том числе по кругу |
| Главная идея | Словарь оригинал → копия. Он одновременно служит множеством посещённых и картой для перевешивания ссылок |
| Обход | Подойдёт любой: рекурсивный DFS, BFS с очередью, DFS со стеком |
| Сложность | по времени, дополнительной памяти |
| Главная ловушка | Копию нужно положить в словарь до того, как идти к соседям, иначе на цикле будет бесконечная рекурсия |
| Родственная задача | Copy List with Random Pointer: та же идея, плюс трюк с переплетением списка за памяти |
Clone Graph (LeetCode 133) и Copy List with Random Pointer (LeetCode 138) — две задачи уровня Medium, которые проверяют одно и то же умение: скопировать не значения, а форму связей. Обе часто попадаются на собеседованиях как раз потому, что код короткий, а место для ошибки одно и очень конкретное. Разберём, где оно, и почему одна идея закрывает целое семейство задач, вплоть до copy.deepcopy в Python и structuredClone в JavaScript.
Постановка задачи
Дан связный неориентированный граф и ссылка на один его узел. Узел устроен так:
class Node: def __init__(self, val=0, neighbors=None): self.val = val self.neighbors = neighbors if neighbors is not None else []
Нужно вернуть глубокую копию графа: для каждого узла создать новый объект с тем же val, а в neighbors положить ссылки на новые объекты, а не на старые. После клонирования ни один узел копии не должен указывать в оригинал.
Пример: граф-квадрат 1–2–3–4–1. LeetCode описывает его списком смежности [[2,4],[1,3],[2,4],[1,3]]: у узла 1 соседи 2 и 4, у узла 2 соседи 1 и 3 и так далее. Копия должна давать тот же список смежности, но состоять из других объектов.
Почему наивное копирование не работает
Первое, что приходит в голову: создать копию узла, затем рекурсивно скопировать каждого соседа.
def clone_naive(node): copy = Node(node.val) for nb in node.neighbors: copy.neighbors.append(clone_naive(nb)) return copy
Проблем две, и обе следуют из того, что граф — не дерево.
- Циклы. Граф неориентированный, поэтому если 1 сосед 2, то и 2 сосед 1. Рекурсия уйдёт 1 → 2 → 1 → 2 → … до
RecursionError. - Общие узлы. Даже без циклов один узел может быть достижим несколькими путями. Наивный код создаст для него несколько копий, и форма графа развалится: там, где в оригинале был один узел, в копии окажутся разные объекты.
Обе проблемы решает одно правило: на каждый узел оригинала ровно одна копия. Значит, нужна память о том, какие узлы уже скопированы и как зовут их копии. Это и есть хеш-таблица.
Решение: DFS со словарём «оригинал → копия»
def clone_graph(node): if node is None: return None copies = {} def dfs(v): if v in copies: return copies[v] c = Node(v.val) copies[v] = c # регистрируем ДО обхода соседей for nb in v.neighbors: c.neighbors.append(dfs(nb)) return c return dfs(node)
Словарь copies делает две работы одновременно:
- Множество посещённых. Если узел уже есть в словаре, второй раз в него не заходим, и цикл обрывается.
- Карта перевода ссылок. Когда нам нужна ссылка на копию соседа, словарь отдаёт ровно тот объект, который уже был создан, поэтому общие узлы остаются общими.
Ключ словаря — сам объект узла. В Python пользовательские классы без __eq__ хешируются по идентичности, это ровно то, что нужно. Ключом по val пользоваться не стоит: в LeetCode 133 значения уникальны, но в реальном коде и в вариациях задачи на собеседовании это не гарантировано. О том, как устроены словари внутри, есть отдельная статья про хеш-таблицы.
Почему порядок строк решает всё
Самая частая ошибка — записать копию в словарь после того, как скопированы соседи:
def dfs(v): if v in copies: return copies[v] c = Node(v.val, [dfs(nb) for nb in v.neighbors]) # соседи раньше регистрации copies[v] = c return c
Выглядит аккуратнее, но на графе с циклом падает с RecursionError. Пока мы обходим соседей узла 1, сам узел 1 в словаре ещё не числится. Сосед 2 вернётся к 1, не найдёт его в copies и начнёт копировать заново. Правило простое: сначала создай и зарегистрируй, потом заполняй. Копия в момент регистрации неполная, у неё пустой neighbors, но это не страшно: остальные узлы держат на неё ссылку, а список соседей она получит к концу своего вызова.
Разбор на примере
Граф-квадрат: 1–2, 2–3, 3–4, 4–1. Запускаем dfs(1).
| Шаг | Вызов | Что происходит | copies |
|---|---|---|---|
| 1 | dfs(1) | Создаём 1', регистрируем, идём к соседу 2 | 1 |
| 2 | dfs(2) | Создаём 2', идём к соседу 1 | 1, 2 |
| 3 | dfs(1) | 1 уже в словаре, возвращаем 1'. 2'.neighbors = [1'] | 1, 2 |
| 4 | dfs(3) | Сосед 3 узла 2: создаём 3', сосед 2 уже есть, идём к 4 | 1, 2, 3 |
| 5 | dfs(4) | Создаём 4', оба соседа (1 и 3) уже скопированы | 1–4 |
| 6 | возврат | 4' → [1', 3'], 3' → [2', 4'], 2' → [1', 3'] | 1–4 |
| 7 | dfs(4) | Второй сосед узла 1: уже в словаре. 1' → [2', 4'] | 1–4 |
Каждый узел создан ровно один раз, каждое ребро просмотрено дважды (по разу с каждой стороны), что для неориентированного графа нормально.
Решение: BFS с очередью
Рекурсия в Python упирается в лимит глубины (по умолчанию 1000). Для графа-цепочки из 10 000 узлов рекурсивный DFS упадёт. Поэтому на собеседовании полезно уметь написать и итеративную версию. BFS здесь выглядит особенно естественно:
from collections import deque def clone_graph_bfs(node): if node is None: return None copies = {node: Node(node.val)} queue = deque([node]) while queue: v = queue.popleft() for nb in v.neighbors: if nb not in copies: copies[nb] = Node(nb.val) queue.append(nb) copies[v].neighbors.append(copies[nb]) return copies[node]
Инвариант тот же: копия создаётся в момент, когда узел впервые увиден, а не когда его достали из очереди. Благодаря этому каждый узел попадает в очередь один раз. Ребро v → nb переносится в копию сразу, даже если nb ещё не обработан: ссылка на его копию уже существует, а соседей она получит позже.
Замените deque на список, а popleft() на pop(), и получится итеративный DFS — порядок обхода сменится, результат нет. Это хорошая демонстрация того, что для клонирования порядок обхода не важен; важно только, чтобы каждый узел был посещён и скопирован один раз. Подробнее о самих обходах — в статье BFS и DFS простыми словами.
Сложность
- Время: . Каждый узел создаём один раз, каждый список соседей проходим один раз.
- Память: на словарь плюс на стек рекурсии или очередь. Саму копию графа, размером , обычно не считают дополнительной памятью: это ответ.
Быстрее нельзя: чтобы скопировать граф, его придётся хотя бы прочитать.
То же на JavaScript
В JS роль словаря играет Map: в отличие от обычного объекта, он принимает объекты в качестве ключей и сравнивает их по ссылке.
function cloneGraph(node, copies = new Map()) { if (!node) return null if (copies.has(node)) return copies.get(node) const copy = { val: node.val, neighbors: [] } copies.set(node, copy) for (const nb of node.neighbors) copy.neighbors.push(cloneGraph(nb, copies)) return copy }
Если в качестве ключа взять обычный объект {}, все узлы превратятся в строку "[object Object]" и сольются в один ключ. Это классическая ошибка JS-кандидатов.
Copy List with Random Pointer
Вторая задача семейства. Дан односвязный список, у каждого узла помимо next есть указатель random, который смотрит на произвольный узел списка или в None. Нужно сделать глубокую копию.
class RNode: def __init__(self, val, next=None, random=None): self.val = val self.next = next self.random = random
Сложность в том, что random может указывать вперёд, на узел, копии которого ещё нет. Если копировать список одним проходом по next, ссылку на будущий узел поставить некуда.
Два прохода со словарём
Та же идея, что в Clone Graph, только обход тривиальный: идём по next.
def copy_random_list(head): copies = {None: None} cur = head while cur: # проход 1: создаём все копии copies[cur] = RNode(cur.val) cur = cur.next cur = head while cur: # проход 2: расставляем ссылки copies[cur].next = copies[cur.next] copies[cur].random = copies[cur.random] cur = cur.next return copies[head]
Запись {None: None} — маленький трюк, который убирает проверки на None: и последний next, и пустой random переводятся в None без отдельных if. Время , память .
Можно уложиться и в один проход: создавать копии лениво, через функцию «дай копию узла, создав её при необходимости», как в DFS для графа. По сути это и есть Clone Graph, где у каждого узла ровно два «соседа».
Решение за O(1) дополнительной памяти
Это тот самый follow-up, ради которого задачу и дают. Словарь нужен, чтобы по оригиналу найти копию. А если положить копию прямо после оригинала в том же списке, то копия узла X — это просто X.next.
Три прохода:
- Переплетаем. Список
A → B → Cпревращаем вA → A' → B → B' → C → C'. - Расставляем
random. ЕслиA.random = C, то копия должна указывать наC', а этоC.next. Значит,A'.random = A.random.next. - Расплетаем. Восстанавливаем
nextу оригиналов и собираем копии в отдельный список.
def copy_random_list_o1(head): if head is None: return None cur = head while cur: # 1. A -> A' -> B -> B' -> ... cur.next = RNode(cur.val, cur.next) cur = cur.next.next cur = head while cur: # 2. копия random: A'.random = A.random.next if cur.random: cur.next.random = cur.random.next cur = cur.next.next new_head = head.next cur = head while cur: # 3. расплетаем два списка copy = cur.next cur.next = copy.next copy.next = copy.next.next if copy.next else None cur = cur.next return new_head
Проверим на примере из условия LeetCode: [[7,null],[13,0],[11,4],[10,2],[1,0]], где второе число — индекс узла, на который смотрит random. Копия даёт ту же структуру, а исходный список после третьего прохода возвращается в первоначальный вид.
На что смотреть в этом решении:
- Шаг 2 нельзя совместить с шагом 3. Пока мы расплетаем список,
randomу ещё не обработанного узла может смотреть на уже расплетённую часть, гдеX.nextбольше не копия. Поэтому всеrandomрасставляются до того, как начинаем рвать связи. - Оригинал нужно вернуть в исходное состояние. LeetCode это проверяет, интервьюер тоже спросит. Мутировать входные данные и не убрать за собой — плохой тон.
- Память — это без учёта самой копии. Новые узлы всё равно занимают , но это ответ, а не вспомогательная структура.
Если работа со ссылками в списках пока даётся тяжело, сначала стоит разобраться с разворотом связного списка и задачами на связные списки.
Глубокое копирование в языках: та же идея
Словарь «оригинал → копия» — не олимпиадный трюк, а стандартный механизм глубокого копирования.
Python. copy.deepcopy(obj, memo) хранит в memo соответствие id(оригинала) → копия. Поэтому циклы и общие ссылки копируются корректно:
import copy a = [1, 2] a.append(a) # список содержит сам себя b = copy.deepcopy(a) print(b[2] is b) # True: цикл сохранён, но уже в копии
Упрощённый deep_copy для списков и словарей пишется ровно по схеме Clone Graph:
def deep_copy(obj, memo=None): if memo is None: memo = {} if id(obj) in memo: return memo[id(obj)] if isinstance(obj, list): res = [] memo[id(obj)] = res # регистрируем до рекурсии res.extend(deep_copy(x, memo) for x in obj) return res if isinstance(obj, dict): res = {} memo[id(obj)] = res for k, v in obj.items(): res[k] = deep_copy(v, memo) return res return obj # числа, строки и прочие неизменяемые значения
Для собственных классов deepcopy позволяет определить __deepcopy__(self, memo) — и внутри него снова нужно сначала положить себя в memo, а потом копировать поля.
JavaScript. JSON.parse(JSON.stringify(obj)) на циклической структуре бросает TypeError, а общие ссылки превращает в независимые копии. Встроенный structuredClone держит внутреннюю карту уже скопированных объектов и с циклами справляется. Вопрос «как сделать глубокое копирование объекта с циклическими ссылками» — частый на фронтенд-собеседованиях, и ответ на него — Clone Graph.
Типичные ошибки
- Регистрация копии после обхода соседей. Бесконечная рекурсия на любом цикле. Создал — сразу положил в словарь.
- Ключ словаря по значению. Работает, пока
valуникальны. Ключом должен быть сам узел (илиid(node)). - Ссылки на оригинал в копии. Например,
copy.neighbors = v.neighbors— копируется список, но в нём старые узлы. Проверяйте: ни один объект копии не должен совпадать с объектом оригинала. - Забыли пустой вход.
node is Noneиhead is None— отдельный случай, LeetCode его проверяет. - Рекурсия на длинных цепочках. На Python это
RecursionErrorуже на тысячах узлов. Если интервьюер спрашивает про большие графы, переходите на BFS или стек. - В решении за памяти не восстановлен исходный список или
randomрасставлен в одном цикле с расплетанием.
Как это выглядит на собеседовании
Типичный сценарий для Clone Graph: кандидат быстро пишет рекурсию, интервьюер просит прогнать на графе из двух узлов, соединённых ребром, и тут выясняется, есть ли проверка «уже скопирован». Хороший ход — сразу проговорить: «граф может содержать циклы, поэтому мне нужен словарь оригинал → копия, он же visited». Это показывает, что вы видите суть задачи, а не вспоминаете код. Привычка рассуждать вслух здесь окупается сразу.
Частые follow-up вопросы:
- Граф несвязный, дан список всех узлов. Запускаем тот же обход из каждого ещё не скопированного узла, словарь общий.
- Граф ориентированный. Код не меняется: словарь работает и для направленных рёбер.
- Нет рекурсии. BFS или стек, как выше.
- Copy List за памяти. Переплетение списка.
- Как проверить, что копия правильная? Обойти оба графа синхронно и убедиться, что значения и структура совпадают, а множества объектов не пересекаются.
Близкие задачи, где работает тот же паттерн «обход + словарь посещённых»: Number of Islands, поиск циклов в графе, сериализация бинарного дерева (там структуру нужно не скопировать, а сохранить и восстановить). А для деревьев без общих узлов словарь не нужен вообще: каждый узел достижим ровно одним путём, и наивная рекурсия из начала статьи работает.
Итог
Любая структура со ссылками — граф, список с random, объект с циклами — копируется по одной схеме: обойти все узлы, на каждый создать ровно одну копию и запомнить её в словаре, а ссылки переводить через этот словарь. Главное — регистрировать копию до того, как идёшь к соседям. Для связного списка словарь можно заменить переплетением: копия живёт сразу за оригиналом, и X.next работает как бесплатная хеш-таблица.