6.6-7 有向无环图及应用

《6.6-7 有向无环图及应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、6.6拓扑排序——用顶点边表示活动的网络，简称AOV网络(ActivityOnVertices)顶点：一个工程中的活动(Activity)边：活动的顶点间的优先关系(Relation)要解决的问题是：将各个顶点（代表各个活动）排列成一个线性有序的序列，使得AOV网络中所有应存在的前驱和后继关系都能得到满足。课程代号课程名先修课程C1高等数学C2程序设计基础C3离散数学C1,C2C4数据结构C3,C2C5高级语言程序设计C2C6编译方法C5,C4C7操作系统C4,C9C8普通物理C1C9计算机原理C8可以用有向图表示一个工程。

2、在这种有向图中，用顶点表示活动。有向边表示：Vi必须先于活动Vj进行。这种有向图叫做顶点表示活动的AOV网络(ActivityOnVertices)。在AOV网络中，如果活动Vi必须在活动Vj之前进行，则存在有向边，AOV网络中不能出现有向回路，即有向环。在AOV网络中如果出现了有向环，则意味着某项活动应以自己作为先决条件。因此，对给定的AOV网络，必须先判断它是否存在有向环。一、什么是拓扑排序将各个顶点(代表各个活动)排列成一个线性有序的序列，使得AOV网络中所有应存在的前驱和后继关系都能得到满

3、足。这种构造AOV网络全部顶点的拓扑有序序列的运算就叫做拓扑排序。例如，对学生选课工程图进行拓扑排序，得到的拓扑有序序列为C1,C2,C3,C4,C5,C6,C8,C9,C7或C1,C8,C9,C2,C5,C3,C4,C7,C6例如，对学生选课工程图进行拓扑排序，得到的拓扑有序序列为C1,C2,C3,C4,C5,C6,C8,C9,C7或C1,C8,C9,C2,C5,C3,C4,C7,C6二、进行拓扑排序的方法首先建立（n个顶点的）AOV网。（1）在AOV网络中选一个没有直接前驱的顶点（入度为0的顶点）,并输出之;（2）从图中

4、删去该顶点,同时删去所有它发出的边；重复（1）和（2），直到全部顶点均已输出，拓扑有序序列形成，拓扑排序完成；若图中还有未输出的顶点，但已跳出处理循环。这说明图中存在环。v1v5v4v3v6三、拓扑排序的过程有向无环图v2v1v5v4v3v6v2(1)输出顶点v6(2)输出顶点v1(3)输出顶点v3(4)输出顶点v4(5)输出顶点v2(6)输出顶点v5v1v5v4v3v6三、拓扑排序的过程有向无环图v2v1v5v4v3v6v2(1)输出顶点v6(2)输出顶点v1(3)输出顶点v3(4)输出顶点v4(5)输出顶点v2(6)输出

5、顶点v5四、存储结构（邻接表）v1v2v3v4v5v612345602123043552054idvexfirstdataarcv1v5v4v3v6v22adjvexnextarctypedefstructarcnode{intadjvex;arcnode*nextarc;}*pointer;//表结点structnode{charvexdata;intid;//顶点的入度pointerfirstarc;}dig[100];//一组头结点在邻接表的头结点中增设了一个数据项id，记录该顶点的入度。入度为零的顶点即无前

6、驱的顶点。在拓扑排序算法中，使用一个存放入度为零的顶点的链式栈，供选择和输出无前驱的顶点。只要出现入度为零的顶点，就将它加入栈中。五、拓扑排序算法思想：(1)建立入度为零的顶点栈;(2)当入度为零的顶点栈不空时,重复执行：(2)-1从顶点栈中退出一个顶点,并输出之;(2)-2从AOV网络中删去这个顶点和它发出的边,边的终顶点入度减一;(2)-3如果边的终顶点入度减至0,则该顶点进入度为零的顶点栈;(3)如果输出顶点个数少于AOV网络的顶点个数,则报告网络中存在有向环。将顶点i进栈时，执行以下指针的修改：dig[i].id=t

7、op;top=i;//top指向新栈顶i,原栈顶元素放在id[i]中退栈操作可以写成：j=top;top=dig[top].id;//位于栈顶的顶点的位置记于j,top退到次栈顶六、拓扑排序的算法voidtoposort(){inistack(s);//置空栈for(i=1;i<=n;++i)if(dig[i].id==0)push(s.i);//入度为零的顶点栈count=0;//count为计数器,计输出顶点数while(!stackempty(s)){j=pop(s);printf(dig[j].vexdata);co

8、unt++;q=dig[j].firstarc;//q指示以vj为尾的第一条弧结点while(q){k=q->adjvex;//顶点vk为vj的直接后继dig[k].id--;if(dig[k].id==0)push(s,k);//新的入度为零的顶点入栈q=q->nextarc;}}if(