Clone Graph (LeetCode 133): DFS con una Hash Map in Python

Clone Graph (LeetCode 133) ti chiede di restituire una copia profonda di un grafo non orientato connesso. L'idea chiave è una hash map che associa ogni nodo originale alla sua copia. Ti permette di creare ogni copia una sola volta e di collegare i vicini senza entrare in un ciclo infinito. Il tempo e lo spazio sono O(V + E).

Il problema

Ricevi un riferimento a un nodo di un grafo non orientato connesso. Ogni nodo ha un valore e una lista di vicini. Restituisci una copia profonda: nuovi nodi con gli stessi valori e le stesse connessioni, e nessun nodo condiviso con l'originale. L'input può essere None, nel qual caso restituisci None.

La classe del nodo è questa:

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

Perché non è solo una ricorsione

Un grafo può contenere cicli, e in un grafo non orientato ogni arco è un piccolo ciclo (A elenca B, e B elenca A). Una funzione di copia che richiama se stessa su ogni vicino non si fermerebbe mai. Devi ricordare quali nodi sono già stati copiati.

Approccio: mappa più ricerca in profondità

Mantieni un dizionario copies che associa un nodo originale al suo clone. Attraversa il grafo con uno stack. Quando incontri un vicino che non hai ancora copiato, crea il suo clone e inseriscilo nello stack. In ogni caso, aggiungi il clone del vicino alla lista dei vicini del clone corrente.

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]

Traccia

Prendi un grafo a quadrato, con 1 collegato a 2 e 4, 2 a 3, 3 a 4. Parti dal nodo 1: crea la copia 1, poi visita i vicini 2 e 4 del nodo 1, creando le copie di entrambi e collegandole alla copia 1. Estrai il nodo 4: i suoi vicini sono 1 e 3, quindi la copia 1 viene collegata (già presente), e la copia 3 viene creata e collegata. Estrai il nodo 3, poi il nodo 2, e i collegamenti rimanenti vengono aggiunti. Ogni nodo viene creato una sola volta, e ogni arco compare in entrambe le direzioni, perché ciascun estremo aggiunge l'altro alla propria lista.

In profondità o in ampiezza

Entrambi funzionano. Sostituisci lo stack con un deque e popleft() per la ricerca in ampiezza. L'unico requisito è la mappa. La ricorsione è più breve da scrivere, ma un grafo profondo può raggiungere il limite di ricorsione di Python, quindi la versione iterativa è più sicura.

Errori comuni

• Creare un nuovo clone ogni volta che si vede un nodo, il che duplica i nodi e genera un ciclo infinito.
• Copiare la lista dei vicini per riferimento, così il clone punta ai nodi originali.
• Dimenticare l'input None.
• Usare il valore del nodo come chiave della mappa quando i valori non sono garantiti unici. Usare l'oggetto nodo stesso è più sicuro.

Casi limite da testare

Come spiegarlo in un colloquio

1. Di' cosa significa copia profonda qui: nuovi nodi, stessa forma.
2. Fai notare i cicli e perché ti serve una mappa.
3. Descrivi la mappa da originale a clone, e l'attraversamento.
4. Scrivilo, poi illustra un esempio con due nodi.
5. Dichiara tempo O(V + E) e spazio O(V).

Ho testato il codice qui sopra su 3.000 grafi connessi casuali, verificando che la copia abbia gli stessi valori e archi e che nessun nodo sia condiviso con l'originale, prima di pubblicare. Un rapido controllo casuale come questo è una buona abitudine quando ti eserciti.

Esercizi correlati

Consulta il nostro Big O cheat sheet per i termini di complessità, la lista LeetCode Blind 75 per cosa esercitare dopo, e la guida all'assistente per colloqui di programmazione per come esercitarti.

Parla ad alta voce del tuo approccio mentre scrivi il codice. Una trascrizione mostra se hai enunciato l'osservazione chiave prima di scrivere. Segui le regole del datore di lavoro sugli strumenti di IA in qualsiasi valutazione dal vivo.