拓扑排序（有向无环图）

文章目录拓扑排序 核心拓扑排序的实现步骤拓扑排序算法实现逆拓朴排序逆拓朴排序的实现DFS算法AOV网用顶点表示活动的网用DAG图有向无环图表示一个工程。顶点表示活动有向边Vi,Vj表示活动Vi必须先于活动Vj进行。【即前驱必须先于后继】拓扑排序 核心每次删除入度为 0 的顶点并移除其所有出边。唯一性若拓扑排序序列不唯一则图中一定存在多个入度为 0的顶点。若在任何时刻都只有一个入度为 0的顶点则拓扑序列唯一。本质一个图能够进行拓扑排序当且仅当它是一个有向无环图DAG。若图中有环则环上的顶点入度永远不可能为 0算法无法输出全部顶点。拓扑排序的实现步骤从AOV网中选择一个没有前驱入度为0的顶点并输出从网中删除该顶点和所有以它为起点的有向边重复1.2.操作直到当前的**AOV网为空 **或当前网中不存在无前驱的顶点为止说明有回路。拓扑排序在图论中由一个有向无环图的顶点组成的序列当且仅当满足下列条件时称为该图的一个拓扑排序① 每个顶点出现且只出现一次。② 若顶点A在序列中排在顶点B的前面则在图中不存在从顶点B到顶点A的路径。(不是回路)或定义为拓扑排序是对有向无环图的顶点的一种排序它使得若存在一条从顶点A到顶点B的路径则在排序中顶点B出现在顶点A的后面。每个AOV网都有一个或多个拓扑排序序列。对有回路的图进行拓扑排序当前网中不存在无前驱的顶点为止拓扑排序算法实现时间复杂度O(|V||E|)若采用邻接矩阵则需O(|V|2)#defineMaxVertexNum100//图中顶点数目的最大值typedefstructArcNode{//边表结点intadjvex;//该弧所指向的顶点的位置structArcNode*nextarc;//指向下一条弧的指针//InfoType info; //网的边权值}ArcNode;typedefstructVNode{//顶点表结点VertexType data;//顶点信息ArcNode*firstarc;//指向第一条依附该顶点的弧的指针}VNode,AdjList[MaxVertexNum];typedefstruct{AdjList vertices;//邻接表intvexnum,arcnum;//图的顶点数和弧数}Graph;//Graph是以邻接表存储的图类型boolTopologicalSort(Graph G){InitStack(S);//初始化栈存储入度为0的顶点for(inti0;iG.vexnum;i)if(indegree[i]0)Push(S,i);//将所有入度为0的顶点进栈intcount0;//计数记录当前已经输出的顶点数while(!IsEmpty(S)){//栈不空则存在入度为0的顶点Pop(S,i);//栈顶元素出栈 每个顶点都需要处理一次print[count]i;//输出顶点ifor(pG.vertices[i].firstarc;p;pp-nextarc){//将所有i指向的顶点的入度减1并且将入度减为0的顶点压入栈Svp-adjvex;// 每条边都需要处理一次if(!(--indegree[v]))Push(S,v);//入度为0则入栈}}//whileif(countG.vexnum)returnfalse;//排序失败有向图中有回路elsereturntrue;//拓扑排序成功}逆拓朴排序对一个AOV网如果采用下列步骤进行排序则称之为逆拓扑排序① 从AOV网中选择一个没有后继出度为0的顶点并输出。② 从网中删除该顶点和所有以它为终点的有向边。③ 重复①和②直到当前的AOV网为空。逆拓朴排序的实现DFS算法voidDFSTraverse(Graph G){//对图G进行深度优先遍历for(v0;vG.vexnum;v)visited[v]FALSE;//初始化已访问标记数据for(v0;vG.vexnum;v)//本代码中是从v0开始遍历if(!visited[v])DFS(G,v);}voidDFS(Graph G,intv){//从顶点v出发深度优先遍历图Gvisited[v]TRUE;//设已访问标记for(wFirstNeighbor(G,v);w0;wNextNeighbor(G,v,w))if(!visited[w]){//w为u的尚未访问的邻接顶点DFS(G,w);}//ifprint(v);//输出顶点 DFS实现逆拓朴排序在顶点退栈前输出}总结AOV网一定是DAG图不能有环拓扑排序、逆拓朴排序序列可能不唯一若图中有环则不存在拓扑排序序列 / 逆拓朴排序序列。