|
无后继的顶点优先拓扑排序方法 思想方法 该方法的每一步均是输出当前无后继(即出度为)的顶点对于一个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中存在有向环则前者不能正常工作 |
