为什么我只认为Leetcode的时间复杂性“ 133”。克隆图是o（e）而不是o（v＆＃x2b; e）

Question

我有一个关于leetcode图问题的问题[133。克隆图]“ https://leetcode.com/problems/clone-graph/”。

我使用DFS解决了这个问题，这是我的代码JavaScript：

/**
 * // Definition for a Node.
 * function Node(val, neighbors) {
 *    this.val = val === undefined ? 0 : val;
 *    this.neighbors = neighbors === undefined ? [] : neighbors;
 * };
 */

/**
 * @param {Node} node
 * @return {Node}
 */
var cloneGraph = function(node) {
    if(!node) return null;
    const visited = new Map();
    
    const dfs = (node) => {
        const n = [];
        if(visited.has(node.val)) return visited.get(node.val);
        let newNode = new Node(node.val);
        visited.set(node.val,newNode);
        
        for(let on of node.neighbors){
            n.push(dfs(on));
        }
        
        newNode.neighbors = n;
        return newNode;
    }
    
    return dfs(node);
};

我的解决方案图就是这样：

< img src =“ https://i.sstatic.net/tgjrh.png” alt =“在此处输入图像说明”>

假定v/e是图形的顶点/边缘。

我发现很多人说这个问题的时间复杂性是o（v+e），但我无法抓住它，因为在这种情况下，我认为这是o（e）。

我认为，我们的输入只是一个节点对象而不是相邻列表，它是一个无方向的图，因此我们不需要检查每个节点的连续序列，我们只需要从输入“节点”和然后它将扫描整个图，这只是树木问题的一种普通DF。

那里有什么错吗？如果是这样，有人可以解释一下为什么我对此解决方案有误会吗？

Answer 1

我发现很多人说这个问题的时间复杂性是o（v+e），但我无法抓住它，因为在这种情况下，我认为这是o（e）。

你是绝对正确的。代码挑战表明该图是连接的，这是一个重要的信息。这意味着至少有v -1边。由于该算法仅通过访问边缘仅在每个方向上访问一次，而不会以另一种方式访问​​节点，而不是通过边缘行驶（一次是第一个节点），o（e）与o（v+）相同e）。

Answer 2

在每个带有n顶点的简单图表中，边数均由n^2绑定，因此o（e）= o（v^2）。完整的图表可以看到，这种界限是紧密的（每个顶点彼此连接）。

但是，对于许多（自然或人为的）图类别的类别类别，对事先已知的边缘数量有限制（例如，树具有v-1 edges），因此，根据不同的不同而言，表达复杂性测量值很普遍在v和e上被正式视为独立实体。

通常，dfs涉及o（v+e）操作，因为...

1. 每个顶点都访问了，无论是在新组件中，它都作为新组件中的初始顶点，无论是在以下边缘的过程中在DFS期间。
2. 才能找出...

（接近）访问了每个边缘：只有事先知道它已经在已经看到的顶点结束的情况下，您才可以跳过一个，但是要知道您需要遵循边缘 ：一旦您看到所有顶点，请立即停止DF。但这取决于DFS的目的 - 如果要构建一个生成树，则可以，如果要检测一个周期，则不是。

返回到您的特定设置：在琐碎的情况下，所有顶点和所有边都必须访问以克隆图，因此o（v+e）。但是，如果该图已连接，您会事先知道访问所有边缘后您已经看到了所有顶点，因此：o（e）。