AOV拓扑排序.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,1.AOV,网的定义,Activity On Vertex Network,i.,用顶点表示活动，用弧表示活动间 的优先关系的有向图，称为顶点表 示活动的网。,ii.AOV,网中不能有回路,2.,拓扑排序：,i.,假设,G=(V，E),是一个具有,n,个顶点的有向图，,V,中顶点序列,v,l,，v,2,，,，v,n,称做一个拓扑序列(,Topological Order)，,当且仅当该顶点序列满足下列条件：若在有向图,G,中存在从顶点,v,i,到,v,j,的一条路径，则在顶点序列中顶点,v,i,必须排在顶点,v,j,之前。通常，在,AOV,网中，将所有活动排列成一个拓扑序列的过程叫做拓扑排序(,Topological Sort)。,由于,AOV,网中有些活动之间没有次序要求，它们在拓扑序列的位置可以是任意的，因此拓扑排序的结果不唯一。对图,7-2,1,进行拓扑排序，可得一个拓扑序列：,C1,，,C2,，,C3,，,C4,，,C5,，,C8,，,C9,，,C7,，,C6,也可得到另一个拓扑序列：,C1,，,C2,，,C3,，,C8,，,C4,，,C5,，,C9,，,C7,，,C6,还可以得到其它的拓扑序列。学生按照任何一个拓扑序列都可以完成所要求的全部课程学习。,在,AOV,网中不应该出现有向环。因为环的存在意味着某项活动将以自己为先决条件，显然无法形成拓扑序列。,判定网中是否存在环的方法：对有向图构造其顶点的拓扑有序序列，若网中所有顶点都出现在它的拓扑有序序列中，则该,AOV,网中一定不存在环。,2026/1/10 周六,2,拓扑排序算法,前者说明,AOV,网中无回路，,后者说明,AOV,网中存在回路。,1,.,从,AOV,网中任选择一个没有前驱,(,即入度为,0,),的顶点,；,2,.,从,AOV,网中,删除,该顶点以及以该顶点为始点的所有边；,3,.,重复上述过程，直到网中的所有顶点都被删除,或者,网中还有顶点，但不存在入度为,0,的顶点。,2026/1/10 周六,3,2026/1/10 周六,4,为了实现拓扑排序的算法,对于给定的有向图,采用邻接表作为存储结构,为每个顶点设立一个链表,每个链表有一个表头结点,这些表头结点构成一个数组,表头结点中增加一个存放顶点入度的域,count,。即将邻接表定义中的,VNode,类型修改如下：,typedef struct /,表头结点类型,Vertex data;/,顶点信息,int indegree;/,存放顶点入度,ArcNode*firstarc;/,指向第一条弧,VNode;,入度为,0,的顶点即为没有前驱的顶点，删除以该顶点为尾的弧，可用以对应弧的弧头顶点的入度减,1,来实现。,为了避免重复检测入度为,0,的顶点，可设一栈暂存所有入度为,0,的顶点。,void topsort(VNode adj,int n),int i,j;,int stackMAXV,top=0;/,栈,stack,的指针为,top,ArcNode*p;,for(i=0;i0)/,栈不为空,i=stacktop;,top-;/,顶点,v,i,出栈,printf(“,d”,i);/,输出,v,i,p=adji.firstarc;/,指向以,v,i,为弧尾的第一条弧,while(p!=NULL),j=p-adjvex;/,以,v,i,为弧尾的弧的另一顶点,v,j,2026/1/10 周六,6,while(p!=NULL),j=p-adjvex;/,以,v,i,为弧尾的弧的另一顶点,v,j,adjj.count-;/,顶点,v,j,的入度减,1,if(adjj.count=0)/,入度为,0,的相邻顶点入栈,top+;,stacktop=j;,p=p-nextarc;/,指向以,v,i,为弧尾的下一条弧,2026/1/10 周六,7,拓扑排序的过程,1.,下面（）方法可以判断出一个有向图中是否又环,A.,广度优先遍历,B.,拓扑排序,C.,求最短路径,D.,求关键路径,2.,有向图,G=(V,A),其中,V=a,b,c,d,e,A=,，,对该图进行拓扑排序，下列序列中一定不是拓扑排序的是（）,A.Adcbe B.dabce C.abdce D.abcde,2026/1/10 周六,8,