2. 从业资格
  3. 拓扑排序是将有向图中所有顶点排成一个线性序列的过程，并且该序列满足：若在AOV网

拓扑排序是将有向图中所有顶点排成一个线性序列的过程，并且该序列满足：若在AOV网

最全题库2022-08-02  70
问题 拓扑排序是将有向图中所有顶点排成一个线性序列的过程，并且该序列满足：若在AOV网中从顶点Vi到Vj有一条路径，则顶点Vì必然在顶点Vj之前。对于下面所示的有向图，（　　）是其拓扑序列。A.1234576B.1235467C.2135476D.2134567
选项 A.1234576
B.1235467
C.2135476
D.2134567
答案 C
解析 本题考查数据结构中的拓扑排序。
拓扑排序通俗一点来讲，其实就是依次遍历没有前驱结点的结点。而某一时刻没有前驱结点的结点有可能存在多个，所以一个图的拓扑排序可能有多个。
以本题为例，1号结点与2号结点都没有前驱结点，所以拓扑排序的第一个元素可以是1，也可以是2。当1与2都访问完了，便可访问3号结点，3号结点访问完了，便可访问5号结点，访问完5号结点，可访问4号，或是7号结点。
所以拓扑排序结果为：（12）35（47）6。括号中有多个数字，则代表在这多个数字的顺序可以变化。
这样，具体的拓扑排序结果为：1235476、1235746、2135476、2135746。
转载请注明原文地址:https://tihaiku.com/congyezige/2410031.html
本试题收录于： 中级 软件设计师题库软件水平考试初中高级分类

中级 软件设计师

软件水平考试初中高级

相关试题推荐
随机试题
最新回复(0)