【例题讲解】拓扑序列求解过程
先序
拓扑序列的含义：是求有向无环图的拓扑序列的方法。
拓扑序列过程：在有向图中任取一个入度为0的顶点，然后将它的值存入拓扑序列中，最后将该顶点以及以该顶点为弧尾的弧全部删掉。随后重新任取一个入度为0的顶点重复上述过程，直到没有一个入度为0的顶点或者顶点全部被删除了结束。而被删掉的顶点的值构成的序列就是拓扑序列。
例题讲解
答案：
图中入度为0的顶点只有1，那么从1开始：
- 删除1和以它为弧尾的弧，此时入度为0的顶点为2。
- 删除2和以它为弧尾的弧，此时入度为0的顶点为5。
- 删除5和以它为弧尾的弧，此时入度为0的顶点为4
- 删除4和以它为弧尾的弧，此时入度为0的顶点为3和7
- 最后可以依次删掉3,7留下6或者依次删掉7,3,6，那么得到的拓扑排序就是1254376或者1254736
所以最后可能的拓扑排序就是:
1-2-5-4-3-7-6
1-2-5-4-7-3-6
先序 拓扑序列的含义：是求有向无环图的拓扑序列的方法。 拓扑序列过程：在有向图中任取一个入度为0的顶点，然后将它的值存入拓扑序列中，最后将该顶点以及以该顶点为弧尾的弧全部删掉。随后重新任取一个入度为0的顶点重复上述过程，直到没有一个入度为0的顶点或者顶点全部被删除了结束。而被删掉的顶点的值构成的序列就是拓扑序列。 例题讲解 答案： 图中入度为0的顶点只有1，那么从1开始： 删除1和以它为弧尾的弧，此时入度为0的顶点为2。 删除2和以它为弧尾的弧，此时入度为0的顶点为5。 删除5和以它为弧尾的弧，此时入度为0的顶点为4 删除4和以它为弧尾的弧，此时入度为0的顶点为3和7 最后可以依次删掉3,7留下6或者依次删掉7,3,6，那么得到的拓扑排序就是1254376或者1254736 所以最后可能的拓扑排序就是: 1-2-5-4-3-7-6 1-2-5-4-7-3-6