题12
题目
Q:在有向图 的拓扑序列中,若顶点 在顶点 之前,则不可能出现的情形是 ( ).
A. 中有弧
B. 中有一条从 到 的路径
C. 中没有弧
D. 中有一条从 到 的路径
分析
A:拓扑排序的卡恩算法就是删除入度为0的点，然后删除以这个点为起点的边，然后重复这个过程。
所以如果 在 之前，代表有一条从 到 的路径，也就是对于 的入度为0， 的入度不为0。
那么 的入度为0， 的入度不为0，所以 到 有一条路径，所以D是不可能的。
解
D
若图 中存在一条从 到 的路径,说明 是 的前驱,则要把 消去以后才能消去 , 从而拓扑序列中必然先输出 ,再输出 ,这显然与题意矛盾。