拓扑排序

 1.概述：

    拓扑排序就是将一个“有向无环图G“（左图所示，右图为有环的有向图）中的所有顶点排成一个线性序列，而这个线性序列就叫做是拓扑序列。

    更专业的说法就是：由某个集合上的一个偏序得到该集合上的一个全序的操作。

    而偏序和全序就是离散数学中的概念：

    1.偏序：设A是一个非空集，P是A上的一个关系，若关系P是自反的、反对称的、和传递的，则称P是集合A上的偏序关系。

    2.全序：在集合 A 中，存在偏序关系 R，如果对于任意 a∈A, b∈A, 有 aRb 或 bRa，即 A 中的每对元素都满足关系 R，则集合 A 上的偏序 R 是全序的或线性次序的。

 

    

 

2.注意点：

    1.如果图中存在着有向环，则不可能进行拓扑排序的：

       比如右图，v3，v6，v7三者之间的入度都等于1，没有一个的入度是0的，所以无法删除节点；

    2.一个有向无环图存在的拓扑排序可能有多种，不唯一：

       因为对于有向图中没有限定次序关系的顶点，是可以人为的加上任意次序的；

       比如左图，拓扑序列可能是v1→v2→v3→v4→v5→v6→v7→v8，也有可能是v1→v3→v2→v6→v7→v4→v5→v8；

 

 

3.实现：

    1.首先要找到任意入度为0的一个顶点，删除它及所有相邻的边，再找入度为0的顶点，以此类推，直到删除所有顶点。顶点的删除顺序即为拓扑排序。（入度为0来判断）

       总言而之，就是逐次去掉没有前驱的结点的过程。

    2.对有向无环图利用深度优先搜索（DFS）进行拓扑排序。（出度为0来判断，用栈）

       在访问完一个结点之后把它加到当前拓扑排序的首部，这里为什么是首部？

       是因为每次最先退出DFS的顶点应该是最后一个，就是出度为0的顶点，那就是拓扑排序的最后一个顶点，所以如果不放在首部的话，那么退出DFS先后记录下来的顶点序列就是逆向的拓扑排序序列了。

 

 

    

评论

3 楼 yomean 2013-08-09  

为什么觉得你说的偏序和全序的定义怪怪的。。

2 楼 Simone_chou 2013-08-08  

沙茶敏 写道

拓扑排序有个找关键路径  可以顺路学下~

我才刚发表的……

1 楼 沙茶敏 2013-08-08  

拓扑排序有个找关键路径  可以顺路学下~