Kahn BFS拓扑排序时间复杂度为何是O(V+E)而非O(n²)

以下为问题对应的Java实现代码：

public static void sort(ArrayList<ArrayList<Integer>> adjList,int vertices){
        int[] inDegree=new int[vertices];
        for(int i=0;i<adjList.size();i++){
            for(int element : adjList.get(i)){
                inDegree[element]++;
            }
        }
        Queue<Integer> ourQueue=new LinkedList<>();
        for(int i=0;i<vertices;i++){
            if(inDegree[i]==0){
                ourQueue.add(i);
            }
        }
        while(!ourQueue.isEmpty()){
            int poppedElement=ourQueue.poll();
            System.out.print(poppedElement+" ");
            for(int element : adjList.get(poppedElement)){
                inDegree[element]--;
                if(inDegree[element]==0){
                    ourQueue.add(element);
                }
            }
        }
    }

计算入度的双层循环时间复杂度是不是O(n²)？ #

不是。这段代码基于邻接表存储图结构，双层循环的总执行次数根本达不到n²量级：

• 外层循环遍历所有顶点，共执行V次，对应O(V)操作
• 内层循环每次只遍历当前顶点的直接邻接点，也就是当前顶点所有出边指向的节点。所有顶点的出边数量累加起来刚好等于图的总边数E，因此内层循环总执行次数固定为E次，对应O(E)操作
  观察到的“多次访问顶点”，本质是遍历边时访问到边的终点，每条有向边只会在遍历起点的邻接表时被访问恰好1次，不存在重复遍历。只有图用邻接矩阵存储时，入度计算需要遍历每个顶点对应的整行矩阵，总操作数才会达到O(V²)，邻接表场景下不存在这个问题。

while循环阶段多次访问顶点，为什么整体复杂度还是O(V+E)？ #

这部分没有冗余操作，总操作数拆解开同样是线性量级：

• 队列操作部分：每个顶点只有在入度被减到0的时候才会入队，一个顶点的入度不可能第二次降到0，因此每个顶点最多入队1次、出队1次，出队后的打印操作也只执行1次，这部分总操作数是O(V)
• 内层遍历邻接点的部分：和计算入度的逻辑一致，只有当某个顶点被出队时，才会遍历它的邻接表，每个顶点的邻接表只会被遍历1次，所有邻接表的遍历总次数累加起来等于总边数E，对应O(E)操作
  这里的“多次访问顶点”同样是在处理边：每次访问邻接节点element，本质是处理poppedElement -> element这一条边，给element的入度减1，每条边只会被处理1次，不存在无意义的重复访问。

总复杂度核算 #

把所有步骤的操作数加总即可得到最终结果：

• 初始化入度数组、遍历所有顶点筛选初始入度为0的节点入队：合计O(V)
• 计算初始入度的双层循环：外层遍历V个顶点，内层累加遍历E条边，合计O(V+E)
• while循环全流程：每个顶点出入队各1次共O(V)，所有边被遍历处理1次共O(E)，合计O(V+E)

忽略常数系数后，整体时间复杂度就是标准的O(V+E)。

时间复杂度核算看的是所有基本操作的总执行次数，不是单纯看循环嵌套层数。如果双层循环的内层总执行次数是固定的E、而非每次都遍历全部V个顶点，就不会产生O(V²)的复杂度。

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