> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/search/level-order-traversal/clone-graph.md).

# Clone Graph

<https://leetcode.com/problems/clone-graph/description/>

> Clone an undirected graph. Each node in the graph contains a `labe`and a list of its `neighbors`.

## Thoughts

BFS动态找出所有点，新老结点建立起映射，并对每个点把它的所有边也插进去。当遇到map中不存在的原图节点, 则创建新图对应节点放入map中。

## Code

```
/*
 * @lc app=leetcode id=133 lang=cpp
 *
 * [133] Clone Graph
 */
/*
// 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:
    Node* cloneGraph(Node* node) {
        unordered_map<Node*, Node*> m;
        queue<Node*> q;
        m[node] = new Node(node->val);
        q.push(node);
        while (!q.empty()) {
            const auto cur = q.front();
            q.pop();
            for (const auto nei : cur->neighbors) {
                if (!m.count(nei)) {
                    m[nei] = new Node(nei->val);
                    q.push(nei);
                }
                (m[cur]->neighbors).push_back(m[nei]);
            }
        }
        return m[node];
    }
};


```