在有向图G的拓扑序列中,若顶点vi在顶点vj之前,则下列情形不可能出现的是( )。

admin2018-08-12  69

问题 在有向图G的拓扑序列中,若顶点vi在顶点vj之前,则下列情形不可能出现的是(    )。

选项 A、G中有弧<vi,vj
B、G中有一条从vi到vj的路径
C、G中没有弧<vi,vj
D、G中有一条从vj到vi的路径

答案D

解析 此题考查的知识点是图的拓扑排序。根据拓扑排序的定义,若顶点vi与顶点vj有一条弧,则拓扑序列中顶点vi必在顶点vj之前。若有一条从vj到vi的路径,则顶点vi不可能在顶点vj之前。所以应选D。
转载请注明原文地址:https://jikaoti.com/ti/x1fjFFFM
0

最新回复(0)