校招刷题群
高效刷题 迎战校招
校招精选试题
近年面笔经面经群内分享
Java刷题群 前端刷题群 产品运营群
首页 > 数据结构 > 图的属性
题目

有环图也能进行拓扑排序()

A.

B.

解答

正确答案是 B

拓扑排序将有向图中的顶点以线性方式进行排序。即对于任何连接自顶点u到顶点v的有向边uv,在最后的排序结果中,顶点u总是在顶点v的前面。一个有向图能被拓扑排序的充要条件就是它是一个有向无环图。

C 2条回复 评论
雪糕乐

有向无环图才能拓扑排序。

发表于 2018-10-13 15:49:37
0 0
冬季恋歌

拓扑排序的基本思想:
1>从有向图中选一个无前驱的顶点输出
2>将此顶点和以它为起点的弧删除
3>重复(1),(2),直到不存在无前驱的顶点
4>若此时输出的顶点数小于有向图中的顶点个数,这说明有向图中存在回路,否则输出的顶点顺序即为一个拓扑排序序列

发表于 2018-10-13 15:49:30
0 0