拓扑序列是无环有向图中所有顶点一个线性序列，图中任意路径中各个顶点在该图拓扑序列中保持先后关系。对于图中有向图， ( ) 不是其一个拓扑序列。
- A.1526374
- B.1526734
- C.5123764
- D.5126374
正确答案及解析
正确答案
C
解析
拓扑序列是将有向图中所有顶点排成一个线性序列，并且该序列满足：若在图中存在从顶点Vi到Vj路径，则在该线性序列中，顶点i必然在顶点Vj之前。对有向图进行拓扑排序方法如下：① 在有向图中选择一个入度为零(没有前驱)顶点且输出之：② 从有向图中删除该顶点及从该顶点出发所有弧；③ 重复上述两步，直至图中不存在入度为0顶点为止。对于图3-4所示有向图，进行拓扑排序顶点序列有：5126374、5126734、1526374和1526734。而选项C"5123764"不是其中一个拓扑序列。
你可能感兴趣的试题
-
- A.V(S2)和P(S4)
- B.P(S2)和V(S4)
- C.P(S2)和P(S4)
- D.V(S2)和V(S4)
- 查看答案
-
- A.V（S1）P（S2）和V（S3）
- B.P（S1）V（S2）和V（S3）
- C.V（S1）V（S2）和V（S3）
- D.P（S1）P（S2）和V（S3）
- 查看答案
-
- A.P（S4）和V（S4）V（S5）
- B.V（S5）和P（S4）P（S5）
- C.V（S3）和V（S4）V（S5）
- D.P（S3）和P（S4）V（P5）
- 查看答案
-
- A.P(S3)和V(S4)V(S5)
- B.V(S3)和P(S4)P(S5)
- C.P(S3)和P(S4)P(S5)
- D.V(S3)和V(S4)V(S5)
- 查看答案
-
- A.P（S2）和P（S4）
- B.P（S2）和V（S4）
- C.V（S2）和P（S4）
- D.V（S2）和V（S4）
- 查看答案