首页 > 试题广场 >

设有向无环图G中的有向边集合E ={,2,3...

[单选题]

设有向无环图G中的有向边集合E ={<1,2>,<2,3>,<3,4>,<1,4>} ，则下列属于该有向图G的一种拓扑排序序列的是（）

查看正确选项

牛客875547913号

拓扑排序步骤：

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

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

重复上述两步，直至全部顶点均已输出，或者当前图中不存在无前驱的节点为止。（后一种情况说明有向图中存在环）

在该题中，我们先输出顶点1，并将该顶点1及弧<1, 2>，<1, 4>从图中删除；

此时无前驱的顶点只有2，输出2，并将顶点2及弧<2, 3>从图中删除；

此时无前驱的顶点只有3，输出3，并将顶点2及弧<3, 4>从图中删除；

此时图中仅剩顶点4，将其输出。

因此，拓扑排序的结果为：1, 2, 3, 4

发表于 2020-09-04 19:40:05 回复(0)

古古筝

只要满足以下条件即可

1在2面前

2在3面前

3在4面前

1在4面前

发表于 2019-10-29 13:09:05 回复(0)

刘诗歌

请知道本题正规解法的大佬分享下，感谢。

发表于 2019-08-26 18:44:47 回复(0)

提交观点

问题信息

C++工程师小米集团测试开发工程师测试工程师图 2019 Java工程师

来自：小米2019秋招测试开...

上传者：小小

难度：

3条回答 24收藏 4917浏览

扫一扫，把题目装进口袋