题目描述

给定无向连通图中一个节点的引用,返回该图的深拷贝(克隆)。图中的每个节点都包含它的值 valInt) 和其邻居的列表(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);
    }
}
pwrliang Algorithms, BFS, DFS, Graph , ,

Leave a Reply

Your email address will not be published. Required fields are marked *