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

# 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;
    }
};