题目描述

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

示例：

输入：
 {"$id":"1","neighbors":[{"$id":"2","neighbors":[{"$ref":"1"},{"$id":"3","neighbors":[{"$ref":"2"},{"$id":"4","neighbors":[{"$ref":"3"},{"$ref":"1"}],"val":4}],"val":3}],"val":2},{"$ref":"4"}],"val":1}
解释：
 节点 1 的值是 1，它有两个邻居：节点 2 和 4 。
 节点 2 的值是 2，它有两个邻居：节点 1 和 3 。
 节点 3 的值是 3，它有两个邻居：节点 2 和 4 。
 节点 4 的值是 4，它有两个邻居：节点 1 和 3 。

提示：

1. 节点数介于 1 到 100 之间。
2. 无向图是一个简单图，这意味着图中没有重复的边，也没有自环。
3. 由于图是无向的，如果节点 p 是节点 q 的邻居，那么节点 q 也必须是节点p 的邻居。
4. 必须将给定节点的拷贝作为对克隆图的引用返回。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/clone-graph
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法1 – DFS

递归的克隆图的节点是一种很自然的想法。为了避免节点重复复制，我们使用Map<Integer, Node> idNewNode来存放节点编号与新节点的对应关系。我们声明辅助函数“private Node cloneNode(Node node, Map idNewNode)”，它实现来根据输入的原始顶点node，返回克隆后的node。

我们使用DFS遍历图，首先将node克隆得到newNode，然后用idNewNode记录我们node节点编号与新节点newNode。然后从node访问到它的临接点nbr，先根据idNewNode来判断nbr是否访问过。如果没访问过，就递归的调用辅助函数cloneNode(nbr, idNewNode)来克隆临接点得到newNbr。然后我们需要向newNode的neighbors中添加newNbr，来添加一条从newNode到newNbr到边。

时间复杂度O(|V|+E|)，空间复杂度O(|V|)。全部代码如下：

class Solution {
    public Node cloneGraph(Node node) {
        if (node == null)
            return node;
        return cloneNode(node, new HashMap<>());
    }

    private Node cloneNode(Node node, Map<Integer, Node> idNewNode) {
        List<Node> nbrList = new ArrayList<>();
        Node newNode = new Node(node.val, nbrList);

        idNewNode.put(newNode.val, newNode);

        if (node.neighbors == null || node.neighbors.size() == 0)
            return newNode;

        for (Node nbr : node.neighbors) {
            Node newNbr = idNewNode.get(nbr.val);
            if (newNbr == null) {
                newNbr = cloneNode(nbr, idNewNode);
            }
            newNode.neighbors.add(newNbr);
        }

        return newNode;
    }
}

解法2 – BFS

当然，我们也可以使用BFS来克隆图。我们创建Map<Integer, Node> idNewNode用来记录节点编号与克隆后得到的新节点，创建Queue<Node> queue来实现BFS。

首先将node加入到queue，然后不断地从queue出队节点node，克隆node得到newNode，将(node.val, newNode)记录到idNewNode。然后访问node的临接点nbr，克隆nbr得到newNbr，再记录newNode到newNbr存在的边，如果nbr没访问过则入队……

时间复杂度O(|V|+|E|)，空间复杂度O(|V|)。全部代码如下：

class Solution {
    public Node cloneGraph(Node node) {
        if (node == null) return null;

        Map<Integer, Node> idNewNode = new HashMap<>();
        Queue<Node> queue = new LinkedList<>();

        queue.offer(node);
        Node current;

        while (!queue.isEmpty()) {
            current = queue.poll();
            Node newNode = idNewNode.get(current.val);

            if (newNode == null) {
                newNode = new Node(current.val, new ArrayList<>());
                idNewNode.put(current.val, newNode);
            }

            for (Node neighbor : current.neighbors) {
                Node newNbr = idNewNode.get(neighbor.val);

                if (newNbr == null) {
                    newNbr = new Node(neighbor.val, new ArrayList<>());
                    idNewNode.put(neighbor.val, newNbr);
                    queue.offer(neighbor);
                }

                newNode.neighbors.add(newNbr);
            }

        }

        return idNewNode.get(node.val);
    }
}