4. Clone Graph

«Истинное клонирование структуры состоит не в копировании узлов, а в точном воспроизведении взаимосвязей между ними».
— Брайан Керниган

Задача Clone Graph (LeetCode 133) — классический водораздел между простым обходом структур данных и их архитектурным конструированием.

Условие: Дан указатель на вершину связного неориентированного графа. Каждая вершина содержит целочисленное значение Val и список смежных вершин Neighbors []*Node. Требуется вернуть глубокую копию (Deep Copy) графа — полностью новый граф с идентичной топологией, не разделяющий с оригиналом ни одного указателя.

Если при обходе деревьев мы двигались строго от корня к листьям в отсутствие циклов, то в графах общего вида ребра образуют двусторонние петли и циклы ($A \leftrightarrow B$). Попытка наивного рекурсивного создания узлов моментально обрушит рантайм в бесконечную рекурсию.

Архитектура: Словарь клонов как инвариант разрешения циклов

Ключевой архитектурный инструмент глубокого копирования — хеш-таблица сопоставления:

$$\text{cloned} : \text{map}[*\text{Node}]*\text{Node}$$

Она одновременно выполняет две критические функции:

1. Множество visited: предотвращает повторный заход в уже обработанные вершины.
2. Таблица разрешения ссылок (Memoization): хранит соответствие между оригинальным указателем и вновь созданным объектом в куче.

flowchart TD
    classDef entry   fill:#1e3a5f,stroke:#38bdf8,stroke-width:2px,color:#f8fafc
    classDef process fill:#1e293b,stroke:#38bdf8,stroke-width:1px,color:#f8fafc
    classDef warning fill:#78350f,stroke:#fbbf24,stroke-width:1px,color:#f8fafc
    classDef success fill:#064e3b,stroke:#34d399,stroke-width:1px,color:#f8fafc

    Start["dfs(node)"]:::entry --> CheckNull{"node == nil?"}:::warning
    CheckNull -->|"Да"| ReturnNil["return nil"]:::process

    CheckNull -->|"Нет"| CheckMap{"node есть в map?"}:::warning
    CheckMap -->|"Да (Узел уже скопирован)"| ReturnClone["return cloned[node]<br>(Разрыв цикла!)"]:::success

    CheckMap -->|"Нет (Первый визит)"| Create["1. Создать copy := &Node{Val: node.Val}<br>2. Записать cloned[node] = copy (ДО соседей!)"]:::process

    Create --> Loop["Для каждого соседа nb в node.Neighbors:"]:::process
    Loop --> Recurse["copy.Neighbors = append(copy.Neighbors, dfs(nb))"]:::process
    Recurse --> ReturnCopy["return copy"]:::success
  

Идиоматичная реализация на Go

package main

type Node struct {
    Val       int
    Neighbors []*Node
}

// cloneGraph создает полную глубокую копию графа с сохранением циклических связей.
// Временная сложность: O(V + E) — посещаем каждую вершину и ребро ровно один раз
// Пространственная сложность: O(V) под хеш-таблицу и стек вызовов
func cloneGraph(node *Node) *Node {
    if node == nil {
        return nil
    }

    // Словарь для связывания оригиналов с клонами
    cloned := make(map[*Node]*Node)

    var dfs func(n *Node) *Node
    dfs = func(n *Node) *Node {
        if n == nil {
            return nil
        }

        // Если узел уже был склонирован ранее — немедленно возвращаем клон
        if clone, exists := cloned[n]; exists {
            return clone
        }

        // ВАЖНО: Регистрируем клон в map ДО рекурсивного обхода соседей!
        // Это гарантирует корректный возврат указателя при обратных ребрах.
        copyNode := &Node{
            Val:       n.Val,
            Neighbors: make([]*Node, 0, len(n.Neighbors)),
        }
        cloned[n] = copyNode

        // Рекурсивно клонируем все смежные вершины
        for _, neighbor := range n.Neighbors {
            copyNode.Neighbors = append(copyNode.Neighbors, dfs(neighbor))
        }

        return copyNode
    }

    return dfs(node)
}

Взгляд под капот: Mechanical Sympathy

1. Хеширование указателей в map[*Node]*Node

В Go тип ключа *Node является 64-битным адресом памяти:

• Для хеширования указателей рантайм использует сверхбыструю функцию memhash64 (прямое перемешивание 8 байт адреса через регистры ALU).
• Сравнение ключей при коллизиях — это простая инструкция CMPQ двух чисел, без разыменования указателей и без чтения полей структуры.
• Сложность поиска cloned[n] составляет $O(1)$ с минимальной константой процессорного времени.

2. Сборка мусора и циклические ссылки (GC Tracing vs Refcounting)

В языках со счетчиками ссылок (Python PyObject, C++ std::shared_ptr) взаимные ссылки двух узлов ($A \leftrightarrow B$) создают классическую утечку памяти (Memory Leak), требуя вмешательства тяжелого cycle detector'а.
В Go сборщик мусора использует алгоритм Tri-color Mark & Sweep:

• GC начинает трассировку исключительно с корневых объектов (Root Set: глобальные переменные, стек горутины).
• Если на граф больше нет внешних ссылок из активных горутин, весь циклический граф признается недостижимым и целиком освобождается за один проход сборщика.

Подводные камни и вопросы с собеседований

Резюме

Clone Graph учит технике изоморфного воспроизведения графов:

• Хеш-таблица сопоставления указателей map[*Node]*Node разрушает циклы.
• Регистрация клона в словаре до перехода к соседям — обязательный инвариант корректности.
• Рантайм Go эффективно работает с циклическими графами в куче благодаря трехцветной маркировке GC.

В следующей задаче мы возвращаемся к деревьям и исследуем накопление числовых инвариантов вдоль ветвей: 5. Path Sum.