# Clone Graph
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/clone-graph)
Canonical: https://scaleengineer.com/dsa/problems/clone-graph
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Hash Table, Graph
**Companies:** [Docusign](https://scaleengineer.com/companies/docusign), [Google](https://scaleengineer.com/companies/google), [Nutanix](https://scaleengineer.com/companies/nutanix), [TikTok](https://scaleengineer.com/companies/tiktok), [Uber](https://scaleengineer.com/companies/uber), [Wix](https://scaleengineer.com/companies/wix), [Yahoo](https://scaleengineer.com/companies/yahoo), [Flexport](https://scaleengineer.com/companies/flexport), [Grammarly](https://scaleengineer.com/companies/grammarly), [Pocket Gems](https://scaleengineer.com/companies/pocket-gems), [ThousandEyes](https://scaleengineer.com/companies/thousandeyes)
---
## Problem
Given a reference of a node in a **[connected](https://en.wikipedia.org/wiki/Connectivity%5F%28graph%5Ftheory%29#Connected%5Fgraph)** undirected graph.

Return a [**deep copy**](https://en.wikipedia.org/wiki/Object%5Fcopying#Deep%5Fcopy) (clone) of the graph.

Each node in the graph contains a value (`int`) and a list (`List[Node]`) of its neighbors.

class Node {
    public int val;
    public List<Node> neighbors;
}

**Test case format:**

For simplicity, each node's value is the same as the node's index (1-indexed). For example, the first node with `val == 1`, the second node with `val == 2`, and so on. The graph is represented in the test case using an adjacency list.

**An adjacency list** is a collection of unordered **lists** used to represent a finite graph. Each list describes the set of neighbors of a node in the graph.

The given node will always be the first node with `val = 1`. You must return the **copy of the given node** as a reference to the cloned graph.

**Example 1:**

![](https://assets.glich.co/dsa/clone-graph/image0.png) 

**Input:** adjList = [[2,4],[1,3],[2,4],[1,3]]
**Output:** [[2,4],[1,3],[2,4],[1,3]]
**Explanation:** There are 4 nodes in the graph.
1st node (val = 1)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
2nd node (val = 2)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).
3rd node (val = 3)'s neighbors are 2nd node (val = 2) and 4th node (val = 4).
4th node (val = 4)'s neighbors are 1st node (val = 1) and 3rd node (val = 3).

**Example 2:**

![](https://assets.glich.co/dsa/clone-graph/image1.png) 

**Input:** adjList = [[]]
**Output:** [[]]
**Explanation:** Note that the input contains one empty list. The graph consists of only one node with val = 1 and it does not have any neighbors.

**Example 3:**

**Input:** adjList = []
**Output:** []
**Explanation:** This an empty graph, it does not have any nodes.

**Constraints:**

* The number of nodes in the graph is in the range `[0, 100]`.
* `1 <= Node.val <= 100`
* `Node.val` is unique for each node.
* There are no repeated edges and no self-loops in the graph.
* The Graph is connected and all nodes can be visited starting from the given node.

# Approaches
## Depth-First Search (DFS)
This approach uses a recursive Depth-First Search (DFS) traversal to clone the graph. A hash map is used to store the mapping between original nodes and their newly created clones. This map is crucial to handle cycles and prevent re-cloning the same node multiple times.
**Time:** O(N + E), where N is the number of nodes and E is the number of edges. Each node is visited once, and we iterate through all its edges. · **Space:** O(N), for the hash map which stores all N nodes, and for the recursion stack which can go up to N deep in the worst case (for a skewed graph).
**Pros:** Conceptually simple and often leads to more concise code.; Efficient, as it visits each node and edge only once.
**Cons:** For very deep graphs, the recursion could lead to a stack overflow error. (Though not an issue with the given constraints).
### Explanation
We start traversing the graph from the given node. We use a hash map, say `visited`, to keep track of nodes that have already been cloned. The map stores the original node as the key and its clone as the value. The core of the approach is a recursive function.

In the recursive function, for a given `node`:
1. If the `node` is already in our `visited` map, it means we have already created a copy for it. We simply return the copy from the map.
2. If the `node` is not in the map, we create a new `Node` with the same value.
3. We immediately put this new node into the `visited` map, with the original `node` as the key. This is important to do *before* traversing its neighbors to handle cycles correctly.
4. Then, we iterate through each `neighbor` of the original `node`.
5. For each `neighbor`, we make a recursive call. This call will return the cloned neighbor node (either by creating it or fetching it from the map).
6. We add this returned cloned neighbor to the neighbors list of our newly created node.
7. Finally, we return the new node.

The initial call to `cloneGraph` will just call this recursive helper function starting with the given node.

```java
/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> neighbors;
    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}
*/

class Solution {
    private HashMap<Node, Node> visited = new HashMap<>();

    public Node cloneGraph(Node node) {
        if (node == null) {
            return node;
        }

        // If the node was already visited, return the clone from the map.
        if (visited.containsKey(node)) {
            return visited.get(node);
        }

        // Create a new node with the same value as the old node.
        Node cloneNode = new Node(node.val, new ArrayList<>());
        // Add the new node to the visited map.
        // This must be done before visiting the neighbors to prevent infinite loops.
        visited.put(node, cloneNode);

        // Iterate through the neighbors of the original node and recursively clone them.
        for (Node neighbor : node.neighbors) {
            cloneNode.neighbors.add(cloneGraph(neighbor));
        }
        return cloneNode;
    }
}
```
### Algorithm
- 1. Create a hash map `visited` to store the mapping from original nodes to their clones.
- 2. Define a recursive function `clone(node)`:
-    a. If `node` is null, return null.
-    b. If `visited` contains `node`, return `visited.get(node)`.
-    c. Create a new node `cloneNode` with `node.val`.
-    d. Add the mapping `(node, cloneNode)` to `visited`.
-    e. For each `neighbor` in `node.neighbors`:
-       i. Add the result of `clone(neighbor)` to `cloneNode.neighbors`.
-    f. Return `cloneNode`.
- 3. The main function `cloneGraph` simply calls `clone(node)`.

## Breadth-First Search (BFS)
This approach uses an iterative Breadth-First Search (BFS) traversal. It uses a queue to manage the nodes to visit and a hash map to store the mapping from original nodes to their clones, just like the DFS approach. This avoids recursion and the potential for stack overflow.
**Time:** O(N + E), where N is the number of nodes and E is the number of edges. Each node is enqueued and dequeued once, and we iterate through all its edges. · **Space:** O(N), for the hash map and the queue. The queue can hold up to O(W) nodes where W is the maximum width of the graph, which can be O(N) in the worst case.
**Pros:** Iterative approach avoids recursion, preventing potential stack overflow errors on very large or deep graphs.; Efficient, as it visits each node and edge only once.
**Cons:** The code can be slightly more verbose than the recursive DFS version.
### Explanation
The core idea is to create a copy of a node, then add its neighbors to a queue to be processed later. We use a hash map to ensure we don't create duplicate clones for the same node.

The algorithm proceeds as follows:
1. Handle the edge case where the input `node` is null.
2. Create a queue and add the starting `node` to it.
3. Create a hash map `visited` to store `original_node -> cloned_node` mappings.
4. Create the clone for the starting `node` and put it in the `visited` map.
5. While the queue is not empty:
    a. Dequeue a node, let's call it `originalNode`.
    b. Iterate through all `neighbor`s of `originalNode`.
    c. For each `neighbor`:
        i. If the `neighbor` is not in the `visited` map, it means we haven't seen it before. So, we create a clone for it, add it to the `visited` map, and enqueue the original `neighbor` for later processing.
    d. After checking all neighbors, we connect the cloned `originalNode` to its cloned neighbors. We retrieve the clone of `originalNode` from the map and add the clones of its neighbors (also retrieved from the map) to its neighbor list.

```java
/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> neighbors;
    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}
*/

class Solution {
    public Node cloneGraph(Node node) {
        if (node == null) {
            return null;
        }

        HashMap<Node, Node> visited = new HashMap<>();
        Queue<Node> queue = new LinkedList<>();

        // Clone the root node and add it to the queue and visited map.
        visited.put(node, new Node(node.val, new ArrayList<>()));
        queue.add(node);

        // Start BFS traversal
        while (!queue.isEmpty()) {
            // Get the original node from the front of the queue.
            Node originalNode = queue.poll();

            // Iterate through the neighbors of the original node.
            for (Node neighbor : originalNode.neighbors) {
                // If the neighbor hasn't been cloned yet.
                if (!visited.containsKey(neighbor)) {
                    // Clone it and add to the map.
                    visited.put(neighbor, new Node(neighbor.val, new ArrayList<>()));
                    // Add the original neighbor to the queue for processing.
                    queue.add(neighbor);
                }
                // Add the cloned neighbor to the neighbors list of the cloned current node.
                visited.get(originalNode).neighbors.add(visited.get(neighbor));
            }
        }

        return visited.get(node);
    }
}
```
### Algorithm
- 1. If the input `node` is null, return null.
- 2. Create a `Queue` for BFS and add the starting `node`.
- 3. Create a `HashMap<Node, Node>` called `visited` to map original nodes to their clones.
- 4. Create the clone for the starting `node`, and put the mapping in `visited`.
- 5. While the `queue` is not empty:
-    a. Dequeue a node, `originalNode`.
-    b. For each `neighbor` of `originalNode`:
-       i. If `neighbor` is not in `visited`:
-          - Create a clone for `neighbor` and add it to `visited`.
-          - Enqueue the `neighbor`.
-       ii. Add the cloned neighbor (`visited.get(neighbor)`) to the neighbor list of the cloned `originalNode` (`visited.get(originalNode).neighbors`).
- 6. Return the clone of the starting `node` from the `visited` map.

# Solutions
### JavaScript

```javascript
/** * // Definition for a _Node. * function _Node(val, neighbors) { * this.val = val === undefined ? 0 : val; * this.neighbors = neighbors === undefined ? [] : neighbors; * }; */ /** * @param {_Node} node * @return {_Node} */ var cloneGraph =
  function (node) {
    const g = new Map();
    const dfs = (node) => {
      if (!node) {
        return null;
      }
      if (g.has(node)) {
        return g.get(node);
      }
      const cloned = new _Node(node.val);
      g.set(node, cloned);
      for (const nxt of node.neighbors) {
        cloned.neighbors.push(dfs(nxt));
      }
      return cloned;
    };
    return dfs(node);
  };

```

### CSharp

```csharp
using System.Collections.Generic ; public class Solution { public Node CloneGraph ( Node node ) { if ( node == null ) return null ; var dict = new Dictionary < int , Node >(); var queue = new Queue < Node >(); queue . Enqueue ( CloneVal ( node )); dict . Add ( node . val , queue . Peek ()); while ( queue . Count > 0 ) { var current = queue . Dequeue (); var newNeighbors = new List < Node >( current . neighbors . Count ); foreach ( var oldNeighbor in current . neighbors ) { Node newNeighbor ; if (! dict . TryGetValue ( oldNeighbor . val , out newNeighbor )) { newNeighbor = CloneVal ( oldNeighbor ); queue . Enqueue ( newNeighbor ); dict . Add ( newNeighbor . val , newNeighbor ); } newNeighbors . Add ( newNeighbor ); } current . neighbors = newNeighbors ; } return dict [ node . val ]; } private Node CloneVal ( Node node ) { return new Node ( node . val , new List < Node >( node . neighbors )); } }
```

### Java

```java
/* // Definition for a Node. class Node { public int val; public List<Node> neighbors; public Node() { val = 0; neighbors = new ArrayList<Node>(); } public Node(int _val) { val = _val; neighbors = new ArrayList<Node>(); } public Node(int _val, ArrayList<Node> _neighbors) { val = _val; neighbors = _neighbors; } } */ class Solution { private Map < Node , Node > visited = new HashMap <>(); public Node cloneGraph ( Node node ) { if ( node == null ) { return null ; } if ( visited . containsKey ( node )) { return visited . get ( node ); } Node clone = new Node ( node . val ); visited . put ( node , clone ); for ( Node e : node . neighbors ) { clone . neighbors . add ( cloneGraph ( e )); } return clone ; } }
```

### Python

```python
""" # Definition for a Node. class Node: def __init__(self, val = 0, neighbors = None): self.val = val self.neighbors = neighbors if neighbors is not None else [] """ class Solution : def cloneGraph ( self , node : 'Node' ) -> 'Node' : visited = defaultdict () def clone ( node ): if node is None : return None if node in visited : return visited [ node ] c = Node ( node . val ) visited [ node ] = c for e in node . neighbors : c . neighbors . append ( clone ( e )) return c return clone ( node )
```

### CPP

```cpp
/* // Definition for a 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; } }; */ class Solution { public: unordered_map < Node * , Node *> visited ; Node * cloneGraph ( Node * node ) { if ( ! node ) return nullptr ; if ( visited . count ( node )) return visited [ node ]; Node * clone = new Node ( node -> val ); visited [ node ] = clone ; for ( auto & e : node -> neighbors ) clone -> neighbors . push_back ( cloneGraph ( e )); return clone ; } };
```