Graph klonen (LeetCode 133): DFS mit einer Hash-Map in Python

Clone Graph (LeetCode 133) verlangt von dir, eine tiefe Kopie eines zusammenhängenden ungerichteten Graphen zurückzugeben. Die Kernidee ist eine Hash-Map von jedem Originalknoten zu seiner Kopie. Sie ermöglicht es dir, jede Kopie genau einmal zu erstellen und Nachbarn zu verbinden, ohne bei Zyklen endlos zu schleifen. Zeit und Speicher sind O(V + E).

Das Problem

Du bekommst eine Referenz auf einen Knoten eines zusammenhängenden ungerichteten Graphen. Jeder Knoten hat einen Wert und eine Liste von Nachbarn. Gib eine tiefe Kopie zurück: neue Knoten mit denselben Werten und denselben Verbindungen, und kein Knoten wird mit dem Original geteilt. Die Eingabe kann None sein, dann gib None zurück.

Die Knotenklasse sieht so aus:

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

Warum es nicht einfach nur Rekursion ist

Ein Graph kann Zyklen enthalten, und in einem ungerichteten Graphen ist jede Kante ein winziger Zyklus (A listet B, und B listet A). Eine Kopierfunktion, die sich selbst für jeden Nachbarn aufruft, würde nie aufhören. Du musst dir merken, welche Knoten bereits kopiert wurden.

Ansatz: Map plus Tiefensuche

Führe ein Dictionary copies, das einen Originalknoten auf seinen Klon abbildet. Durchlaufe den Graphen mit einem Stack. Wenn du auf einen Nachbarn triffst, den du noch nicht kopiert hast, erstelle seinen Klon und lege ihn auf den Stack. In beiden Fällen hängst du den Klon des Nachbarn an die Nachbarliste des aktuellen Klons an.

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]

Durchlauf

Nimm einen quadratischen Graphen, 1 verbunden mit 2 und 4, 2 mit 3, 3 mit 4. Starte bei Knoten 1: erstelle Kopie 1, dann besuche die Nachbarn 2 und 4 von Knoten 1, erstelle Kopien für beide und verlinke sie mit Kopie 1. Hole Knoten 4 vom Stack: seine Nachbarn sind 1 und 3, also wird Kopie 1 verlinkt (bereits vorhanden), und Kopie 3 wird erstellt und verlinkt. Hole Knoten 3, dann Knoten 2 vom Stack, und die restlichen Verbindungen werden hinzugefügt. Jeder Knoten wird einmal erstellt, und jede Kante erscheint in beide Richtungen, weil jeder Endpunkt den anderen zu seiner eigenen Liste hinzufügt.

Tiefensuche oder Breitensuche

Beides funktioniert. Ersetze den Stack durch eine deque und popleft() für die Breitensuche. Die einzige Voraussetzung ist die Map. Rekursion ist kürzer zu schreiben, aber ein tiefer Graph kann das Rekursionslimit von Python erreichen, daher ist die iterative Version sicherer.

Häufige Fehler

• Bei jedem Auftreten eines Knotens einen neuen Klon erstellen, was Knoten dupliziert und endlos schleift.
• Die Nachbarliste per Referenz kopieren, sodass der Klon zurück auf Originalknoten zeigt.
• Die None-Eingabe vergessen.
• Den Knotenwert als Map-Schlüssel verwenden, wenn Werte nicht garantiert eindeutig sind. Das Knotenobjekt selbst zu verwenden ist sicherer.

Randfälle zum Testen

Wie du es im Interview erklärst

1. Sag, was eine tiefe Kopie hier bedeutet: neue Knoten, gleiche Form.
2. Weise auf die Zyklen hin und darauf, warum du eine Map brauchst.
3. Beschreibe die Map von Original zu Klon und den Durchlauf.
4. Schreibe es, dann geh ein Beispiel mit zwei Knoten durch.
5. Nenne O(V + E) Zeit und O(V) Speicher.

Ich habe den obigen Code an 3.000 zufälligen zusammenhängenden Graphen getestet und geprüft, dass die Kopie dieselben Werte und Kanten hat und dass kein Knoten mit dem Original geteilt wird, bevor ich ihn veröffentlicht habe. Ein solcher schneller Zufallstest ist eine gute Angewohnheit beim Üben.

Verwandte Übung

Sieh dir unseren Big-O-Spickzettel für die Komplexitätsbegriffe an, die LeetCode Blind 75 Liste für das, was du als Nächstes üben solltest, und den Leitfaden zum Coding-Interview-Assistenten für das Üben.

Sprich deinen Ansatz laut durch, während du codest. Ein Transkript zeigt, ob du die entscheidende Beobachtung vor dem Schreiben genannt hast. Befolge die Regeln des Arbeitgebers zu KI-Tools in jeder Live-Bewertung.