给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝（克隆）。

图中的每个节点都包含它的值 val（int） 和其邻居的列表（list[Node]）。

class Node {
public:
    int val;
    vector<Node*> neighbors;
    Node() {
        val = 0;
        neighbors = vector<Node*>();
    }
    Node(int _val) {
        val = _val;
        neighbors = vector<Node*>();
    }
    Node(int _val, vector<Node*> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
};

				

					
				
				

					
				
				

					
				
				

					
				
			

图在测试用例中使用邻接列表表示。

邻接列表 是用于表示有限图的无序列表的集合。每个列表都描述了图中节点的邻居集。

给定节点将始终是图中的第一个节点（值为 1）。你必须将 给定节点的拷贝 作为对克隆图的引用返回。

示例 1：
 
输入：adjList = [[2,4],[1,3],[2,4],[1,3]]
输出：[[2,4],[1,3],[2,4],[1,3]]
解释：
图中有 4 个节点。
节点 1 的值是 1，它有两个邻居：节点 2 和 4 。
节点 2 的值是 2，它有两个邻居：节点 1 和 3 。
节点 3 的值是 3，它有两个邻居：节点 2 和 4 。
节点 4 的值是 4，它有两个邻居：节点 1 和 3 。
示例 2：
 
输入：adjList = [[]]
输出：[[]]
解释：输入包含一个空列表。该图仅仅只有一个值为 1 的节点，它没有任何邻居。
示例 3：
 
输入：adjList = []
输出：[]
解释：这个图是空的，它不含任何节点。
示例 4：
 
输入：adjList = [[2],[1]]
输出：[[2],[1]]

				

					
				
				

					
				
				

					
				
				

					
				
			

提示：

• 节点数不超过 100 。
• 每个节点值 Node.val 都是唯一的，1 <= Node.val <= 100。
• 无向图是一个简单图，这意味着图中没有重复的边，也没有自环。
• 由于图是无向的，如果节点 p 是节点 q 的邻居，那么节点 q 也必须是节点 p 的邻居。
• 图是连通图，你可以从给定节点访问到所有节点。

思路：
题目的意思是：根据给出的无向连通图的一个节点，构造一个新的无向连通图，并返回该节点。

深度遍历：从给出的节点开始遍历
 复制该节点
 复制该节点的邻居节点
  如果邻居节点已存在，直接加入；
  如果没有，把邻居节点做为当前节点开始遍历
 遍历完当前节点就返回上一层节点继续遍历未遍历完的邻居节点

//实现一
Node* createNode(Node* node, unordered_map<int, Node*> &created) {
    Node* res = new Node(node->val);
    created.insert({node->val, res});
 
    vector<Node*> &neighbors = node->neighbors;
    for (int i = 0; i < neighbors.size(); ++i) {
        if (created.count(neighbors[i]->val)) {
            res->neighbors.push_back(created[neighbors[i]->val]);
        } else {
            res->neighbors.push_back(createNode(neighbors[i], created));
        }
    }
    return res;
}
 
Node* cloneGraph(Node* node) {
    if (!node)
        return node;
    unordered_map<int, Node*> created;
    return createNode(node, created);
}
 
//实现二
class Solution {
public:
    unordered_map<Node*, Node*> created;
    Node* cloneGraph(Node* node) {
        if (node == nullptr) {
            return node;
        }
 
        if (created.count(node)) {
            return created[node];
        }
 
        Node* cloneNode = new Node(node->val);
 
        created[node] = cloneNode;
        for (auto& neighbor: node->neighbors) {
            cloneNode->neighbors.emplace_back(cloneGraph(neighbor));
        }
        return cloneNode;
    }
};

				

					
				
				

					
				
				

					
				
				

					
				
			

广度优先遍历：遍历每个节点时，先遍历完当前节点的所有的邻居节点，再对邻居节点进行遍历。

Node* cloneGraph(Node* node) {
    if (!node)
        return node;
 
    unordered_unordered_map<Node*, Node*> created;
    queue<Node*>que;
    que.push(node);
    Node* res = new Node(node->val);
    created[node] = res;
 
    while (!que.empty()) {
        node = que.front();
        que.pop();
        for (auto neighbor : node->neighbors) {
            if (created.count(neighbor) == 0) {
                Node* tmp = new Node(neighbor->val);
                que.push(neighbor);
                created[neighbor] = tmp;
            }
            created[node]->neighbors.push_back(created[neighbor]);
        }
    }
 
    return res;
}