问题
单项选择题
拓扑序列是无环有向图中所有顶点的一个线性序列,图中任意路径中的各个顶点在该图的拓扑序列中保持先后关系。对于图6-10所示的有向图,()不是其的一个拓扑序列。
A.1526374
B.1526734
C.5123764
D.5126374
答案
参考答案:C
解析:
[要点解析] 拓扑序列是将有向图中所有顶点的一个线性序列的过程,并且该序列满足:若在图中存在从顶点Vi到Vj有一条路径,则在该线性序列中,顶点Vi必然在顶点Vj之前。
对有向图进行拓扑排序的方法如下:
①在有向图中选择一个入度为零(没有前驱)的顶点且输出之。
②从网中删除该顶点及从该顶点出发的所有弧。
③重复上述两步,直到图中不存在入度为0的顶点为止。
对于图6-10所示的有向图,进行拓扑排序的顶点序列有:5126374、5126734、1526374、1526734。而选项C的“5123764”不是其的一个拓扑序列。