Leetcode[133] Clone Graph

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

OJ’s undirected graph serialization: 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
     / \
     \_/ ###Python ####BFS ```python # Definition for a undirected graph node # class UndirectedGraphNode(object): #     def __init__(self, x): #         self.label = x #         self.neighbors = []

class Solution(object): def cloneGraph(self, node): “”” :type node: UndirectedGraphNode :rtype: UndirectedGraphNode “”” if not node: return node dict = {} queue = [] queue.append(node) newNode = UndirectedGraphNode(node.label) dict[node] = newNode while len(queue) > 0: cur = queue.pop(0) for nei in cur.neighbors: if nei not in dict: copy = UndirectedGraphNode(nei.label) dict[nei] = copy dict[cur].neighbors.append(copy) queue.append(nei) else: dict[cur].neighbors.append(dict[nei]) return dict[node]

####DFS
```python
# Definition for a undirected graph node
# class UndirectedGraphNode(object):
#     def __init__(self, x):
#         self.label = x
#         self.neighbors = []

class Solution(object):
    def cloneGraph(self, node):
        """
        :type node: UndirectedGraphNode
        :rtype: UndirectedGraphNode
        """
        if not node:
            return node
        return self.dfs(node, {})
    def dfs(self, node, dict):
        if not node:
            return None
        if node in dict:
            return dict[node]
        newNode = UndirectedGraphNode(node.label)
        dict[node] = newNode
        for nei in node.neighbors:
            newNode.neighbors.append(self.dfs(nei, dict))
        return newNode
                

###Java

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

        HashMap<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<UndirectedGraphNode, UndirectedGraphNode>();
        map.put(node, new UndirectedGraphNode(node.label));
        ArrayList<UndirectedGraphNode> temp = new ArrayList<UndirectedGraphNode>();
        temp.add(node);
        int start = 0;
        while (start < temp.size()) {
        	UndirectedGraphNode crtNode = temp.get(start++);

        	for (UndirectedGraphNode oneNode: crtNode.neighbors) {
		        if (!map.containsKey(oneNode)) {
		        	map.put(oneNode, new UndirectedGraphNode(oneNode.label));
		        	temp.add(oneNode);
		        }
        	}
        }

        for (UndirectedGraphNode crtNode: temp) {
        	UndirectedGraphNode newNode = map.get(crtNode);
        	for (UndirectedGraphNode oneNode: crtNode.neighbors) {
        		newNode.neighbors.add(map.get(oneNode));
        	}

        }

        return map.get(node);
    }
}

###Points

• BFS & DFS
• Details: The order of BFS is, create new node first then add to queue
• DFS: Return new node all the time; if already visited, return; otherwise create new node and go DFS

由于遍历一个图有两种方式：bfs和dfs。所以深拷贝一个图也可以采用这两种方法。不管使用dfs还是bfs都需要一个哈希表map来存储原图中的节点和新图中的节点的一一映射。map的作用在于替代bfs和dfs中的visit数组，一旦map中出现了映射关系，就说明已经复制完成，也就是已经访问过了。