图的 BFS 的时间复杂度

Question

我无法理解图的 BFS 的时间复杂度是 O(v+2E)， 其中 V 是顶点数，E 是边数。

/**
 * @param {number} V
 * @param {number[][]} adj
 * @returns {number[]}
*/
class Solution {
    // Function to return Breadth First Traversal of given graph.
    bfsOfGraph(V, adj) {
        const queue=new Queue();
        
        const visited=Array.from({length:V},()=>false);
        const ans=[];
        
        queue.add(0);
        visited[0]=true;

        
        while(!queue.isEmpty()){
            const el=queue.remove();
            ans.push(el);
            
            for(const v of adj[el]){
                if(!visited[v]){
                    queue.add(v);
                    visited[v]=true;
                }
            }
        }
        
        return ans;
    }
}


class Queue {
    constructor() {
        this.arr = [];
        this.start = 0;
        this.end = -1;
    }


    add(el) {
        this.arr.push(el);
        this.end++;
    }


    remove() {
        if (this.isEmpty())
            return;

        let el = this.arr[this.start];
        this.start++;

        return el;
    }

    isEmpty() {
        return this.start > this.end;
    }

    get length() {
        return this.end - this.start < 0 ? 0 : this.end - this.start + 1;
    }
}

在上面图的 BFS 的 javascript 实现中，由于队列只保存 尚未访问过的顶点，这使得外循环运行恰好 V 次，并且对于每个顶点 顶点，我们通过查看访问数组来检查它的相邻节点是否已被访问，其中 本身是一个 O(1) 操作。因此，从技术上讲，对于每个顶点，我们进行 O(1) 次操作，等于度数 该顶点的。那么，为什么算法的 TC 不等于 O(V*平均图度).

我尝试了一切，但仍然没有线索。我检查了有关堆栈溢出的类似问题，但没有帮助。 有人可以解释一下为什么它是 O(V+E) 而不是 O(V*平均图度).

Answer 1

O(𝑉+𝐸) 与 O(𝑉𝑑)（几乎）相同，其中 𝑑 是平均度数。当图未连接时，O(𝑉𝑑) 并不完全正确。举个极端的例子，图没有边，那么𝑉𝑑就是0，但显然你仍然需要访问每个节点来找出它没有邻居，所以实际上我们应该说O(𝑉+𝑉𝑑)。经过修正后，它们是等价的：

由于每条边都连接两个顶点，因此每条边都会将两个顶点的度数加一，使度数之和等于 2𝐸，得出平均值 𝑑 = 2𝐸/𝑉。 如果我们将其代入 O(𝑉+𝑉𝑑)，我们会得到 O(𝑉+2𝑉𝐸/𝑉) = O(𝑉+2𝐸) = O(𝑉+𝐸)。请注意，因子 2 与大 O 表示法 无关，可以用因子 1 代替。