## # 133. 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.

Approach 1: DFS.

Approach 2: BFS.

### # Code (Python)

Approach 1:

``````class Solution:
def cloneGraph(self, node: 'Node') -> 'Node':
if not node:
return None

table = {}

def explore(node):
if node in table:
return
table[node] = Node(node.val)
for neighbor in node.neighbors:
explore(neighbor)
table[node].neighbors.append(table[neighbor])

explore(node)
return table[node]
``````

Approach 2:

### # Code (C++)

Approach 1:

``````/*
// 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 {
private:
unordered_map<int,Node*> created;
public:
Node* cloneGraph(Node* node) {
if (node == NULL)
return NULL;
if (created.find(node->val) != created.end())
return created[node->val];
Node *newNode = new Node();
newNode->val = node->val;
created[newNode->val] = newNode;
for (int i = 0; i < node->neighbors.size(); ++i)
{
Node *newNeighbor = cloneGraph(node->neighbors[i]);
newNode->neighbors.push_back(newNeighbor);
}
return newNode;
}
};
``````

Approach 2:

``````// BFS
class Solution {
private:
unordered_map<int,Node*> created;
public:
Node* cloneGraph(Node* node) {
if (node == NULL)
return NULL;
queue<Node*> q;
q.push(node);
Node *newNode = new Node();
newNode->val = node->val;
created[node->val] = newNode;
while (!q.empty())
{
Node *curr = q.front();
q.pop();
Node *newCurr = created[curr->val];
for (int i = 0; i < curr->neighbors.size(); ++i)
{
Node *neighbor = curr->neighbors[i];
Node *newNeighbor = NULL;
if (created.find(neighbor->val) != created.end())
{
newNeighbor = created[neighbor->val];
}
else
{
newNeighbor = new Node();
newNeighbor->val = neighbor->val;
created[newNeighbor->val] = newNeighbor;
q.push(neighbor);
}
newCurr->neighbors.push_back(newNeighbor);
}
}
return newNode;
}
};
``````