Clone Graph (LeetCode 133): DFS met een hashmap in Python

Clone Graph (LeetCode 133) vraagt je om een diepe kopie van een samenhangende ongerichte graaf terug te geven. Het belangrijkste idee is een hashmap van elk origineel knooppunt naar zijn kopie. Daarmee maak je elke kopie één keer aan en verbind je de buren zonder eindeloos door te lopen op cycli. Tijd en ruimte zijn O(V + E).

Het probleem

Je krijgt een verwijzing naar één knooppunt van een samenhangende ongerichte graaf. Elk knooppunt heeft een waarde en een lijst met buren. Geef een diepe kopie terug: nieuwe knooppunten met dezelfde waarden en dezelfde verbindingen, en geen enkel knooppunt dat gedeeld wordt met het origineel. De invoer kan None zijn, en dan geef je None terug.

De node-klasse ziet er zo uit:

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

Waarom het niet gewoon recursie is

Een graaf kan cycli bevatten, en in een ongerichte graaf is elke rand een kleine cyclus (A noemt B, en B noemt A). Een kopieerfunctie die zichzelf op elke buur aanroept, stopt nooit. Je moet onthouden welke knooppunten al gekopieerd zijn.

Aanpak: map plus diepte-eerst zoeken

Houd een dictionary copies bij die elk origineel knooppunt aan zijn kloon koppelt. Doorloop de graaf met een stack. Als je een buur tegenkomt die je nog niet hebt gekopieerd, maak je zijn kloon aan en push je die. In beide gevallen voeg je de kloon van de buur toe aan de burenlijst van de huidige kloon.

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]

Trace

Neem een vierkante graaf: 1 verbonden met 2 en 4, 2 met 3, 3 met 4. Begin bij knooppunt 1: maak kopie 1, bezoek dan de buren 2 en 4 van knooppunt 1, maak kopieën voor beide en verbind ze met kopie 1. Pop knooppunt 4: zijn buren zijn 1 en 3, dus kopie 1 wordt verbonden (staat er al) en kopie 3 wordt aangemaakt en verbonden. Pop knooppunt 3, dan knooppunt 2, en de resterende verbindingen worden toegevoegd. Elk knooppunt wordt één keer aangemaakt, en elke rand verschijnt in beide richtingen, omdat elk uiteinde het andere aan zijn eigen lijst toevoegt.

Diepte-eerst of breedte-eerst

Beide werken. Vervang de stack door een deque en popleft() voor breedte-eerst. Het enige wat vereist is, is de map. Recursie is korter om te schrijven, maar een diepe graaf kan tegen Python's recursielimiet aanlopen, dus de iteratieve versie is veiliger.

Veelgemaakte fouten

• Elke keer dat een knooppunt wordt gezien een nieuwe kloon maken, waardoor knooppunten worden gedupliceerd en het oneindig doorloopt.
• De burenlijst by reference kopiëren, zodat de kloon terugwijst naar originele knooppunten.
• De None-invoer vergeten.
• De waarde van het knooppunt als sleutel in de map gebruiken terwijl waarden niet gegarandeerd uniek zijn. Het knooppuntobject zelf gebruiken is veiliger.

Randgevallen om te testen

Hoe je het uitlegt in een sollicitatiegesprek

1. Zeg wat een diepe kopie hier betekent: nieuwe knooppunten, dezelfde vorm.
2. Wijs op de cycli en waarom je een map nodig hebt.
3. Beschrijf de map van origineel naar kloon, en de traversal.
4. Schrijf het uit en loop dan door een voorbeeld met twee knooppunten.
5. Noem O(V + E) tijd en O(V) ruimte.

Ik heb de code hierboven getest op 3.000 willekeurige samenhangende grafen, waarbij ik controleerde of de kopie dezelfde waarden en randen heeft en of geen enkel knooppunt gedeeld wordt met het origineel, voordat ik publiceerde. Zo'n snelle willekeurige controle is een goede gewoonte tijdens het oefenen.

Gerelateerde oefening

Bekijk onze Big O cheat sheet voor de complexiteitstermen, de LeetCode Blind 75-lijst voor wat je hierna kunt oefenen, en de gids voor de coding interview-assistent voor hoe je oefent.

Praat je aanpak hardop door terwijl je codeert. Een transcript laat zien of je de belangrijkste observatie hebt benoemd voordat je begon te schrijven. Volg de regels van de werkgever over AI-tools bij elke live assessment.