首页 > 试题广场 >

对于一个有向有环图，其拓扑序

[单选题]
对于一个有向有环图，其拓扑序 
  • 不存在
  • 存在且仅有一个
  • 存在且可以有多个
  • 视情况而定
查看答案及解析
添加回答
科大15届软工代言人头像 科大15届软工代言人
a.不存在
通常可以用拓扑排序的方法检测图中是否有环。
过程：从起始点开始按拓扑排序依次删除节点，直到拓扑排序结束，如果依然有节点未被删除，那么一定是因为存在环，使得无法找到环的拓扑排序的入口。
由此可见，有向有环图无法输出拓扑排序。
发表于 2023-03-31 14:19:32 回复(0)
bigodf头像 bigodf
有向无环图存在拓扑序，可能不唯一
有环图必不存在拓扑序
发表于 2020-09-25 14:39:54 回复(0)
提交观点

问题信息

算法工程师 第四范式 2020
上传者：小小
难度：
2条回答 1060浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号