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

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

Have you met this question in a real interview? Yes

**Example**\
return a deep copied graph.

**Tags**\
Breadth First Search Facebook

## Analysis

本题是Graph相关的基础问题，图的遍历主要有两种方法：BFS，DFS，也就是广度优先搜索和深度优先搜索。

**Breadth-first Search**

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

这是一种对图的遍历方法，对于一个节点来说先把所有neighbors都检查一遍，再从\
第一个neighbor开始，循环往复。

由于BFS的这个特质，BFS可以帮助寻找最短路径。

通常BFS用queue+循环实现。

**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.”

通常来说简便的DFS写法是用递归，如果非递归的话就是栈套迭代，思想是一样的。

思路1：使用BFS，先将头节点入queue，每一次queue出列一个node，然后检查这个node的所有的neighbors，如果没visited过，就入队，并更新neighbor。

思路2：使用DFS，可以分为迭代和循环两种方式，后者需要利用stack。

## Solution

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

```java
/**
 * 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>();
        LinkedList<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>();
        UndirectedGraphNode head = new UndirectedGraphNode(node.label);
        hm.put(node, head);
        queue.add(node);

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

        return head;
    }
}
```

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

```java
/**
 * 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>();
        LinkedList<UndirectedGraphNode> stack = new LinkedList<UndirectedGraphNode>();
        UndirectedGraphNode head = new UndirectedGraphNode(node.label);
        hm.put(node, head);
        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);
                }

                hm.get(curnode).neighbors.add(hm.get(aneighbor));
            }
        }

        return head;
    }
}
```

### DFS Recursive

```java
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) {
                clone.neighbors.add(neighborClone);
            }
            else {
                clone.neighbors.add(cloneGraph(neighbor, cloneMap));
            }
        }

        return clone;
    }
}
```

## Reference

* [Clone Graph leetcode java（DFS and BFS 基础）](http://www.cnblogs.com/springfor/p/3874591.html)