对下图进行拓扑排序，（）序列不是该图的拓扑序列

[单选题]

```
123546
```
```
125346
```
```
231546
```
```
213546
```

查看答案及解析

推荐

白驹之过隙

选B。

拓扑排序：将有向图中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边<u,v>∈E(G)，则u在线性序列中出现在v之前。

从有向图中没有入度的顶点开始
依据顶点出度的指向进行对线性序列的逐渐加入

B选项中：1--->2--->5--X--3--->4--->6 其中顶点5没有出度指向3

编辑于 2019-11-28 14:20:56 回复(2)

Jino.

选B。

拓扑排序是将AOV网中所有顶点排成一个线性序列的过程，并且该序列满足：若在AOV网中从顶点vi到vj有一条路径，则在该线性序列中，顶点vi必然在顶点vj之前。在B项中，顶点3到顶点5存在路径，因此3不能在5之后，所以B项错误。
对AOV网进行拓扑排序的方法如下：
(1)在AOV网中选择一个入度为零(没有前驱)的顶点且输出它；
(2)从网中删除该顶点及与该顶点有关的所有边；
(3)重复上述两步，直至网中不存在入度为零的顶点为止。

发表于 2019-11-27 18:54:06 回复(0)