试题-一个有向无环图的拓扑排序序列()是唯一的

题目

一个有向无环图的拓扑排序序列()是唯一的

A.一定

B.不一定

解答

正确答案是 B

有向无环图的拓扑排序可以看成图的层序遍历，每一层的顶点可以有不同的顺序，这就造成拓扑排序序列不唯一。

C 6条回复评论

李子寒

这题有够坑的，老是错

发表于 2023-06-23 22:00:00

孑然

在卷的地方，测试要比开发还要开发，又要懂业务又要懂测试，还要懂运维，我都搞不懂现在测试到底是个什么角色了

发表于 2022-05-08 21:00:00

pyyyyy

写的不错共勉~，最近也在开始写博客。大佬们来翻牌啊！

发表于 2021-09-13 11:00:00

小飞鞋

每个顶点出现且只出现一次。
若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。
一个有向无环图可以有一个或多个拓扑排序序列。

发表于 2018-10-13 10:24:40

星辰大海

拓扑排序就是在不断输出没有前驱顶点，并删除该定点和以他为尾的弧的过程。在有向图中选一个没有前驱，即入度为零的顶点输出时，如果此时有多个这样的点，可以任取一个，取点顺序的不同会造成输出的顺序不同，所以选择B，不一定。

发表于 2018-10-13 10:24:11

繁星知晓

如果不连通，就可以有多个起始节点，所以不唯一

发表于 2018-10-13 10:23:32

问题信息

分类：数据结构 - 最小生成树

难度: