首页 > 试题广场 >

对如下所示的有向图进行拓扑排序，得到的拓扑序列可能是（）

[单选题]

查看正确选项

二咩

314265或314625两种情况

发表于 2016-11-28 08:38:26 回复(0)

philian

每次选取极大顶点（入度为0的顶点），并把它跟它的出度一起从图中删掉
第一次删掉3
第二次删掉1
第三次删掉4
第四次可以删掉2或者6，若依据选项CD删掉2，那么第五次删掉6，最后删掉5
314265，选D

发表于 2016-12-16 10:39:41 回复(0)

牛客-liwei4939

按照拓扑排序的定义，若有向无环图中存在一条从i到j的边，则拓扑排序中i一定在j的前面

发表于 2017-04-23 15:24:03 回复(0)

shiyan娃娃

每次选取极大顶点（入度为0的顶点），并把它跟它的出度一起从图中删掉：

发表于 2017-08-24 17:33:23 回复(0)

大脸盘纸

就是看能不能顺着箭头走通

发表于 2016-12-13 16:51:53 回复(0)

在找对象的潜伏者很年轻

拓扑序是按照点的先后顺序排列的，也就是说入度为0的点一定是排在前面的，我们直接对一个图BFS一遍，BFS过程中更新每个点的入度，如果一个点的入度为0，那么就将其加入拓扑序，并且删除其与后继结点的所有边。

发表于 2022-07-23 18:57:11 回复(0)

提交观点

问题信息

图

上传者：城市里的养猫者

难度：

6条回答 185收藏 11002浏览

扫一扫，把题目装进口袋