Clone Graph (LeetCode 133): Pythonでのハッシュマップを使ったDFS

Clone Graph（LeetCode 133）は、連結な無向グラフのディープコピーを返す問題です。鍵となる考え方は、各元ノードからそのコピーへのハッシュマップです。これにより、各コピーを一度だけ作成し、サイクルで無限ループに陥ることなく隣接ノードを接続できます。時間と空間は O(V + E) です。

問題

連結な無向グラフの1つのノードへの参照が与えられます。各ノードは値と隣接ノードのリストを持ちます。ディープコピーを返してください。つまり、同じ値と同じ接続を持つ新しいノードで、元のグラフと共有するノードがないものです。入力は None の可能性があり、その場合は None を返します。

ノードクラスは次のようになります。

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

単なる再帰ではない理由

グラフにはサイクルが含まれることがあり、無向グラフではすべての辺が小さなサイクルです（AがBを挙げ、BがAを挙げる）。すべての隣接ノードに対して自分自身を呼び出すコピー関数は決して停止しません。どのノードがすでにコピーされたかを覚えておく必要があります。

アプローチ：マップと深さ優先探索

元ノードをそのクローンに対応付ける辞書 copies を保持します。スタックでグラフをたどります。まだコピーしていない隣接ノードに出会ったら、そのクローンを作成してプッシュします。いずれの場合も、隣接ノードのクローンを現在のクローンの隣接リストに追加します。

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]

トレース

正方形のグラフを考えます。1は2と4に接続、2は3に、3は4に接続。ノード1から開始：コピー1を作成し、次にノード1の隣接ノード2と4を訪れ、両方のコピーを作成してコピー1にリンクします。ノード4をポップ：その隣接ノードは1と3なので、コピー1がリンクされ（すでに存在）、コピー3が作成されてリンクされます。ノード3、次にノード2をポップし、残りのリンクが追加されます。すべてのノードは一度だけ作成され、すべての辺は両方向に現れます。なぜなら各端点が他方を自身のリストに追加するからです。

深さ優先か幅優先か

どちらでも動作します。幅優先にするには、スタックを deque と popleft() に置き換えます。唯一の要件はマップです。再帰は書くのが短いですが、深いグラフではPythonの再帰制限に達する可能性があるため、反復版の方が安全です。

よくある間違い

• ノードが見られるたびに新しいクローンを作成し、ノードが重複して無限ループになる。
• 隣接リストを参照でコピーし、クローンが元のノードを指してしまう。
• None 入力の処理を忘れる。
• 値が一意であることが保証されていないのに、ノードの値をマップのキーとして使う。ノードオブジェクト自体を使う方が安全です。

テストすべきエッジケース

面接での説明の仕方

1. ここでのディープコピーの意味を述べる：新しいノード、同じ形。
2. サイクルを指摘し、なぜマップが必要かを説明する。
3. 元からクローンへのマップと、たどり方を説明する。
4. 書いてから、2ノードの例を順にたどる。
5. 時間 O(V + E)、空間 O(V) を述べる。

私は公開前に、上記のコードを3,000個のランダムな連結グラフでテストし、コピーが同じ値と辺を持ち、元のグラフと共有するノードがないことを確認しました。このような簡単なランダムチェックは、練習するときの良い習慣です。

関連する練習

複雑さの用語についてはBig O チートシートを、次に何を練習すべきかについてはLeetCode Blind 75 リストを、練習方法についてはコーディング面接アシスタントガイドをご覧ください。

コードを書きながら、アプローチを声に出して説明しましょう。文字起こしを見れば、書く前に鍵となる観察を述べたかどうかがわかります。ライブ評価では、AIツールに関する雇用主のルールに従ってください。