133. Clone Graph

Medium

Description

給定一個無向連通圖中某個節點的參考，回傳該圖的深拷貝 (deep copy)。每個節點包含一個值和一個鄰居列表。

Example:

Input: adjList = [[2,4],[1,3],[2,4],[1,3]] Output: [[2,4],[1,3],[2,4],[1,3]]

Intuition#

用 HashMap 記錄「原始節點 -> 複製節點」的映射，遍歷圖時遇到已複製的節點直接回傳映射。

深拷貝圖的關鍵是避免重複建立節點（圖可能有環）
使用 HashMap 紀錄已複製的節點，同時充當 visited 的角色
DFS 或 BFS 皆可，差異只在遍歷順序

Approaches#

1: BFS#

概念: 從起始節點開始 BFS，每次出隊時建立鄰居的複製品並連接
時間複雜度: O(V + E)
空間複雜度: O(V)

class Solution {
    fun cloneGraph(node: Node?): Node? {
        if (node == null) return null
        val map = HashMap<Node, Node>()
        val queue: ArrayDeque<Node> = ArrayDeque()
        map[node] = Node(node.`val`)
        queue.add(node)

        while (queue.isNotEmpty()) {
            val cur = queue.removeFirst()
            for (neighbor in cur.neighbors) {
                if (neighbor != null && neighbor !in map) {
                    map[neighbor] = Node(neighbor.`val`)
                    queue.add(neighbor)
                }
                map[cur]!!.neighbors.add(map[neighbor])
            }
        }
        return map[node]
    }
}

⭐2: DFS（遞迴）#

概念: 遞迴訪問每個節點，利用 HashMap 避免重複訪問並建立映射關係
時間複雜度: O(V + E)
空間複雜度: O(V)

class Solution {
    private val map = HashMap<Node, Node>()

    fun cloneGraph(node: Node?): Node? {
        if (node == null) return null
        if (node in map) return map[node]

        val clone = Node(node.`val`)
        map[node] = clone
        for (neighbor in node.neighbors) {
            clone.neighbors.add(cloneGraph(neighbor))
        }
        return clone
    }
}

🔑 Takeaways#

Pattern: 圖的深拷貝 – HashMap 映射 + DFS/BFS 遍歷
關鍵技巧: HashMap 同時解決「是否已訪問」和「原始到複製的映射」兩個問題