克隆图

来源Leetcode第133题克隆图

给定无向连通图中一个节点的引用，返回该图的深拷贝（克隆）。图中的每个节点都包含它的值 val（Int） 和其邻居的列表（list[Node]）。

图的定义

class Node {
public int val;
public List neighbors;

public Node() {}

public Node(int _val,List<Node> _neighbors) {
    val = _val;
    neighbors = _neighbors;
}

};

广度优先搜索

这题的本质就是对图的遍历，在遍历时怎么把图的邻居添加进去。

首先对图进行一个 BFS，把所有节点 new 出来，不处理 neighbors，并且把所有的节点存到 map 中。
然后再对图做一个 BFS，因为此时所有的节点已经创建了，只需要更新所有节点的 neighbors。

public Node cloneGraph(Node node) {
    if (node == null)
        return null;
    Queue<Node> queue = new LinkedList<>();
    //队列用来判断是否遍历完所有结点
    Map<Node, Node> map = new HashMap<>();
    //map key值为原结点，val值为克隆结点
    Node new_node = new Node(node.val, new LinkedList<>());
    queue.offer(node);
    //头结点入队
    map.put(node, new_node);
    while (!queue.isEmpty()) {
        Node cur = queue.poll();
        for (Node n : cur.neighbors) {
            if (!map.containsKey(n)) {
                //不包含的结点加入到map里
                queue.offer(n);
                //同把该结点入队
                Node tmp = new Node(n.val, new LinkedList<>());
                map.put(n, tmp);
            }
            map.get(cur).neighbors.add(map.get(n));
        }
    }
    return map.get(node);
}

深度优先搜索

同样利用一个map来存储原结点和克隆结点，接着对第一个结点进行深度优先搜索，出口为当所有结点都在map时。

public Node cloneGraph(Node node) {
    if (node == null)
        return null;
    HashMap<Node,Node> map = new HashMap<Node,Node>();
    node = dfs(node,map);
    return node;
}

public Node dfs(Node node,HashMap<Node,Node> map){
   //当所有结点都在map里时退出递归
    Node aNode = new Node(node.val,new ArrayList<>());
    map.put(node,aNode);
    for(Node neighbours : node.neighbors){
        if(!map.containsKey(neighbours))
            //如果没有包含此结点，从此结点一直往下遍历
            neighbours = dfs(neighbours,map);
        else
            //如果包含了此结点，返回其克隆结点
            neighbours = map.get(neighbours);
        aNode.neighbors.add(neighbours);
    }
    return aNode;
}