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