Копирование графа

Копирование графа

Задача

Создать глубокую копию связного неориентированного графа. Каждый узел содержит значение (int) и список соседей.

Основная сложность: граф может содержать циклы, поэтому нужно отслеживать уже скопированные узлы, чтобы не зациклиться.

Решение 1: DFS с Hashmap (Рекурсивное)

Используем глубинный поиск с hashmap для отслеживания скопированных узлов.

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

def cloneGraph(node):
    """
    Копирует граф используя DFS.
    
    Идея:
    1. Используем hashmap: исходный узел → копированный узел
    2. Рекурсивно копируем каждый узел
    3. Связываем копированные узлы через neighbours
    
    Временная сложность: O(V + E) — посещаем каждый узел и ребро один раз
    Пространственная сложность: O(V) — hashmap + стек рекурсии
    """
    if not node:
        return None
    
    # Hashmap для отслеживания уже скопированных узлов
    visited = {}
    
    def dfs(original_node):
        # Если уже скопировали, возвращаем копию
        if original_node in visited:
            return visited[original_node]
        
        # Создаём копию текущего узла
        copy_node = Node(original_node.val)
        visited[original_node] = copy_node
        
        # Рекурсивно копируем соседей и связываем
        for neighbor in original_node.neighbors:
            copy_node.neighbors.append(dfs(neighbor))
        
        return copy_node
    
    return dfs(node)

# Пример использования
# Граф: 1 — 2
#       |   |
#       3 — 4

node1 = Node(1)
node2 = Node(2)
node3 = Node(3)
node4 = Node(4)

node1.neighbors = [node2, node3]
node2.neighbors = [node1, node4]
node3.neighbors = [node1, node4]
node4.neighbors = [node2, node3]

copied = cloneGraph(node1)
print(copied.val)  # 1
print(copied is node1)  # False (разные объекты)
print(copied.neighbors[0].val)  # 2

Решение 2: BFS с Queue (Итеративное)

Итеративный подход с использованием очереди.

from collections import deque

def cloneGraph_bfs(node):
    """
    Копирует граф используя BFS.
    Более интуитивно для некоторых, проще избежать stack overflow.
    
    Временная сложность: O(V + E)
    Пространственная сложность: O(V)
    """
    if not node:
        return None
    
    # Hashmap для отслеживания скопированных узлов
    visited = {node: Node(node.val)}
    queue = deque([node])
    
    while queue:
        original = queue.popleft()
        
        # Для каждого соседа оригинального узла
        for neighbor in original.neighbors:
            # Если сосед ещё не скопирован, создаём копию
            if neighbor not in visited:
                visited[neighbor] = Node(neighbor.val)
                queue.append(neighbor)
            
            # Добавляем ребро между копиями
            visited[original].neighbors.append(visited[neighbor])
    
    return visited[node]

Решение 3: DFS итеративный (со стеком)

Итеративный DFS с явным стеком.

def cloneGraph_iterative(node):
    """
    Итеративный DFS со стеком.
    Похож на DFS рекурсивный, но без вызовов функций.
    """
    if not node:
        return None
    
    visited = {node: Node(node.val)}
    stack = [node]
    
    while stack:
        original = stack.pop()
        
        for neighbor in original.neighbors:
            if neighbor not in visited:
                visited[neighbor] = Node(neighbor.val)
                stack.append(neighbor)
            
            visited[original].neighbors.append(visited[neighbor])
    
    return visited[node]

Сравнение подходов

Пошаговое выполнение

Для графа:

1 — 2
|   |
3 — 4

DFS подход:

Шаг 1: dfs(1)
  visited = {1: Node(1)}
  Соседи: [2, 3]
  
Шаг 2: dfs(2)
  visited = {1: Node(1), 2: Node(2)}
  Соседи: [1, 4]
  - dfs(1) уже в visited, используем существующую копию
  
Шаг 3: dfs(4)
  visited = {1: Node(1), 2: Node(2), 4: Node(4)}
  Соседи: [2, 3]
  - dfs(2) уже в visited
  
Шаг 4: dfs(3)
  visited = {1: Node(1), 2: Node(2), 4: Node(4), 3: Node(3)}
  Соседи: [1, 4]
  - Оба уже в visited

Результат: граф скопирован, все связи сохранены

Проверка корректности копии

def test_clone():
    # Создаём граф
    node1 = Node(1)
    node2 = Node(2)
    node3 = Node(3)
    node4 = Node(4)
    
    node1.neighbors = [node2, node3]
    node2.neighbors = [node1, node4]
    node3.neighbors = [node1, node4]
    node4.neighbors = [node2, node3]
    
    # Копируем
    cloned = cloneGraph(node1)
    
    # Проверяем
    assert cloned.val == 1
    assert cloned is not node1  # Разные объекты
    assert cloned.neighbors[0].val == 2
    assert cloned.neighbors[0] is not node2  # Разные объекты
    
    # Проверяем циклические ссылки
    assert cloned.neighbors[0].neighbors[0] is cloned  # Замкнутый цикл
    
    print("Все проверки пройдены!")

test_clone()

Граф с изолированным узлом

def test_isolated_node():
    # Единственный узел без соседей
    node = Node(1, [])
    
    cloned = cloneGraph(node)
    
    assert cloned.val == 1
    assert cloned is not node
    assert len(cloned.neighbors) == 0
    
    print("Тест пройден!")

test_isolated_node()

Граф с самоссылкой

def test_self_loop():
    # Узел, указывающий на себя
    node = Node(1)
    node.neighbors = [node]
    
    cloned = cloneGraph(node)
    
    assert cloned.val == 1
    assert cloned.neighbors[0] is cloned  # Указывает на себя
    assert cloned is not node
    
    print("Тест пройден!")

test_self_loop()

Визуализация процесса копирования

def print_graph(node, visited_nodes=None):
    """
    Выводит граф в читаемом формате.
    """
    if visited_nodes is None:
        visited_nodes = set()
    
    if id(node) in visited_nodes:
        return
    
    visited_nodes.add(id(node))
    neighbor_vals = [n.val for n in node.neighbors]
    print(f"Node {node.val}: neighbors {neighbor_vals}")
    
    for neighbor in node.neighbors:
        print_graph(neighbor, visited_nodes)

# Использование
node1 = Node(1)
node2 = Node(2)
node1.neighbors = [node2]
node2.neighbors = [node1]

print("Оригинал:")
print_graph(node1)

cloned = cloneGraph(node1)

print("\nКопия:")
print_graph(cloned)

print("\nОригинал и копия — разные объекты:")
print(f"node1 is cloned: {node1 is cloned}")
print(f"node1 == cloned (по структуре): {node1.val == cloned.val}")

Анализ сложности

Временная сложность: O(V + E)

• Посещаем каждый узел (V) ровно один раз
• Проходим по каждому ребру (E) один раз

Пространственная сложность: O(V)

• visited hashmap: O(V)
• Стек рекурсии или queue: O(V) в худшем случае (для связного графа)
• В худшем случае (звёзда): глубина O(1)
• В худшем случае (цепь): глубина O(V)

Особенности неориентированного графа

Для неориентированного графа каждое ребро двусторонне:

• Если 1→2, то и 2→1
• При копировании нужно правильно обработать оба направления
• visited hashmap предотвращает бесконечную рекурсию

Рекомендации для интервью

1. Спросите про граф: ориентированный или нет? Циклы? Изолированные узлы?
2. Предложите DFS рекурсивный как первое решение (просто)
3. Обсудите BFS как альтернативу (итеративно)
4. Покажите примеры тестирования (включая граф с циклами)
5. Объясните почему нужен visited hashmap (предотвращение бесконечных циклов)

Заключение

Это задача на DFS/BFS и работу с графами. Ключевые моменты:

• Используй hashmap для отслеживания копированных узлов
• Обрабатывай циклы правильно
• Понимай разницу между глубокой и поверхностной копией
• Практикуй как рекурсивный, так и итеративный подходы

Часто встречается на интервью у Google, Apple, Meta.