资源描述：
《AOV拓扑排序.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、1.AOV网的定义——ActivityOnVertexNetworki.用顶点表示活动，用弧表示活动间的优先关系的有向图，称为顶点表示活动的网。ii.AOV网中不能有回路2.拓扑排序：i.假设G=(V，E)是一个具有n个顶点的有向图，V中顶点序列vl，v2，…，vn称做一个拓扑序列(TopologicalOrder)，当且仅当该顶点序列满足下列条件：若在有向图G中存在从顶点vi到vj的一条路径，则在顶点序列中顶点vi必须排在顶点vj之前。通常，在AOV网中，将所有活动排列成一个拓扑序列的过程叫做拓
2、扑排序(TopologicalSort)。由于AOV网中有些活动之间没有次序要求，它们在拓扑序列的位置可以是任意的，因此拓扑排序的结果不唯一。对图7-21进行拓扑排序，可得一个拓扑序列：C1，C2，C3，C4，C5，C8，C9，C7，C6也可得到另一个拓扑序列：C1，C2，C3，C8，C4，C5，C9，C7，C6还可以得到其它的拓扑序列。学生按照任何一个拓扑序列都可以完成所要求的全部课程学习。在AOV网中不应该出现有向环。因为环的存在意味着某项活动将以自己为先决条件，显然无法形成拓扑序列。判定网中
3、是否存在环的方法：对有向图构造其顶点的拓扑有序序列，若网中所有顶点都出现在它的拓扑有序序列中，则该AOV网中一定不存在环。2021/8/312拓扑排序算法前者说明AOV网中无回路，后者说明AOV网中存在回路。1.从AOV网中任选择一个没有前驱(即入度为0)的顶点；2.从AOV网中删除该顶点以及以该顶点为始点的所有边；3.重复上述过程，直到网中的所有顶点都被删除,或者网中还有顶点，但不存在入度为0的顶点。2021/8/3132021/8/314为了实现拓扑排序的算法,对于给定的有向图,采用邻接表作为
4、存储结构,为每个顶点设立一个链表,每个链表有一个表头结点,这些表头结点构成一个数组,表头结点中增加一个存放顶点入度的域count。即将邻接表定义中的VNode类型修改如下：typedefstruct//表头结点类型{Vertexdata;//顶点信息intindegree;//存放顶点入度ArcNode*firstarc;//指向第一条弧}VNode;入度为0的顶点即为没有前驱的顶点，删除以该顶点为尾的弧，可用以对应弧的弧头顶点的入度减1来实现。为了避免重复检测入度为0的顶点，可设一栈暂存所有入度
5、为0的顶点。voidtopsort(VNodeadj[],intn){inti,j;intstack[MAXV],top=0;//栈stack的指针为topArcNode*p;for(i=0;i0)//栈不为空{i=stack[top];top--;//顶点vi出栈printf(“％d”,i);//输出vip=adj[i].firstarc;//指向以vi为弧尾的
6、第一条弧while(p!=NULL){j=p->adjvex;//以vi为弧尾的弧的另一顶点vj2021/8/316while(p!=NULL){j=p->adjvex;//以vi为弧尾的弧的另一顶点vjadj[j].count--;//顶点vj的入度减1if(adj[j].count==0)//入度为0的相邻顶点入栈{top++;stack[top]=j;}p=p->nextarc;//指向以vi为弧尾的下一条弧}}}2021/8/317拓扑排序的过程1.下面（）方法可以判断出一个有向图中是否又
7、环A.广度优先遍历B.拓扑排序C.求最短路径D.求关键路径2.有向图G=(V,A),其中V={a,b,c,d,e},A={,,,,，},对该图进行拓扑排序，下列序列中一定不是拓扑排序的是（）A.AdcbeB.dabceC.abdceD.abcde2021/8/318
