Clone Graph

LintCode LeetCode

这道题让克隆一个无向图，题目里关于如何序列化一个无向图的介绍对解题没有什么帮助。这道题仍然用BFS来解决，这个视频帮到我很多。

Clone Graph

基本思路是，1、先克隆所有的点；2、再克隆所有的联结关系。
用一个HashMap来形成原图和克隆图的mapping,同时可以用来保存已经被visited的节点。HashMap的key是original node, value 是clone node. 同时，每逢bfs几乎必用的Queue用来辅助遍历。注意，每次要将某些节点offer进queue等待下一步遍历的时候，也要将这些节点加入到HashMap里表示已经visited.但是，注意一开始加入到HashMap里的时候，value先设为null,直到poll这个节点出来遍历该点的时候，再将mapping更新为key = original node; value = clone node. (为什么先设为null呢？）

当所有的点都被克隆完后，还需要克隆初原来图中的连结关系。我们需要遍历出original graph的每个点的每个neighbor, 然后在clone graph里边先get到对应的点，再在这个点的neighbors里边add所有的neighbor.

    public class Solution {
    /**
     * @param node: A undirected graph node
     * @return: A undirected graph node
     */
        public UndirectedGraphNode cloneGraph(UndirectedGraphNode node){
            if (node == null) {
                return null;
            }
            Queue<UndirectedGraphNode> queue = new LinkedList<UndirectedGraphNode>();
            HashMap<UndirectedGraphNode,UndirectedGraphNode> visited = new HashMap<UndirectedGraphNode,UndirectedGraphNode>();
            queue.offer(node);
            visited.add(node, null);
            while (!queue.isEmpty()){
                UndirectedGraphNode temp = queue.poll();
                UndirectedGraphNode copy = new UndirectedGraphNode(temp.label);
                visited.put(temp, copy);
                for (UndirectedGraphNode neighbor : temp.neighbors){
                    if (!visited.containsKey(neighbor)){
                        queue.offer(neighbor);
                        visited.put(neighbor, null);
                    }
                }
            }
            for (UndirectedGraphNode original : visited.keySet()){
                UndirectedGraphNode cpy = visited.get(original);
                for (UndirectedGraphNode neighbor: original.neighbors){
                    cpy.neighbors.add(visited.get(neighbor));
                }
            }
            return visited.get(node);
            }
    }