单选题 21.对图4—1进行拓扑排序,可以得到不同的拓扑序列的个数是( )。
【正确答案】 B
【答案解析】寻找拓扑排序的步骤:
(1)在有向图中选一个没有前驱的顶点并且输出。
(2)从图中删除该顶点和所有以它为尾的弧。重复上述两步,直至全部顶点均已输出。由于没有前驱的顶点可能不唯一,所以拓扑排序的结果也不唯一。 题中所给图有3个不同的拓扑排序序列,分别为:
1)a, b, c, e, d。
2)a, b, e, c, d。
3)a, e, b, c, d。