问题 单项选择题

拓扑序列是无环有向图中所有顶点的一个线性序列,图中任意路径中的各个顶点在该图的拓扑序列中保持先后关系。对于图6-10所示的有向图,()不是其的一个拓扑序列。

A.1526374

B.1526734

C.5123764

D.5126374

答案

参考答案:C

解析:

[要点解析] 拓扑序列是将有向图中所有顶点的一个线性序列的过程,并且该序列满足:若在图中存在从顶点Vi到Vj有一条路径,则在该线性序列中,顶点Vi必然在顶点Vj之前。

对有向图进行拓扑排序的方法如下:

①在有向图中选择一个入度为零(没有前驱)的顶点且输出之。

②从网中删除该顶点及从该顶点出发的所有弧。

③重复上述两步,直到图中不存在入度为0的顶点为止。

对于图6-10所示的有向图,进行拓扑排序的顶点序列有:5126374、5126734、1526374、1526734。而选项C的“5123764”不是其的一个拓扑序列。

多项选择题
单项选择题