LeetCode #133 Clone Graph: คัดลอกวงจรด้วยตาราง old-to-new

LeetCode #133 ให้ reference ไปยังโหนดหนึ่งใน undirected connected graph แล้วขอ deep copy ทั้งกราฟ ปัญหาไม่ได้อยู่ที่สร้างโหนดใหม่ แต่อยู่ที่วงจร: ถ้าเดิน A→B→A แล้วสร้างใหม่ทุกครั้ง โปรแกรมจะวนไม่จบหรือได้สำเนา A หลายตัว

หัวใจจึงเป็นตาราง ต้นฉบับ -> สำเนา เหมือนย้ายออฟฟิศแล้วแจกบัตรพนักงานใหม่ พอพบคนเดิมอีกครั้งต้องใช้บัตรใหม่ใบเดิม ไม่ออกบัตรซ้ำ จากนั้นค่อยเชื่อมความสัมพันธ์ระหว่างสำเนาเท่านั้น

วิธี 1: DFS แบบ recursive

เมื่อพบโหนดใหม่ สร้างสำเนาและบันทึกลง map ก่อน เดินเพื่อนบ้าน จากนั้น clone เพื่อนบ้านแต่ละตัว recursively ใช้เวลา O(V+E) และ map O(V) ส่วน call stack สูงสุด O(V) โค้ดกระชับและเป็น best default ภายใต้ constraints ของโจทย์ ที่มีโหนดไม่มาก เพราะสะท้อนนิยามกราฟโดยตรง

วิธี 2: BFS ด้วย queue

สร้างสำเนาโหนดเริ่ม บันทึก map แล้วใช้ queue เดินเป็นชั้น ถ้าเพื่อนบ้านยังไม่มีสำเนาจึงสร้างและ enqueue จากนั้นต่อ edge ทุกเส้น เวลา O(V+E), map O(V) และ queue สูงสุด O(V) เช่นกัน ข้อดีคือไม่เสี่ยง recursion limit เมื่อกราฟลึกมาก และ debug ตามลำดับชั้นง่ายกว่า

from __future__ import annotations

from collections import deque
import unittest


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


def clone_dfs(node: Node | None) -> Node | None:
    copies: dict[Node, Node] = {}

    def clone(current: Node) -> Node:
        if current in copies:
            return copies[current]
        copy = Node(current.val)
        copies[current] = copy
        copy.neighbors = [clone(neighbor) for neighbor in current.neighbors]
        return copy

    return None if node is None else clone(node)


def clone_bfs(node: Node | None) -> Node | None:
    if node is None:
        return None
    copies = {node: Node(node.val)}
    pending = deque([node])
    while pending:
        current = pending.popleft()
        for neighbor in current.neighbors:
            if neighbor not in copies:
                copies[neighbor] = Node(neighbor.val)
                pending.append(neighbor)
            copies[current].neighbors.append(copies[neighbor])
    return copies[node]


def snapshot(start: Node | None) -> dict[int, list[int]]:
    if start is None:
        return {}
    result: dict[int, list[int]] = {}
    pending = deque([start])
    seen = {start}
    while pending:
        node = pending.popleft()
        result[node.val] = sorted(neighbor.val for neighbor in node.neighbors)
        for neighbor in node.neighbors:
            if neighbor not in seen:
                seen.add(neighbor)
                pending.append(neighbor)
    return result


class CloneGraphTests(unittest.TestCase):
    def graph_with_cycle_and_self_loop(self) -> Node:
        one, two, three = Node(1), Node(2), Node(3)
        one.neighbors = [two, three]
        two.neighbors = [one, three]
        three.neighbors = [one, two, three]
        return one

    def test_none(self):
        self.assertIsNone(clone_dfs(None))
        self.assertIsNone(clone_bfs(None))

    def test_both_methods_make_deep_copy(self):
        for solve in (clone_dfs, clone_bfs):
            original = self.graph_with_cycle_and_self_loop()
            cloned = solve(original)
            self.assertEqual(snapshot(cloned), snapshot(original))
            self.assertIsNot(cloned, original)
            self.assertTrue(all(a is not b for a, b in zip(cloned.neighbors, original.neighbors)))
            cloned.val = 99
            self.assertEqual(original.val, 1)


if __name__ == "__main__":
    unittest.main()

Decision table

เงื่อนไข	Recursive DFS	Iterative BFS
Input เล็ก / readability	สั้นและตรงนิยาม	มี queue เพิ่ม
กราฟลึกมาก	เสี่ยง recursion limit	ปลอดภัยกว่า
Memory จำกัด	map + stack O(V)	map + queue O(V)
โครงสร้างคล้าย tree	เหมาะ	เหมาะ
Streaming input	ทำไม่ได้จาก Node API; ต้องมี graph ครบ	ทำไม่ได้เช่นกัน
ลำดับเพื่อนบ้านสำคัญ	รักษาตาม list	รักษาตาม list
ห้ามแก้ input	ได้	ได้

Edge cases และ trade-offs

Input None ต้องคืน None; โหนดเดียวอาจไม่มีเพื่อนบ้านหรือมี self-loop; ค่า val ไม่ควรใช้เป็น key แทน object identity เว้นแต่สัญญารับประกัน unique จริง เพราะสองโหนดอาจมีค่าเท่ากันในระบบทั่วไป บันทึกสำเนาลง map ก่อน recursion เสมอ ไม่เช่นนั้น self-loop จะวนทันที

Tests ไม่ได้เช็กแค่ adjacency เท่ากัน แต่เช็กว่า object สำเนาไม่ใช่ object เดิมและแก้สำเนาแล้วต้นฉบับไม่เปลี่ยน นี่คือความหมายของ deep copy ที่สำคัญกว่าการพิมพ์ค่าเหมือนกัน

Recap

• ใช้ object ต้นฉบับเป็น key ของตาราง old-to-new
• บันทึกสำเนาก่อนเดินเพื่อนบ้านเพื่อหยุดวงจร
• ใช้ DFS เป็น default เมื่อกราฟไม่ลึกเกิน stack
• เปลี่ยนเป็น BFS เมื่อกราฟลึกหรืออยากควบคุม traversal เอง