数据结构与算法 · 单选题 · 第 55 题
计算机基础面试八股 · 第 55 题
拓扑排序可以用来解决下列哪个问题?
- A求带权图中两点间的最短路径
- B求无向连通图的最小生成树
- C判断有向图中是否存在环
- D判断无向图能否被二着色
答案
C C. 判断有向图中是否存在环
解析
Kahn 算法反复删除入度为 0 的顶点,如果最后还有顶点没被删掉,说明图中有环。所以拓扑排序常用于课程依赖、构建依赖、任务调度中的环检测。最短路径用 Dijkstra 等算法,最小生成树用 Prim 或 Kruskal,二着色用 BFS 或 DFS 判断。