拓扑排序用BFS还是DFS？Kahn算法与BFS、DFS有何关联？

开发者阿泽

2026-9-30

拓扑排序相关疑问解答

1. 拓扑排序的实现方法是BFS还是DFS？

两种实现都是合法的，不存在唯一正确的方案：

基于BFS的实现是更普及的写法：核心是统计每个节点的入度，每次取出入度为0的节点加入结果序列，再将该节点所有邻接节点的入度减1，重复操作直到没有入度为0的节点。如果最终结果序列的长度小于总节点数，说明图存在环，无法生成拓扑序。
基于DFS的实现同样符合拓扑排序的规则：对每个未访问的节点执行深度优先遍历，等该节点的所有后继节点都完成遍历后，将当前节点压入栈中，全图遍历完成后将栈逆序输出，就能得到合法的拓扑序，遍历过程中如果检测到回边也可以判定图存在环。

两种实现的时间复杂度都是O(V+E)（V为节点总数，E为边总数），实际使用中可以根据场景灵活选择。

2. Kahn算法是否等同于BFS或DFS？

Kahn算法和BFS、DFS都不是等价关系，BFS/DFS只是实现算法时可以用到的遍历工具：
Kahn算法的核心逻辑是「入度统计+入度消解」，和具体使用的遍历方式没有强绑定。它的标准实现用BFS的队列来存储待处理的入度为0的节点，所以很多资料会把Kahn算法直接等同于BFS实现的拓扑排序，但本质上BFS只是实现工具：比如你需要生成字典序最小的拓扑序时，把队列替换成优先队列存储入度为0的节点，依然属于Kahn算法的范畴。