不同图实现中BFS遍历的时间复杂度推导疑问

你的BFS代码（无向无权图） #

public ArrayList<Integer> getBFSResult() {
    int noOfVertices = getNoOfVertices(), exploredNodesCount = 0;
    boolean visitedVertices[] = new boolean[noOfVertices];
    ArrayList<Integer> bfsResult = new ArrayList<>();
    
    Queue<Integer> queue = new ArrayDeque<>();
    
    if(noOfVertices > 0) {
        queue.add(0);
        visitedVertices[0] = true;
        while(!queue.isEmpty() && exploredNodesCount < noOfVertices) {
            int idx = queue.peek();
            ArrayList<Integer> adjacentNodes = getAdjacentNodes(idx);
            for(int i: adjacentNodes) {
                if(!visitedVertices[i]) {
                    queue.add(i);
                    visitedVertices[i] = true;
                }
            }
            int exploredNodeIndex = queue.remove();
            bfsResult.add(exploredNodeIndex);
            exploredNodesCount++;
        }   
    }
    return bfsResult;
}

你的推导结果 #

• 边列表实现的图：时间复杂度为O(|V||E| + |V| + 2|E|)，核心依据是getAdjacentNodes(idx)耗时O(|E|)，执行|V|次；for循环总计执行2*|E|次。
• 邻接矩阵实现的图：时间复杂度为O(|V|² + |V| + 2*|E|)，核心依据是getAdjacentNodes(idx)耗时O(|V|)，执行|V|次。
• 邻接表实现的图：时间复杂度为O(|V|² + 2*|E| + |V|)，核心依据是getAdjacentNodes(idx)耗时O(|V|)，执行|V|次。

注：未考虑bfsResult.add的时间复杂度，认为其总耗时为O(|V|*(|V|+1)/2)。

你的问题 #

网上资料显示边列表实现的图的BFS时间复杂度为O(|E|²)，邻接表实现的为O(|V|+|E|)，但无法通过上述代码推导出这些结论，请问忽略了什么？

核心错误点分析 #

1. 邻接表实现的时间复杂度推导错误 #

你错误地假设邻接表的getAdjacentNodes(idx)时间复杂度为O(|V|)，但实际上：

• 邻接表为每个顶点维护了一个仅包含其邻接顶点的列表，getAdjacentNodes(idx)可以直接返回该列表的引用，耗时为O(1)。
• 遍历邻接节点的for循环，总执行次数等于所有顶点的度数之和。对于无向图，所有顶点度数之和为2|E|，因此这部分总时间是O(|E|)。
• while循环会执行|V|次（每个顶点出队一次），每次循环内的常量操作耗时O(1)，这部分总时间是O(|V|)。
• 综上，邻接表实现的BFS总时间复杂度为O(|V| + |E|)，与网上结论一致。

2. 边列表实现的时间复杂度差异原因 #

网上所说的O(|E|²)并非边列表BFS的标准时间复杂度，你的推导O(|V|*|E|)更符合实际情况：

• 边列表的getAdjacentNodes(idx)需要遍历所有|E|条边筛选相邻顶点，每次调用耗时O(|E|)。
• 若图是连通的，getAdjacentNodes会被调用|V|次，总时间为O(|V|*|E|)；若图不连通，完整BFS需遍历所有未访问顶点作为起点，调用次数仍为O(|V|)，总时间不变。
• 网上的O(|E|²)可能是混淆了其他图操作（如边列表中的任意边查找），或是极端稀疏图场景下的等价表述（当|V|≈|E|时，O(|V|*|E|)等价于O(|E|²)），但这不是BFS的标准复杂度。

3. 代码的局限性 #

你的代码仅从顶点0开始遍历，若图存在多个连通分量，未与顶点0连通的节点不会被遍历。完整的BFS需在外部增加循环，遍历所有顶点并对未访问顶点执行入队操作，但这不会改变核心逻辑的复杂度阶数。

关于bfsResult.add的时间复杂度 #

ArrayList.add的均摊时间复杂度为O(1)，总共有|V|次调用，因此这部分总时间为O(|V|)，可合并到整体复杂度中，不影响最终阶数。

内容的提问来源于stack exchange，提问作者Shri