我要招人

去企业版

首页 > 试题广场 >

用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应

[单选题]

用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是( )

```
逆拓扑有序
```
```
拓扑有序
```
```
无序的
```

查看答案及解析

xfei

不理解为什么选逆拓扑有序

这个图入栈顺序不可以是A->B->D->C吗？即出栈顺序为CDBA。可是拓扑序列为ACBD。

求解释

发表于 2017-08-09 10:46:46 回复(5)

更多回答

疯狂的1024

首先说下这个拓扑有序，说明这个图得到的拓扑唯一。如上面这个图的拓扑就是一个有序的。
言归正传：首先这个有向无环图的深度遍历得到的序列是不唯一的。比如从ABCD、ABDC、CBDA等这些都是这些。但是他们退栈确实相同的。A入栈然后看A有那个可以到达的访问B，然后查看B有没有哪个可以到达的访问。有D。看D还有没有哪个可以到达的访问。没有。D出站，看看B有没有哪个除了D可以访问的。没有退栈B。查看A还有没有除了B其他的访问的。有C，C入栈，看看C没有哪个除了BD可以访问的，没有退栈C，所以A还有没有除了BC可以到达的，没有退栈A。最后退栈的序列就是DBCA。同理可以验证其他几个最后退栈的序列都会DBCA。然后这个有向图的拓扑序列是ACBD。所以说这哥深度优先遍历算法中退栈次序是逆拓扑有序。

编辑于 2018-06-19 07:36:41 回复(0)

凯风

DFS是一个递归算法,在遍历的过程中,先访问的点被压入栈底。拓扑有序是指如果点U到点V有一条弧,则在拓扑序列中U一定在V之前.深度优先算法搜索路径恰恰是一条弧,栈的输出是从最后一个被访问点开始输出,最后一个输出的点是第一个被访问的点.所以是逆的拓扑有序序列

发表于 2017-07-30 23:34:16 回复(0)

五朵花，金花牛牛

拓扑排序和逆拓扑排序都是对无环图才有用。对有向无环图，拓扑排序是每次输出入度为0的点，逆拓扑排序则是出度为0 的点。

对下图，入度为0 的点有0和2（因此拓扑排序不唯一）。假设先把0压入栈中根据dfs，接下来一直把1,3,4压入栈中，到了4之后没有接下来的点所以输出，则为4,3,1,0.然后把2压入并输出（在下图是第二个for循环把未访问的点进行dfs）所以顺序是4,3,1,0,2。根据我刚刚讲的，拓扑是把入度为0的点输出，也从0开始，输出后1和2的入度都为0，接着是输出1，输出3，输出4，输出2，即0,1,3,4,2（也可以是2，0,1,3,4，或0,2,1,3,4拓扑不唯一）

逆拓扑则可以是4,3,1,0,2

如果用dfs遍历图，用的是队列不是栈，则输出为拓扑排序。（不理解的自己理解栈和队列的输出）

编辑于 2023-05-14 20:35:36 回复(0)

牛客220684022号

dfs会一直访问直到没有点可达，此时输出的点就是出度为0的点，而返回时由于该点被标记，相当于该点被删去，因而是逆拓扑有序

发表于 2022-04-30 15:44:24 回复(0)

天尊墨宇

选A
首先说下这个拓扑有序，说明这个图得到的拓扑唯一。如上面这个图的拓扑就是一个有序的。
言归正传：首先这个有向无环图的深度遍历得到的序列是不唯一的。比如从ABCD、ABDC、CBDA等这些都是这些。但是他们退栈确实相同的。A入栈然后看A有那个可以到达的访问B，然后查看B有没有哪个可以到达的访问。有D。看D还有没有哪个可以到达的访问。没有。D出站，看看B有没有哪个除了D可以访问的。没有退栈B。查看A还有没有除了B其他的访问的。有C，C入栈，看看C没有哪个除了BD可以访问的，没有退栈C，所以A还有没有除了BC可以到达的，没有退栈A。最后退栈的序列就是DBCA。同理可以验证其他几个最后退栈的序列都会DBCA。然后这个有向图的拓扑序列是ACBD。所以说这个深度优先遍历算法中退栈次序是逆拓扑有序。

发表于 2020-07-13 17:45:40 回复(0)

YCYCY

栈先入后出

发表于 2018-09-05 17:24:16 回复(0)

提交观点

问题信息

图

上传者：阿奻_

难度：

7条回答 73收藏 13844浏览

用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应

问题信息

热门推荐

相关试题