首页 > 试题广场 > 判断下列说法是否正确:对AOV网进行拓扑排序得到的拓扑有序序
[单选题]
判断下列说法是否正确:对AOV网进行拓扑排序得到的拓扑有序序列不一定是唯一的。( )
  • 正确
  • 错误
推荐
A。考察的是图的拓扑排序思想和特性。
有向图每个顶点代表一个活动,弧<Vi,Vj>表示活动,i必须先于j进行,图中不允许出现回路,称为AOV(Activity On Vertex)。

对有向图进行拓扑排序:

  1. 输出图中一个没有前驱节点的顶点
  2. 删除该顶点以及该顶点的出边。
  3. 重复上述两步直到所有的顶点都被输出,完成拓扑排序。或者还有未输出的顶点,而这些顶点有前驱而不能删除,说明存在环路。


  1. 如上图拓扑排序 C2、C1、C4、C3、C5、C7、C6 也可以a途中C1放在C2之前,c图中C3、C4也可以任意输出,……。


所以一个AOV的拓扑序列不是唯一的,AOV中如果出现回路则一定不能完成拓扑排序。
编辑于 2019-07-22 14:17:19 回复(0)
A 拓扑排序结果不唯一
发表于 2019-07-21 11:34:27 回复(0)
选A
发表于 2019-07-19 15:25:38 回复(0)
a
发表于 2018-12-10 20:48:00 回复(0)