LeetCode 133 Clone Graph：無向圖深拷貝 BFS/DFS 完整解法

題目

給定無向連通圖的一個節點引用，每個節點含 label 與 neighbors 列表。回傳圖的深拷貝 (新節點、新邊)。

核心難點

• 圖含環，需避免重複訪問/無限遞迴。
• 需建立 原節點 → 複製節點 的映射，確保同一原節點只複製一次，且鄰居關係正確指向複製節點。

通用模板 (BFS/DFS 通用)

1. 若輸入為 null，回傳 null。
2. 建立 unordered_map cloneMap。
3. 建立容器 (queue/stack) 放入起始節點，建立其複製節點放入 map。
4. 迴圈：取出節點 cur，遍歷其 neighbors：
   • 若鄰居 nbr 不在 map，建立複製節點、放入 map、加入容器。
   • 將 cloneMap[nbr] 加入 cloneMap[cur]->neighbors。
5. 回傳 cloneMap[原起始節點]。

DFS 遞迴實作 (簡潔)

/*
// Definition for a Node.
class Node {
public:
    int val;
    vector neighbors;
    Node() { val = 0; }
    Node(int _val) { val = _val; }
    Node(int _val, vector _neighbors) { val = _val; neighbors = _neighbors; }
};
*/
class Solution {
    unordered_map mp;
public:
    Node* cloneGraph(Node* node) {
        if (!node) return nullptr;
        if (mp.count(node)) return mp[node];
        Node* copy = new Node(node->val);
        mp[node] = copy;
        for (Node* nbr : node->neighbors)
            copy->neighbors.push_back(cloneGraph(nbr));
        return copy;
    }
};

BFS 迭代實作 (無遞迴棧溢位風險)

class Solution {
public:
    Node* cloneGraph(Node* node) {
        if (!node) return nullptr;
        unordered_map mp;
        queue q;
        q.push(node);
        mp[node] = new Node(node->val);
        while (!q.empty()) {
            Node* cur = q.front(); q.pop();
            for (Node* nbr : cur->neighbors) {
                if (!mp.count(nbr)) {
                    mp[nbr] = new Node(nbr->val);
                    q.push(nbr);
                }
                mp[cur]->neighbors.push_back(mp[nbr]);
            }
        }
        return mp[node];
    }
};

DFS 迭代實作 (顯式棧)

class Solution {
public:
    Node* cloneGraph(Node* node) {
        if (!node) return nullptr;
        unordered_map mp;
        stack st;
        st.push(node);
        mp[node] = new Node(node->val);
        while (!st.empty()) {
            Node* cur = st.top(); st.pop();
            for (Node* nbr : cur->neighbors) {
                if (!mp.count(nbr)) {
                    mp[nbr] = new Node(nbr->val);
                    st.push(nbr);
                }
                mp[cur]->neighbors.push_back(mp[nbr]);
            }
        }
        return mp[node];
    }
};

關鍵點總結

• 時間複雜度：O(V + E) (每節點、每邊訪問常數次)。
• 空間複雜度：O(V) (map + 容器 + 遞迴棧/隊列/棧)。
• 哈希表鍵用原節點指標，C++ unordered_map 預設支援指標雜湊。

進階：節點值不唯一時

本題保證 label (val) 唯一，若不唯一，必須用指標/記憶體位址作鍵，不可用值作鍵。