# Clone Graph

## Question

Given the head of a graph, return a deep copy (clone) of the graph. Each node in the graph contains a`label` (`int`) and a list (`List[UndirectedGraphNode]`) of its`neighbors`. There is an edge between the given node and each of the nodes in its neighbors.

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

How we serialize an undirected graph:

Nodes are labeled uniquely.

We use `#` as a separator for each node, and `,` as a separator for node label and each neighbor of the node.

As an example, consider the serialized graph `{0,1,2#1,2#2,2}.`

The graph has a total of three nodes, and therefore contains three parts as separated by #.

First node is labeled as 0. Connect node 0 to both nodes 1 and 2. Second node is labeled as 1. Connect node 1 to node 2. Third node is labeled as 2. Connect node 2 to node 2 (itself), thus forming a self-cycle.

Visually, the graph looks like the following:

``````  1
/ \
/   \
0 --- 2
/ \
\_/``````

Have you met this question in a real interview? Yes

Example return a deep copied graph.

## Analysis

Wikipedia: “In graph theory, breadth-first search (BFS) is a strategy for searching in a graph when search is limited to essentially two operations: (a) visit and inspect a node of a graph; (b) gain access to visit the nodes that neighbor the currently visited node. The BFS begins at a root node and inspects all the neighboring nodes. Then for each of those neighbor nodes in turn, it inspects their neighbor nodes which were unvisited, and so on. Compare BFS with the equivalent, but more memory-efficient Iterative deepening depth-first search and contrast with depth-first search.”

Depth-first Search

Wikipedia: “Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. One starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking.”

## Solution

### BFS - breadth first search, non-recursive

``````/**
* Definition for undirected graph.
* class UndirectedGraphNode {
*     int label;
*     ArrayList<UndirectedGraphNode> neighbors;
*     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
* };
*/
public class Solution {
/**
* @param node: A undirected graph node
* @return: A undirected graph node
*/
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if (node == null) {
return null;
}
HashMap<UndirectedGraphNode, UndirectedGraphNode> hm = new HashMap<UndirectedGraphNode, UndirectedGraphNode>();

while (!queue.isEmpty()) {
UndirectedGraphNode currentNode = queue.remove();
for (UndirectedGraphNode neighbor : currentNode.neighbors) {
if (!hm.containsKey(neighbor)) {
UndirectedGraphNode newNeighbor = new UndirectedGraphNode(neighbor.label);
hm.put(neighbor, newNeighbor);
}
}
}

}
}``````

### DFS - depth first search, non-recursive

``````/**
* Definition for undirected graph.
* class UndirectedGraphNode {
*     int label;
*     ArrayList<UndirectedGraphNode> neighbors;
*     UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); }
* };
*/
public class Solution {
/**
* @param node: A undirected graph node
* @return: A undirected graph node
*/
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if(node == null)
return null;

HashMap<UndirectedGraphNode, UndirectedGraphNode> hm = new HashMap<UndirectedGraphNode, UndirectedGraphNode>();
stack.push(node);

while(!stack.isEmpty()){
UndirectedGraphNode curnode = stack.pop();
for(UndirectedGraphNode aneighbor: curnode.neighbors){//check each neighbor
if(!hm.containsKey(aneighbor)){//if not visited,then push to stack
stack.push(aneighbor);
UndirectedGraphNode newneighbor = new UndirectedGraphNode(aneighbor.label);
hm.put(aneighbor, newneighbor);
}

}
}

}
}``````

### DFS Recursive

``````public class Solution {
public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
if (node == null) {
return null;
}
return cloneGraph(node, new HashMap<>());
}

private UndirectedGraphNode cloneGraph(UndirectedGraphNode node,
Map<UndirectedGraphNode, UndirectedGraphNode> cloneMap) {

UndirectedGraphNode clone = new UndirectedGraphNode(node.label);
cloneMap.put(node, clone);

for (UndirectedGraphNode neighbor : node.neighbors) {
UndirectedGraphNode neighborClone = cloneMap.get(neighbor);
if (neighborClone != null) {