Clone Graph (LeetCode 133): DFS com um Hash Map em Python

Clonar Grafo (LeetCode 133) pede que você retorne uma cópia profunda de um grafo não direcionado conectado. A ideia central é um hash map de cada nó original para sua cópia. Ele permite criar cada cópia uma única vez e conectar os vizinhos sem entrar em loop infinito nos ciclos. O tempo e o espaço são O(V + E).

O problema

Você recebe uma referência a um nó de um grafo não direcionado conectado. Cada nó tem um valor e uma lista de vizinhos. Retorne uma cópia profunda: novos nós com os mesmos valores e as mesmas conexões, e nenhum nó compartilhado com o original. A entrada pode ser None, e nesse caso retorne None.

A classe do nó é assim:

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

Por que não é só uma recursão

Um grafo pode conter ciclos, e em um grafo não direcionado toda aresta é um pequeno ciclo (A lista B, e B lista A). Uma função de cópia que chama a si mesma em cada vizinho nunca pararia. Você precisa lembrar quais nós já foram copiados.

Abordagem: map mais busca em profundidade

Mantenha um dicionário copies que mapeia um nó original para seu clone. Percorra o grafo com uma pilha. Quando encontrar um vizinho que você ainda não copiou, crie seu clone e empilhe-o. De qualquer forma, adicione o clone do vizinho à lista de vizinhos do clone atual.

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]

Traço

Considere um grafo quadrado, 1 conectado a 2 e 4, 2 a 3, 3 a 4. Comece no nó 1: crie a cópia 1, depois visite os vizinhos 2 e 4 do nó 1, criando cópias para ambos e ligando-os à cópia 1. Desempilhe o nó 4: seus vizinhos são 1 e 3, então a cópia 1 é ligada (já estava lá), e a cópia 3 é criada e ligada. Desempilhe o nó 3, depois o nó 2, e as ligações restantes são adicionadas. Cada nó é criado uma vez, e cada aresta aparece nos dois sentidos, porque cada extremidade adiciona a outra à sua própria lista.

Busca em profundidade ou em largura

Ambas funcionam. Substitua a pilha por um deque e popleft() para busca em largura. O único requisito é o map. A recursão é mais curta de escrever, mas um grafo profundo pode atingir o limite de recursão do Python, então a versão iterativa é mais segura.

Erros comuns

• Criar um novo clone toda vez que um nó é visto, o que duplica nós e entra em loop infinito.
• Copiar a lista de vizinhos por referência, fazendo o clone apontar de volta para os nós originais.
• Esquecer a entrada None.
• Usar o valor do nó como chave do map quando os valores não têm garantia de serem únicos. Usar o próprio objeto do nó é mais seguro.

Casos extremos para testar

Como explicar isso em uma entrevista

1. Diga o que uma cópia profunda significa aqui: novos nós, mesma forma.
2. Aponte os ciclos e por que você precisa de um map.
3. Descreva o map de original para clone, e a travessia.
4. Escreva, depois percorra um exemplo de dois nós.
5. Declare tempo O(V + E) e espaço O(V).

Testei o código acima em 3.000 grafos conectados aleatórios, verificando que a cópia tem os mesmos valores e arestas e que nenhum nó é compartilhado com o original, antes de publicar. Uma verificação aleatória rápida como essa é um bom hábito quando você pratica.

Prática relacionada

Veja nosso Big O cheat sheet para os termos de complexidade, a lista LeetCode Blind 75 para o que praticar em seguida, e o guia do assistente de entrevista de programação para saber como praticar.

Fale sobre sua abordagem em voz alta enquanto programa. Uma transcrição mostra se você declarou a observação principal antes de escrever. Siga as regras da empresa sobre ferramentas de IA em qualquer avaliação ao vivo.