首页 > 试题广场 >

关于拓扑排序，下列说法正确的是( )。

[不定项选择题]

关于拓扑排序，下列说法正确的是( )。

所有连通的有向图都可以实现拓扑排序

对同一个图而言，拓扑排序的结构是唯一的

拓扑排序中入度为 0 的结点总会排在入度大于 0 的结点的前面

拓扑排序结果序列中的第一个结点一定是入度等于 0 的点

查看正确选项

牛客862228207号

答案：D。存在环就不能实现拓扑排序，A错；若有多个入度为0的点，排序不唯一，B错；当图中有多个入度为0的点，当你选择一个点作为起点，它后续的点入度不为0但是排在入度为0的点的前边，C错。

发表于 2022-08-09 11:33:12 回复(0)

xuxuxuxuxu

难点在C

3个点1,2,3

一条有向边1->2

拓扑序可以是1,2,3

发现此时入度为1的点2在入度为0的点3前面

发表于 2019-10-17 20:56:45 回复(1)

copy201807271619405

答案选择C而非D

拓扑排序

1 在图中选择一个入度为0的顶点；

2 输出该顶点，并删除该顶点的出度；

3 循环步骤1，2

发表于 2019-10-06 21:44:41 回复(0)

Leven_

这道题在比赛中D选项是“等于”，但是nowcoder在该题录入时写成了“大于”，在改成了大于之后的情况下这道题是没有答案的！

对于上一个解答答案是C的选项的 @copy201807271619405 同学应该是没有想到此题的图可以不连通，只要图不联通，C选项就不一定成立！！

发表于 2019-10-09 16:38:03 回复(0)

jfjdjdjs

本题没有正确答案。 c非连通图时不满足。拓扑排序必须在有向无环图，其时间复杂度O(n+e)。

编辑于 2019-11-23 19:38:29 回复(2)

提交观点

问题信息

提高 C++ Pascal 图论选择题

来自：NOIP2010初赛提高组

上传者：牛客309901号

难度：

5条回答 6收藏 11691浏览

扫一扫，把题目装进口袋