Cloner un graphe (LeetCode 133) : DFS avec une table de hachage en Python

Clone Graph (LeetCode 133) vous demande de renvoyer une copie profonde d'un graphe non orienté connexe. L'idée clé est une table de hachage qui associe chaque nœud d'origine à sa copie. Elle vous permet de créer chaque copie une seule fois et de relier les voisins sans boucler indéfiniment sur les cycles. Le temps et l'espace sont en O(V + E).

Le problème

On vous donne une référence à un nœud d'un graphe non orienté connexe. Chaque nœud possède une valeur et une liste de voisins. Renvoyez une copie profonde : de nouveaux nœuds avec les mêmes valeurs et les mêmes connexions, et aucun nœud partagé avec l'original. L'entrée peut être None, auquel cas renvoyez None.

La classe du nœud ressemble à ceci :

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

Pourquoi ce n'est pas une simple récursion

Un graphe peut contenir des cycles, et dans un graphe non orienté chaque arête est un mini-cycle (A liste B, et B liste A). Une fonction de copie qui s'appelle elle-même sur chaque voisin ne s'arrêterait jamais. Il faut se souvenir des nœuds déjà copiés.

Approche : table de correspondance et parcours en profondeur

Gardez un dictionnaire copies qui associe un nœud d'origine à son clone. Parcourez le graphe avec une pile. Quand vous rencontrez un voisin que vous n'avez pas encore copié, créez son clone et empilez-le. Dans tous les cas, ajoutez le clone du voisin à la liste de voisins du clone courant.

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]

Déroulé

Prenez un graphe en carré, 1 relié à 2 et 4, 2 à 3, 3 à 4. Partez du nœud 1 : créez la copie 1, puis visitez les voisins 2 et 4 du nœud 1, en créant des copies pour les deux et en les reliant à la copie 1. Dépilez le nœud 4 : ses voisins sont 1 et 3, donc la copie 1 est reliée (déjà présente), et la copie 3 est créée et reliée. Dépilez le nœud 3, puis le nœud 2, et les liens restants sont ajoutés. Chaque nœud est créé une seule fois, et chaque arête apparaît dans les deux sens, car chaque extrémité ajoute l'autre à sa propre liste.

En profondeur ou en largeur

Les deux fonctionnent. Remplacez la pile par un deque et popleft() pour un parcours en largeur. La seule exigence est la table de correspondance. La récursion est plus courte à écrire, mais un graphe profond peut atteindre la limite de récursion de Python, donc la version itérative est plus sûre.

Erreurs courantes

• Créer un nouveau clone chaque fois qu'un nœud est vu, ce qui duplique les nœuds et boucle indéfiniment.
• Copier la liste de voisins par référence, de sorte que le clone pointe vers les nœuds d'origine.
• Oublier le cas d'entrée None.
• Utiliser la valeur du nœud comme clé de la table alors que les valeurs ne sont pas garanties uniques. Utiliser l'objet nœud lui-même est plus sûr.

Cas limites à tester

Comment l'expliquer en entretien

1. Dites ce que signifie une copie profonde ici : de nouveaux nœuds, la même forme.
2. Soulignez les cycles et pourquoi vous avez besoin d'une table de correspondance.
3. Décrivez la table qui associe l'original au clone, et le parcours.
4. Écrivez-le, puis déroulez un exemple à deux nœuds.
5. Indiquez une complexité en O(V + E) en temps et O(V) en espace.

J'ai testé le code ci-dessus sur 3 000 graphes connexes aléatoires, en vérifiant que la copie a les mêmes valeurs et les mêmes arêtes et qu'aucun nœud n'est partagé avec l'original, avant de publier. Une vérification aléatoire rapide comme celle-ci est une bonne habitude à prendre lorsque vous vous entraînez.

Entraînement associé

Consultez notre aide-mémoire Big O pour les termes de complexité, la liste LeetCode Blind 75 pour savoir quoi travailler ensuite, et le guide de l'assistant d'entretien de codage pour savoir comment vous entraîner.

Exposez votre approche à voix haute pendant que vous codez. Une transcription montre si vous avez énoncé l'observation clé avant d'écrire. Respectez les règles de l'employeur concernant les outils d'IA lors de toute évaluation en direct.