试题- 已知有向图G=(V,E)，其中V={ V1 , V2 , V3 , V4 , V5 , V6 , V7 }， E={<V1 ,V2>, <V1 ,V3>, <V1 ,V4>, <V2 ,V5>,

题目

已知有向图G=(V,E)，其中V={ V1 , V2 , V3 , V4 , V5 , V6 , V7 }，
E={<V1 ,V2>, <V1 ,V3>, <V1 ,V4>, <V2 ,V5>, <V3 ,V5>, <V3 ,V6>, <V4 ,V6>, <V5 ,V7>, <V6 ,V7>}G的拓扑序列是（）

A.V1, V3, V4, V6, V2, V5, V7

B.V1, V3, V2, V6, V4, V5, V7

C.V1, V3, V4, V5, V2, V6, V7

D.V1, V2, V5, V3, V4, V6, V7

上一题 下一题

解答

正确答案是 A

1. 根据连接关系画出有向图

2. 选择一个入度为0的顶点输出，并删除该顶点以及该顶点的所有出度。

3.重复第二步，直到所有顶点都被输出。

//说明：根据入度为0的顶点选择的不同，拓扑排序的结果不唯一。

C 4条回复评论

紫侠仙子

楼主的这篇文章写得很精彩，总结的很到位，支持一个

发表于 2022-02-17 22:00:00

0 0

小洁癖

遇到这种题把图画出来之后记得要化简展开一下，别偷这个懒，，

发表于 2018-10-13 10:53:07

0 0

资深90后

哪位大神可以解答下

发表于 2018-10-13 10:52:59

0 0

小茉莉

拓扑序列算法思想

(1)从有向图中选取一个没有前驱(即入度为0)的顶点，并输出之;

(2)从有向图中删去此顶点以及所有以它为尾的弧;

重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止。

发表于 2018-10-13 10:52:49

0 0

问题信息

分类：数据结构 - 图的遍历

难度:

最新校招难题刷题，快来进刷题群吧