# 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:
- 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.
# Solution
Approach 1: DFS. Use a map/dictionary to store mappings from original node to cloned.
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;
}
};