10 一个有向图G存在拓扑排序,则图G一定没有环;而一个有向无环图却不一定存在拓扑排序。()
时间: 2024-04-04 09:32:01 浏览: 201
有向图的拓扑排序判断是否存在环
5星 · 资源好评率100%
正确。如果一个有向图存在拓扑排序,则说明该图可以被线性地排成一个序列,使得每个顶点都在它的后继节点之前出现。这意味着该图不可能存在环路,因为如果存在环路,那么其中至少存在一个顶点在该环路上的后继节点之前出现,从而无法进行拓扑排序。但是,有向无环图不一定存在拓扑排序,因为可能存在一些顶点之间的依赖关系无法进行排序。
阅读全文