Clonar grafo (LeetCode 133): DFS con un mapa hash en Python

Clone Graph (LeetCode 133) te pide devolver una copia profunda de un grafo no dirigido y conexo. La idea clave es un mapa hash que va de cada nodo original a su copia. Te permite crear cada copia una sola vez y conectar los vecinos sin quedarte en un bucle infinito por los ciclos. El tiempo y el espacio son O(V + E).

El problema

Recibes una referencia a un nodo de un grafo no dirigido y conexo. Cada nodo tiene un valor y una lista de vecinos. Devuelve una copia profunda: nodos nuevos con los mismos valores y las mismas conexiones, y sin compartir ningún nodo con el original. La entrada puede ser None, en cuyo caso devuelves None.

La clase del nodo es así:

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

Por qué no es solo una recursión

Un grafo puede contener ciclos, y en un grafo no dirigido cada arista es un pequeño ciclo (A lista a B, y B lista a A). Una función de copia que se llame a sí misma sobre cada vecino nunca terminaría. Necesitas recordar qué nodos ya se copiaron.

Enfoque: mapa más búsqueda en profundidad

Mantén un diccionario copies que asocie cada nodo original con su clon. Recorre el grafo con una pila. Cuando encuentres un vecino que aún no has copiado, crea su clon y apílalo. En cualquier caso, añade el clon del vecino a la lista de vecinos del clon actual.

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]

Traza

Toma un grafo cuadrado: 1 conectado con 2 y 4, 2 con 3, 3 con 4. Empieza en el nodo 1: crea la copia 1 y luego visita los vecinos 2 y 4 del nodo 1, creando copias de ambos y enlazándolas con la copia 1. Saca el nodo 4: sus vecinos son 1 y 3, así que la copia 1 se enlaza (ya estaba) y se crea y enlaza la copia 3. Saca el nodo 3 y luego el nodo 2, y se añaden los enlaces restantes. Cada nodo se crea una vez, y cada arista aparece en ambos sentidos, porque cada extremo añade el otro a su propia lista.

En profundidad o en anchura

Ambos funcionan. Sustituye la pila por un deque y popleft() para hacerlo en anchura. El único requisito es el mapa. La recursión es más corta de escribir, pero un grafo profundo puede alcanzar el límite de recursión de Python, así que la versión iterativa es más segura.

Errores comunes

• Crear un clon nuevo cada vez que se ve un nodo, lo que duplica nodos y provoca un bucle infinito.
• Copiar la lista de vecinos por referencia, de modo que el clon apunta a los nodos originales.
• Olvidar el caso de entrada None.
• Usar el valor del nodo como clave del mapa cuando no se garantiza que los valores sean únicos. Usar el propio objeto nodo es más seguro.

Casos límite que probar

Cómo explicarlo en una entrevista

1. Di qué significa una copia profunda aquí: nodos nuevos, misma forma.
2. Señala los ciclos y por qué necesitas un mapa.
3. Describe el mapa de original a clon y el recorrido.
4. Escríbelo y luego recorre un ejemplo de dos nodos.
5. Indica O(V + E) de tiempo y O(V) de espacio.

Probé el código anterior con 3.000 grafos conexos aleatorios, comprobando que la copia tiene los mismos valores y aristas y que no comparte ningún nodo con el original, antes de publicarlo. Una comprobación aleatoria rápida como esa es un buen hábito cuando practicas.

Práctica relacionada

Consulta nuestra chuleta de Big O para los términos de complejidad, la lista LeetCode Blind 75 para saber qué practicar después, y la guía del asistente para entrevistas de programación para saber cómo practicar.

Explica tu enfoque en voz alta mientras programas. Una transcripción muestra si enunciaste la observación clave antes de escribir. Sigue las normas del empleador sobre herramientas de IA en cualquier evaluación en vivo.