Question

数据结构题,叙述对有环无向图求拓扑排序序列的步骤 (2)写出下图的4个不同的拓扑排序序列麻烦解答,

Answer 1

(1)

设对有向无环图G=,求得它的一个拓扑序列为S,

初始化S为空,然后每次从G中选取一个入度为0的点v,将v插入到S的尾部,再在G中删除点v,并删除所有以v为弧尾的边(即由v引出去的边),如此循环,直到图G中的V为空集时结束.

2

1 2 3 4 5 6 7 8

1 3 2 4 5 7 6 8

3 1 4 2 5 6 7 8

3 1 2 5 4 7 8 6