133. Clone Graph

題目網址：https://leetcode.cn/problems/clone-graph/

題意：給一無向連通圖的 node, 請返回該圖的 copy。

圖中每個 node 都包含它的 val (int) 和其 neighbors (list[node])

Solution 1：

想法：利用 DFS

class Solution {
public:
    Node* cloneGraph(Node* node) {
        if (!node) {
            return node;
        }
        return dfs(node);
    }

private:
    unordered_map<Node*, Node*> visited; // {old : new}, 用來記錄已生成的 node

    Node* dfs(Node* node){
        // 若 node 已經生成過, 則返回其 copy
        if (visited.find(node) != visited.end()) {
            return visited[node];
        }

        // 生成當前 node
        Node* copy = new Node(node->val);
        visited[node] = copy;

        // 添加當前 node 的 neighbors
        for (const auto& neighbor : node->neighbors) {
            copy->neighbors.emplace_back(dfs(neighbor));
        }
        return copy;
    }
};

• time：$O(V+E)$ ➔ 必須拜訪所有 node, 和其延伸出去的所有 edge
  • V 是 node 數, E 是 edge 數
• space：$O(V)$ ➔ oldToNew

Solution 2：

想法：利用 BFS

class Solution {
public:
    Node* cloneGraph(Node* node) {
        if (!node) {
            return node;
        }

        unordered_map<Node*, Node*> visited; // {old : new}, 用來記錄已生成的 node
        queue<Node*> q;
        q.push(node);
        visited[node] = new Node(node->val);

        while (!q.empty()) {
            Node* n = q.front();
            q.pop();

            for (const auto& neighbor : n->neighbors) {
                // 如果 neighbor 還沒被拜訪過
                if (visited.find(neighbor) == visited.end()) {
                    visited[neighbor] = new Node(neighbor->val); // 生成該 node
                    q.push(neighbor); // 加到 queue 中
                }
                
                // 更新當前 node 的 neighbors
                visited[n]->neighbors.emplace_back(visited[neighbor]);
            }
        }
        return visited[node];
    }
};

• time：$O(V+E)$ ➔ 必須拜訪所有 node, 和其延伸出去的所有 edge
  • V 是 node 數, E 是 edge 數
• space：$O(V)$ ➔ visited