克隆图

题目：克隆图

    给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝（克隆）。

    图中的每个节点都包含它的值 val（int） 和其邻居的列表（list[Node]）。

class Node {
    public int val;
    public List<Node> neighbors;
}

输入：[[2,4],[1,3],[2,4],[1,3]]

输出：[[2,4],[1,3],[2,4],[1,3]]

 

题解：

1. 两遍BFS

/**
     * 第一遍BFS：复制所有点
     * 第二遍BFS：复制所有邻居
     */
    class Solution {
        public Node cloneGraph(Node node) {
            if(null == node) return null;

            Map<Node, Node> map=new HashMap();
            Queue<Node> queue =new ArrayDeque<>();
            queue.add(node);

            Node temp=null;
            while (!queue.isEmpty())
            {
                temp=queue.poll();
                Node cv=new Node(temp.val);
                map.put(temp, cv);

                for(Node neighber : temp.neighbors)
                {
                    if(map.containsKey(neighber))
                        continue;
                    queue.add(neighber);
                }
            }

            queue.add(node);
            int book[]=new int[101];
            book[node.val]=1;
            Node cv=null;
            while (!queue.isEmpty())
            {
                temp=queue.poll();
                cv=map.get(temp);
                for(Node neighbor : temp.neighbors)
                {
                    cv.neighbors.add(map.get(neighbor));
                    if(book[neighbor.val]==1)
                        continue;
                    book[neighbor.val]=1;
                    queue.add(neighbor);
                }
            }
            return map.get(node);
        }
    }