Clone Graph

Средняя№133граф

Дан один узел связного неориентированного графа; у каждого узла есть значение и список соседей. Нужно вернуть глубокую копию: новые узлы с теми же значениями и теми же рёбрами, и ни одна ссылка копии не должна вести на старый узел. Наш граф: треугольник 1 – 2 – 3 с хвостом 3 – 4 – 5, и нам дан узел 1. Ответ — узел 1′ нового графа той же формы: 1′ – 2′ – 3′ с хвостом 3′ – 4′ – 5′.

133 Clone GraphРазбор · 1×

Пример: скопировать треугольник 1 – 2 – 3 с хвостом 3 – 4 – 5, начиная с узла 1. Копия нарисована справа, её узлы помечены ′.

графкопия12345copies—вызовы cloneвершина справа—
ещё не дошлиждёт в стеке вызововтекущий вызовследующий сосед; копия из словаряскопирован со всеми соседями

copies = пустой словарь: для каждого старого узла — его копия

01/55
сначала · назад · пуск · шаг
Скорость
1function cloneGraph(node):
2 copies = empty map // old node → its copy
3 return clone(node)
4
5function clone(node):
6 if node in copies:
7 return copies[node]
8 copy = new node with node.val
9 copies[node] = copy // before the neighbours
10 for next in node.neighbors:
11 copy.neighbors.add(clone(next))
12 return copy
состояние
node
1
next
–
copy
–
copies
{}
нажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Обход в глубину из данного узла доходит до каждого узла связного графа, и clone(node) копирует каждый, до которого дошёл.
  2. По циклу обход возвращается к узлу, который уже начал копировать, а до узла можно дойти с двух сторон, как до 3 здесь. Словарь «старый → копия» заполняется до обхода соседей, поэтому такой узел в нём уже есть и его копия берётся оттуда: без второй копии и без бесконечного круга.
  3. Каждый сосед копии — это то, что вернул clone, а clone возвращает только копии, поэтому ни одна ссылка копии не ведёт в старый граф.

Сложность

Время O(V + E): каждый узел копируем один раз, каждое ребро смотрим с двух концов. Память O(V): словарь и стек вызовов глубиной до V.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.