[LeetCode]Clone Graph

类似Copy List With Random Pointer的问题，难点在于遍历图比遍历List更加复杂，基本思路还是一样的，
维护一个map，每一个原来的node对应新的node，第一个遍历的时候创建拷贝节点，之后在根据已有的map来build neighbors的list。 这里遍历图的时候我们采用BFS，注意BFS每次check邻接节点的时候要看是不是访问过并且加入visited set，而不是在queue中remove节点的时候加入visited set，第二种方法会导致queue中有重复的节点。值得注意的是。BFS中queue上的节点都是没有访问过的，且是没有重复的。要对节点做什么操作的话，在enqueue和dequeue的时候都可以，但是check访问过和更新visited set一定要在enqueue的时候。
代码如下：

	/**
	* 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>();
	LinkedList<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>();
	queue.add(node);
	map.put(node, new UndirectedGraphNode(node.label));
	while (!queue.isEmpty()) {
	UndirectedGraphNode curr = queue.removeFirst();
	for (int i = 0; i < curr.neighbors.size(); i++) {
	if (!map.containsKey(curr.neighbors.get(i))) {
	queue.add(curr.neighbors.get(i));
	map.put(curr.neighbors.get(i), new UndirectedGraphNode(curr.neighbors.get(i).label));
	}
	}
	}
	HashSet<UndirectedGraphNode> visited = new HashSet<UndirectedGraphNode>();
	queue.add(node);
	visited.add(node);
	while (!queue.isEmpty()) {
	UndirectedGraphNode curr = queue.removeFirst();
	UndirectedGraphNode copy = map.get(curr);
	for (int i = 0; i < curr.neighbors.size(); i++) {
	copy.neighbors.add(map.get(curr.neighbors.get(i)));
	if (!visited.contains(curr.neighbors.get(i))) {
	queue.add(curr.neighbors.get(i));
	visited.add(curr.neighbors.get(i));
	}
	}
	}
	return map.get(node);
	}
	}

view raw clone graph.java hosted with ❤ by GitHub