我要招人

去企业版

首页 > 试题广场 >

对下图进行拓扑排序，可以得到不同的拓扑序列的个数是（）

[单选题]

```
4
```
```
3
```
```
2
```
```
1
```

查看答案及解析

范二er

a没有被其他节点指向;

d没有指向其他节点;

所以拓扑排序的形式如下:aXXXd;

又因为b指向c,那么b一定是在c的前面;

所以可能的拓扑排序如下:

abced,aebcd,abecd;

发表于 2017-01-04 11:30:58 回复(1)

二咩

观察图可知只有a没有被其他节点指向，所以a节点是第一个；只有d没有指向其他节点，是最后一个；b要在c前面，e可以放入中间三个空隙，所以有三种情况。

发表于 2016-11-28 08:32:22 回复(0)

小柒木有熙

拓扑排序的步骤：
(1)、找到一个没有后继的顶点(如果有一条边从A指向B,那么B是A的后继)。
(2)、从图中删除这个顶点，在列表的前面插入顶点的标记。

(3)、重复步骤1和2.直到所有的顶点都从图中删除。这时列表显示的顶点顺序就是拓扑排序的结果。

从图可知删除 d 后有两种删法，一是删 e ，一是删 c 。依次类推可以得到不同的拓扑序列

发表于 2017-06-19 12:39:33 回复(0)

VAim

拓扑排序的步骤：

1) 在有向图中选一个没有前驱的顶点且输出之；

2)从图中删除该顶点和所有以它为尾的弧。

重复上述两步，直至全部顶点均已输出，或者当前图中不存在无前驱的顶点为止。

发表于 2017-05-31 22:42:49 回复(0)

倚杖听江声

在所有该事件的前提事件完成之后，才可以执行该事件。

发表于 2018-08-27 11:28:15 回复(0)

牛客67236699号

但是按照拓扑排序算法的步骤，其实只有两种结果，分别是aebcd,abced,并没有abecd,因为如果是ab...d这种序列的话，说明e要先于b进栈，之后b出栈后紧接着c会进栈，因此下一个出栈的只会是c而不会是e，所以不会有abecd

编辑于 2021-05-22 22:32:52 回复(1)

不做人了

拓扑排序如下

a e b c d

a b e c d

a b c e d

发表于 2020-06-29 10:53:10 回复(0)

爱糖果的Kitty

求拓扑序列的操作就是不断选取入度为0的点（边选边删）。

一般去掉第一个以后，有好几种删法。

编辑于 2018-09-10 13:07:43 回复(0)

misiyu

a一定在开头，d一定在结尾。中间三个无序自由排序且保证b在c前。

A₃ ³/ 2 = 3

编辑于 2017-07-01 17:41:00 回复(0)

天涯追梦的航帆

拓扑有序序列：

把AOV网络中各顶点按照他们相互之间的优先关系排列到一个线性序列的过程。若vi 是vj前驱，则vi 一定在vj，对于没有优先关系的点，顺序任意。

发表于 2017-06-12 18:08:03 回复(0)

提交观点

问题信息

图

上传者：城市里的养猫者

难度：

10条回答 232收藏 11444浏览

对下图进行拓扑排序，可以得到不同的拓扑序列的个数是（）

问题信息

热门推荐

相关试题