Клонирование графа (LeetCode 133): DFS с хеш-таблицей на Python

Задача Clone Graph (LeetCode 133) просит вернуть глубокую копию связного неориентированного графа. Ключевая идея — хеш-таблица, которая сопоставляет каждому исходному узлу его копию. Она позволяет создать каждую копию один раз и связать соседей, не зацикливаясь бесконечно на циклах. Время и память — O(V + E).

Задача

Вы получаете ссылку на один узел связного неориентированного графа. У каждого узла есть значение и список соседей. Верните глубокую копию: новые узлы с теми же значениями и теми же связями, и ни один узел не должен быть общим с оригиналом. Входные данные могут быть None, в этом случае верните None.

Класс узла выглядит так:

class Node:
    def __init__(self, val=0, neighbors=None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []

Почему это не просто рекурсия

Граф может содержать циклы, а в неориентированном графе каждое ребро — это крошечный цикл (A указывает на B, а B указывает на A). Функция копирования, которая вызывает себя для каждого соседа, никогда не остановится. Нужно запоминать, какие узлы уже скопированы.

Подход: словарь плюс поиск в глубину

Заведите словарь copies, который сопоставляет исходный узел его клону. Обходите граф со стеком. Когда встречаете соседа, которого ещё не копировали, создайте его клон и положите в стек. В любом случае добавьте клон соседа в список соседей текущего клона.

class Node:
    def __init__(self, val=0, neighbors=None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []

def clone_graph(node):
    if node is None:
        return None
    copies = {node: Node(node.val)}
    stack = [node]
    while stack:
        cur = stack.pop()
        for nb in cur.neighbors:
            if nb not in copies:
                copies[nb] = Node(nb.val)
                stack.append(nb)
            copies[cur].neighbors.append(copies[nb])
    return copies[node]

Трассировка

Возьмём граф-квадрат: 1 соединён с 2 и 4, 2 с 3, 3 с 4. Начинаем с узла 1: создаём копию 1, затем посещаем соседей узла 1 — 2 и 4, создаём копии для обоих и связываем их с копией 1. Извлекаем узел 4: его соседи — 1 и 3, поэтому копия 1 связывается (уже есть), а копия 3 создаётся и связывается. Извлекаем узел 3, затем узел 2, и оставшиеся связи добавляются. Каждый узел создаётся один раз, и каждое ребро появляется в обоих направлениях, потому что каждая вершина добавляет другую в свой список.

Поиск в глубину или в ширину

Работают оба. Замените стек на deque и popleft() для поиска в ширину. Единственное обязательное условие — словарь. Рекурсию писать короче, но глубокий граф может упереться в лимит рекурсии Python, поэтому итеративная версия безопаснее.

Частые ошибки

• Создавать новый клон каждый раз, когда узел встречается снова, — это дублирует узлы и приводит к бесконечному циклу.
• Копировать список соседей по ссылке, из-за чего клон указывает обратно на исходные узлы.
• Забыть про входные данные None.
• Использовать значение узла как ключ словаря, когда значения не гарантированно уникальны. Использовать сам объект узла надёжнее.

Краевые случаи для проверки

Как объяснить это на собеседовании

1. Скажите, что здесь означает глубокая копия: новые узлы, та же структура.
2. Укажите на циклы и объясните, почему нужен словарь.
3. Опишите словарь от оригинала к клону и обход.
4. Напишите код, затем пройдитесь по примеру с двумя узлами.
5. Назовите время O(V + E) и память O(V).

Я протестировал приведённый выше код на 3 000 случайных связных графах, проверяя, что копия имеет те же значения и рёбра и что ни один узел не является общим с оригиналом, прежде чем публиковать. Такая быстрая случайная проверка — хорошая привычка при практике.

Связанная практика

Смотрите нашу шпаргалку по Big O для терминов сложности, список LeetCode Blind 75 для того, что практиковать дальше, и руководство по ассистенту для собеседований по программированию для того, как практиковаться.

Проговаривайте свой подход вслух, пока пишете код. Транскрипт показывает, сформулировали ли вы ключевое наблюдение до того, как начали писать. Соблюдайте правила работодателя об AI-инструментах на любом живом ассессменте.