6.6-7 有向无环图及应用

6.6拓扑排序——用顶点边表示活动的网络，简称AOV网络(ActivityOnVertices)顶点：一个工程中的活动(Activity)边：活动的顶点间的优先关系(Relation)要解决的问题是：将各个顶点（代表各个活动）排列成一个线性有序的序列，使得AOV网络中所有应存在的前驱和后继关系都能得到满足。课程代号课程名先修课程C1高等数学C2程序设计基础C3离散数学C1,C2C4数据结构C3,C2C5高级语言程序设计C2C6编译方法C5,C4C7操作系统C4,C9C8普通物理C1C9计算机原理C8可以用有向图表示一个工程。在这种有向图中，用顶点表示活动。有向边Vi,Vj表示：Vi必须先于活动Vj进行。这种有向图叫做顶点表示活动的AOV网络(ActivityOnVertices)。在AOV网络中，如果活动Vi必须在活动Vj之前进行，则存在有向边Vi,Vj，AOV网络中不能出现有向回路，即有向环。在AOV网络中如果出现了有向环，则意味着某项活动应以自己作为先决条件。因此，对给定的AOV网络，必须先判断它是否存在有向环。一、什么是拓扑排序将各个顶点(代表各个活动)排列成一个线性有序的序列，使得AOV网络中所有应存在的前驱和后继关系都能得到满足。这种构造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）从图中删去该顶点,同时删去所有它发出的边；重复（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)输出顶点v5四、存储结构（邻接表）v1v2v3v4v5v612345602123043552054idvexfirstdataarcv1v5v4v3v6v22adjvexnextarctypedefstructarcnode{intadjvex;arcnode*nextarc;}*pointer;//表结点structnode{charvexdata;intid;//顶点的入度pointerfirstarc;}dig[100];//一组头结点在邻接表的头结点中增设了一个数据项id，记录该顶点的入度。入度为零的顶点即无前驱的顶点。在拓扑排序算法中，使用一个存放入度为零的顶点的链式栈，供选择和输出无前驱的顶点。只要出现入度为零的顶点，就将它加入栈中。五、拓扑排序算法思想：(1)建立入度为零的顶点栈;(2)当入度为零的顶点栈不空时,重复执行：(2)-1从顶点栈中退出一个顶点,并输出之;(2)-2从AOV网络中删去这个顶点和它发出的边,边的终顶点入度减一;(2)-3如果边的终顶点入度减至0,则该顶点进入度为零的顶点栈;(3)如果输出顶点个数少于AOV网络的顶点个数,则报告网络中存在有向环。将顶点i进栈时，执行以下指针的修改：dig[i].id=top;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);count++;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(countn)error(“该图中存在回路”)}分析此拓扑排序算法可知，如果AOV网络有n个顶点，e条边，在拓扑排序的过程中，搜索入度为零的顶点，建立链式栈所需要的时间是O(n)。在正常的情况下，有向图有n个顶点，每个顶点进一次栈，出一次栈，共输出n次。顶点入度减一的运算共执行了e次。所以总的时间复杂度为O(n+e)。6.7关键路径——用边表示活动的网络，简称AOE网络(ActivityOnEdges)边：一个工程中的活动(Activity)边上权值：活动持续时间(Duration)顶点：事件(Event)要解决的问题是：(1)完成整个工程至少需要多少时间(假设网络中没有环)?(2)为缩短完成工程所需的时间,应当加快哪些活动?完成整个工程所需的时间取决于从源点到汇点的最长路径长度，即在这条路径上所有活动的持续时间之和。这条路径长度最长的路径就叫做关键路径(CriticalPath)。定义几个与计算关键活动有关的量：（1）事件Vj的最早可能开始时间Ve(j)——从源点V1到顶点Vj的最长路径长度。（2）事件Vi的最迟允许开始时间Vl[i]——在保证汇点Vn在Ve[n]时刻完成的前提下，事件Vi的允许的最迟开始时间。Ve(1)=0Ve(j)=max{Ve(i)+i,j的权}Vl(n)=Ve(n)Vl(i)=min{Vl(j)-i,j的权}1324a1=8a2=65678a10=12a9=6a8=18a5=26a6=4a7=6a3=14a4=10VeVl12345678086222832465808142228404658关键路径：124578小结一、熟悉图的各种存储结构（了解实际问题与采取何种存储和算法有密切联系）；二、掌握遍历图的递归和非递归算法，并应用图的遍历算法求解各种简单路径问题；三、理解教科书中讨论的各种图的算法。四、掌握构造最小生成树的方法，求拓扑排序的方法，求解关键路径的方法，求解最短路径的Dijkstra方法。图是一种比树更复杂的、非线性的数据结构，一个图由顶点集合（是非空有限集合）和边集合（可以是空集合）组成。图的存储表示有邻接矩阵、邻接表、邻接多重表和十字链表等。以前两种最常用。图的邻接矩阵元素个数与顶点有关，非零元素个数与边有关；图的邻接表既与顶点个数n有关，又与边数有关。对图可以进行深度优先遍历和广度优先遍历。图有许多应用，采用prim算法、Kruskal算法、Floyd算法、Dijkstra算法、拓扑排序算法和求关键路径算法可以解决实际应用问题。