[leetcode]Clone Graph

新博文地址：[leecode]Clone Graph

Clone Graph

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
             / \
             \_/

这道题刚开始都木有看懂= =//，还纳闷，参数只给了一个点node，题目怎么说复制graph呢，后来才反应过来，题中参数给的其实是一个连通分量啊。。

简单的做一下描述：复制一个有向图的连通分量

BFS和DFS应该都可以，我用的BFS，题目没啥难度，就是有一点需要注意->图中两点之间的边，可能有多条，比如#2,3,3，表示点2,到点3有两条路，更甚者#5,5,5.....在现实中的含义可能是你原地转小圈转大圈的区别吧= =//

弄懂了题意之后，对BFS做一下适当的变形，配合hashMap和set，没啥难度

代码如下：

public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {
		if(node == null || node.neighbors == null || node.neighbors.size() == 0){
			return node == null ? node : new UndirectedGraphNode(node.label);
		}
		Queue<UndirectedGraphNode> q = new ArrayDeque<UndirectedGraphNode>();
		q.offer(node);
		Map<Integer,UndirectedGraphNode> hash = new HashMap<Integer,UndirectedGraphNode>();
		Set<Integer> processed = new HashSet<Integer>();
		UndirectedGraphNode nodeClone = new UndirectedGraphNode(node.label);
		hash.put(node.label, nodeClone);
		while(!q.isEmpty()){
			UndirectedGraphNode tem = q.poll();
			processed.add(tem.label);
			UndirectedGraphNode temClone = hash.containsKey(tem.label) ? hash.get(tem.label) : new UndirectedGraphNode(tem.label);
			for(UndirectedGraphNode neighbor : tem.neighbors){
				if(!processed.contains(neighbor.label)){
					boolean exist = false;
					for(UndirectedGraphNode n : q){
						if(n.label == neighbor.label){
							exist = true;
							break;
						}
					}
					if(!exist) q.offer(neighbor);
				}
				if(!hash.containsKey(neighbor.label)){
					UndirectedGraphNode neighborClone = new UndirectedGraphNode(neighbor.label);
					temClone.neighbors.add(neighborClone);
					hash.put(neighbor.label, neighborClone);
				}else{
					temClone.neighbors.add(hash.get(neighbor.label));
				}
			}
		}
		return nodeClone;
    }