题目描述

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:

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

算法1

(bfs)

C++ 代码

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

    Node() {}

    Node(int _val, vector<Node*> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};
*/
class Solution {
public:
    //bfs
    Node* cloneGraph(Node* node) {
        //旧节点和新节点的映射
        unordered_map<Node*,Node*> map;
        queue<Node*> q;
        //注意克隆时不管是节点还是邻居，都得新建，新加入邻居，不能用原来的直接复制，否则就不是新的节点、邻居了
        Node* clone=new Node(node->val,vector<Node*>());
        map[node]=clone;
        q.push(node);

        while(!q.empty()){
            Node *cur=q.front();
            q.pop();
            for(auto n:cur->neighbors){
                //如果当前邻居没有出现过，那么clone图里面应新建一个节点,并以他可以作为下一次的bfs
                if(map.find(n)==map.end()){
                    map[n]=new Node(n->val,vector<Node*>());
                    q.push(n);
                }
                //clone图表中也得把邻居加入neighbors
                map[cur]->neighbors.push_back(map[n]);
            }
        }
        return clone;
    }
};

算法2

(dfs)

C++ 代码

class Solution {
public:
    //旧节点到新节点的映射
    unordered_map<Node*,Node*> map;
    Node* cloneGraph(Node* node) {
        if(node==nullptr)
            return nullptr;
        Node *clone=new Node(node->val,vector<Node*>());
        map[node]=clone;
        dfs(node);
        return clone;
    }
    void dfs(Node* node){
        for(auto &n:node->neighbors){
            if(map.find(n)==map.end()){
                map[n]=new Node(n->val,vector<Node*>());
                dfs(n);
            }
            map[node]->neighbors.push_back(map[n]);
        }
    }
};