基本操作

克隆图

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

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

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

示例1:

输入：adjList = [[2,4],[1,3],[2,4],[1,3]]
输出：[[2,4],[1,3],[2,4],[1,3]]
解释：
图中有 4 个节点。
节点 1 的值是 1，它有两个邻居：节点 2 和 4 。
节点 2 的值是 2，它有两个邻居：节点 1 和 3 。
节点 3 的值是 3，它有两个邻居：节点 2 和 4 。
节点 4 的值是 4，它有两个邻居：节点 1 和 3 。

方案A 深度优先遍历

:::details 点击查看代码

function cloneGraph(node){
    let map=new Map();
    const clone=(node)=>{
        if(!node){
            return 
        }
        if(map.has(node)){
            return map.get(node);
        }
        let cloneNode=new Node(node.val,[]);
        map.set(node,cloneNode);
        for(let i=0;i<node.neighbors.length;i++){
            cloneNode.neighbors.push(clone(node.neighbors[i]));
        }
        return cloneNode;
    }
    return clone(node);
}

:::

性能分析:

• 时间复杂度：O(N)，其中 N 表示节点数量。深度优先搜索遍历图的过程中每个节点只会被访问一次。

• 空间复杂度：O(N)。存储克隆节点和原节点的哈希表需要 O(N) 的空间，递归调用栈需要 O(H) 的空间，其中 H 是图的深度，经过放缩可以得到 O(H)=O(N)，因此总体空间复杂度为 O(N)。

方案B 广度优先遍历

思路:

:::details 点击查看代码

function cloneGraph(node){
    if(!node){
        return node;
    }
    let map=new Map();
    let queue=[];
    queue.push(node);
    map.set(node,new Node(node.val,[]));
    while(queue.length){
        let n=queue.shift();
        for(let i=0;i<n.neighbors.length;i++){
            if(!map.has(n.neighbors[i])){
                map.set(n.neighbors[i],new Node(n.neighbors[i].val,[]));
                queue.push(n.neighbors[i]);
            }
            map.get(n).neighbors.push(map.get(n.neighbors[i]));
        }
    }
    return map.get(node);
}

:::

性能分析:

• 时间复杂度：O(N)，其中 N 表示节点数量。广度优先搜索遍历图的过程中每个节点只会被访问一次。

• 空间复杂度：O(N)。哈希表使用 O(N) 的空间。广度优先搜索中的队列在最坏情况下会达到 O(N) 的空间复杂度，因此总体空间复杂度为 O(N)。