拓扑排序(Topological Sort)
对一个 有向无环图 (Directed Acyclic Graph简称 DAG )G进行拓扑排序是将G中所有顶点排成一个线性序列使得图中任
意一对顶点u和v若 ∈E(G)则u在线性序列中出现在v之前
通常这样的线性序列称为满足拓扑次序(TopoiSicai Order)的序列简称 拓扑序列
注意
①若将图中顶点按拓扑次序排成一行则图中所有的有向边均是从左指向右的
②若图中存在有向环则不可能使顶点满足拓扑次序
③一个DAG的拓扑序列通常表示某种方案切实可行
【例】一本书的作者将书本中的各章节学习作为顶点各章节的先学后修关系作为边构成一个有向图按有向图的拓扑次序安
排章节才能保证读者在学习某章节时其预备知识已在前面的章节里介绍过
④一个DAG可能有多个拓扑序列
【例】对图G 进行拓扑排序至少可得到如下的两个(实际远不止两个)拓扑序列C C C C C C C
C C 和C C C C C C C C C
⑤当有向图中存在有向环时拓扑序列不存在
【例】下面(a)图中的有向环重排后如(b)所示有向边和其它边反向若有向图被用来表示某项工程实施方案或某项
工作计划则找不到该图的拓扑序列(即含有向环)就意味着该方案或计划是不可行的
无前趋的顶点优先的拓扑排序方法
该方法的每一步总是输出当前无前趋(即人度为零)的顶点其抽象算法可描述为
NonPreFirstTopSort(G){//优先输出无前趋的顶点
while(G中有人度为的顶点)do{
从G中选择一个人度为的顶点v且输出之;
从G中删去v及其所有出边;
}
if(输出的顶点数目<|V(G)|)
//若此条件不成立则表示所有顶点均已输出排序成功
Error(G中存在有向环排序失败!);
}
对G执行上述算法的执行过程和得到的拓扑序列是C C C C C C C C C
注意
无前趋的顶点优先的拓扑排序算法在具体存储结构下为便于考察每个顶点的人度可保存各顶点当前的人度为避免每次选入
度为的顶点时扫描整个存储空间可设一个栈或队列暂存所有入度为零的顶点
在开始排序前扫描对应的存储空间将人度为零的顶点均入栈(队)以后每次选人度为零的顶点时只需做出栈(队)操作即可
无后继的顶点优先拓扑排序方法
思想方法
该方法的每一步均是输出当前无后继(即出度为)的顶点对于一个DAG按此方法输出的序列是 逆拓扑次序 因此设置一个
栈(或向量)T来保存输出的顶点序列即可得到拓扑序列若T是栈则每当输出顶点时只需做人栈操作排序完成时将栈中顶点依
次出栈即可得拓扑序列若T是向量则将输出的顶点从T[n]开始依次从后往前存放即可保证T中存储的顶点是拓扑序列
抽象算法描述
算法的抽象描述为
NonSuccFirstTopSort(G){//优先输出无后继的顶点
while(G中有出度为的顶点)do {
从G中选一出度为的顶点v且输出v;
从G中删去v及v的所有人边
}
if(输出的顶点数目<|V(G)|)
Error(G中存在有向环排序失败!);
}
算法求精
在对该算法求精时可用逆邻接表作为G的存储结构设置一个向量outdegree[n]或在逆邻接表的顶点表结点中增加个出
度域来保存各顶点当前的出度;设置一个栈或队列来暂存所有出度为零的顶点除了增加一个栈或向量T来保存输出的顶点序列外
该算法完全类似于NonPreFirstTopSort具体算法【参见练习】
利用深度优先遍历对DAG拓扑排序
当从某顶点v出发的DFS搜索完成时v的所有后继必定均已被访问过(想像它们均已被删除)此时的v相当于是无后继的顶点因
此在DFS算法返回之前输出顶点v即可得到 DAG的逆拓扑序列
其中第一个输出的顶点必是无后继(出度为)的顶点它应是拓扑序列的最后一个顶点若希望得到的不是逆拓扑序列同样可增
加T来保存输出的顶点若假设T是栈并在DFSTraverse算法的开始处将T初始化
利用DFS求拓扑序列的抽象算法可描述为
void DFSTopSort(GiT){
//在DisTraverse中调用此算法i是搜索的出发点T是栈
int j;
visited[i]=TRUE; //访问i
for(所有i的邻接点j)//即∈E(G)
if(!visited[j])
DFSTopSort(GjT);
//以上语句完全类似于DFS算法
Push(&Ti); //从i出发的搜索已完成输出i
}
只要将深度优先遍历算法DFSTraverse中对DFS的调用改为对DFSTopSort的调用即可求得拓扑序列T其具体算法不难从上述抽
象算法求精后得到
若G是一个DAG则用DFS遍历实现的拓扑排序与NonSuccFirstTopSort算法完全类似;但若C中存在有向环则前者不能正常工作
转载自：http://sjjp.tjuci.edu.cn/sjjg/DataStructure/DS/web/gailun/gailun1.1.1b.htm
