LeetCode – Clone Graph

题目：

Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node in the graph contains a val (int) and a list (List[Node]) of its neighbors.

Example:

Input:

{"$id":"1","neighbors":[{"$id":"2","neighbors":[{"$ref":"1"},{"$id":"3","neighbors":[{"$ref":"2"},{"$id":"4","neighbors":[{"$ref":"3"},{"$ref":"1"}],"val":4}],"val":3}],"val":2},{"$ref":"4"}],"val":1}

Explanation:

Node 1's value is 1, and it has two neighbors: Node 2 and 4.
Node 2's value is 2, and it has two neighbors: Node 1 and 3.
Node 3's value is 3, and it has two neighbors: Node 2 and 4.
Node 4's value is 4, and it has two neighbors: Node 1 and 3.

Note:

1. The number of nodes will be between 1 and 100.
2. The undirected graph is a simple graph, which means no repeated edges and no self-loops in the graph.
3. Since the graph is undirected, if node p has node q as neighbor, then node q must have node p as neighbor too.
4. You must return the copy of the given node as a reference to the cloned graph.

解题：

• 深度优先DFS：

       使用递归方式，利用hashmap建立原节点和克隆节点的对应关系， 判断是否已经进行克隆， 处理过程：

1. 先判断结束条件： 当前节点是否为空；
2. 判断为非空节点后， 通过hashmap判断是否克隆过， 发现已经克隆过，直接反馈其克隆节点；
3. 对于未进行克隆的节点，对当前节点进行克隆， 并且在hashmap中建立映射关系；
4. 遍历当前节点所有neighbors 中的节点，再次调用cloneGraph函数，将他们克隆到当前节点克隆节点的neighbors数组中。
5. 返回克隆节点；

实现：

// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> neighbors;

    Node() {}

    Node(int _val, vector<Node*> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};
*/
/* DFS */
class Solution {
public:
    Node* cloneGraph(Node* node) {
        if(!node){
            return NULL;
        }
        if (copies.find(node) == copies.end()){
            copies[node] = new Node(node->val, {});
            for (Node* neighbor : node->neighbors){
                copies[node]->neighbors.push_back(cloneGraph(neighbor));
            }
        }
        return copies[node];
    }
private:
    unordered_map<Node*, Node*> copies;
};

• 广度优先BFS：

       增加队列queue进行辅助，利用hashmap建立原节点和克隆节点的对应关系，判断是否已经进行克隆，处理过程：

1. 先判断结束条件： 当前节点是否为空；
2. 判断为非空节点后，对当前节点进行克隆， 并且在hashmap中建立映射关系，并将其放入队列queue；
3.  对队列进行处理，取出队列的元素。
4.  遍历其所有的neighbors数组的节点neighbor， 如果不在hashmap中，克隆一个新的neighbor节点，并在hashmap中建立映射关系， 将其放入队列，并将其克隆到当前节点克隆节点的neighbors数组中
5. 重复3，4处理，直到队列为空退出。
6. 返回克隆节点；

// Definition for a Node.
class Node {
public:
    int val;
    vector<Node*> neighbors;

    Node() {}

    Node(int _val, vector<Node*> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};
//BFS
class Solution {
public:
    Node* cloneGraph(Node* node) {
        if(!node){
            return NULL;
        }
        Node *copy = new Node(node->val, {});
        copies[node] = copy;
        queue<Node*> q;
        q.push(node);
        while (!q.empty()){
            Node* cur = q.front();
            q.pop();
            for (Node* neighbor : cur->neighbors){
                 if (copies.find(neighbor) == copies.end()){
                     copies[neighbor] = new Node(neighbor->val, {});
                     q.push(neighbor);
                 }
                 copies[cur]->neighbors.push_back(copies[neighbor]);
            }
        }
       
        return copies[node];
    }
private:
    unordered_map<Node*, Node*> copies;
};