对图4—1进行拓扑排序，可以得到不同的拓扑序列的个数是( )。

admin2017-04-28 12

问题对图4—1进行拓扑排序，可以得到不同的拓扑序列的个数是( )。

选项 A、4
B、3
C、2
D、1

答案B

解析寻找拓扑排序的步骤：
(1)在有向图中选一个没有前驱的顶点并且输出。
(2)从图中删除该顶点和所有以它为尾的弧。重复上述两步，直至全部顶点均已输出。由于没有前驱的顶点可能不唯一，所以拓扑排序的结果也不唯一。
题中所给图有3个不同的拓扑排序序列，分别为：
1)a，b，  c，  e，  d。
2)a，b，  e，  c，  d。
3)a，  e，  b，  c，  d。

转载请注明原文地址:https://kaotiyun.com/show/1PRi777K

本试题收录于：计算机408题库学硕统考专业分类