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

题目

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

A.对

B.错

解答

正确答案是 B

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

C 2条回复评论

雪糕乐

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

发表于 2018-10-13 15:49:37

冬季恋歌

拓扑排序的基本思想：

1>从有向图中选一个无前驱的顶点输出

2>将此顶点和以它为起点的弧删除

3>重复(1),(2)，直到不存在无前驱的顶点

4>若此时输出的顶点数小于有向图中的顶点个数，这说明有向图中存在回路，否则输出的顶点顺序即为一个拓扑排序序列

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