单选题
拓扑排序是将有向图中所有顶点排成一个线性序列的过程,并且该序列满足:若在AOV网中从顶点V
i
到V
j
有一条路径,则顶点V
i
必然在顶点V
j
之前。对于如图所示的有向图,______是其拓扑序列。
【正确答案】
C
【答案解析】本题考查数据结构中的拓扑排序。
拓扑排序通俗一点来讲,其实就是依次遍历没有前驱节点的节点。而某一时刻没有前驱节点的节点有可能存在多个,所以一个图的拓扑排序可能有多个。
以本题为例,1号节点与2号节点都没有前驱节点,所以拓扑排序的第1个元素可以是1,也可以是2。当1与2都访问完了,便可访问3号节点,3号节点访问完了,便可访问5号节点,访问完5号节点,可访问4号,或是7号节点。
所以拓扑排序结果为:(12)35(47)6。括号中有多个数字,则代表着这多个数字的顺序可以变化。
这样,具体的拓扑排序结果为:1235476、1235746、2135476、2135746。