数据结构第七章-图.ppt

2023/6/21,1,第7章 图,图是一种多对多的结构关系，每个元素可以有零个或多个直接前趋；零个或多个直接后继。,2,【重点掌握】：图的两种遍历方法：遍历的定义、深度优先搜索遍历和广度优先搜索遍历的算法；应用图的遍历算法判断图的连通性及求图的生成树；用Prim、Kruskal算法求图的最小生成树；用Dijkstra算法求解单源最短路径问题；用Floyd算法求所有顶点间的最短路径问题；利用AOV网进行拓扑排序；利用AOE网求关键路径问题；【掌 握】：掌握图的定义和术语；图的各种存储结构及其构造算法、在实际问题中的求解效率。,3,7.3 图的遍历,7.3 图的遍历：从图的某顶点出发，访问图中所有顶点，并且每个顶点仅访问一次。,图结构的遍历复杂性：（1）在图结构中，没有一个“自然”的首结点，图中的任意一个顶点都可以作为第一个被访问的结点（2）在非连通图中，从一个顶点出发，只能访问它所在的连通分量上的所有顶点，因此，还需考虑如何选取下一个出发点以访问图中的其余连通分量（3）在图结构中，如果有回路存在，那么一个顶点被访问后，有可能沿回路又回到该顶点，考虑如何避免重复访问（4）在图结构中，一个顶点可以和其他多个顶点邻接，当这样的顶点访问过后，考虑如何选取下一个要访问的顶点的问题,4,图的遍历方法有深度优先遍历和广度优先遍历两种。,深度优先搜索,方法：（1）从图的某一顶点V0出发，访问此顶点；（2）依次从V0的未被访问的邻接点出发，深度优先遍历图，直至图中所有和V0相通的顶点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问到。,5,若图的存储结构为邻接表，则访问邻接点的顺序不唯一，深度优先序列不是唯一的,V0,V1,V3,V4,V7,V2,V5,V6,求图G以V0为起点的的深度优先序列（设存储结构为邻接矩阵）,6,void DFS(Graph G,int v)/*从第v个顶点出发，递归地深度优先遍历图G*/*v是顶点在一维数组中的位置，假设G是非空图*/visitedv=1;Visit(v);/*访问第v个顶点*/for(w=FirstAdjVex(G,v);w;w=NextAdjVex(G,v,w)if(!visitedw)DFS(G,w);/*对v的尚未访问的邻接顶点w递归调用DFS*/,辅助数组：int visitedMax_Vertex_Num;访问标志数组,全局变量，初始时所有分量全为0，visitedv=1表示顶点v已被访问.,visited,深度优先遍历算法:,7.3 图的遍历,7,7.3 图的遍历,在邻接表存储结构上实现深度优先搜索:,void DFSTraverseAL(ALGraph G)/*深度优先遍历以邻接表存储的图G*/int i;for(i=0;iG.vexnum;+i)visitedi=0;/*标志数组初始化*/for(i=0;iG.vexnum;+i)if(!visitedi)DFSAL(G,i);/*Vi未访问过，从Vi开始DFS搜索*/,8,void DFSAL(ALGraph G,int i)/*从第v个顶点出发，递归地深度优先遍历图G*/*v是顶点的序号，假设G是用邻接表存储*/EdgeNode*p;int w;visitedi=1;Visit(i);/*访问第v个顶点*/for(p=G.verticesi.firstarc;p;p=p-nextarc)w=p-adjvex;/*w是v的邻接顶点的序号*/if(!visitedw)DFSAL(G,w);/*若w尚未访问,递归调用DFS*/*DFSAL*/,7.3 图的遍历,9,在遍历时，对图中每个顶点至多调用一次DFS函数，因为一旦某个顶点被标志成已被访问，就不再从它出发进行搜索。因此，遍历图的过程实质上是对每个顶点查找其邻接点的过程。其耗费的时间则取决于所采用的存储结构。用邻接矩阵做图的存储结构时，查找各个顶点的邻接点所需的时间为O(n2)，其中n为图中顶点数。当以邻接矩阵做存储结构时，深度优先搜索遍历图的时间复杂度为O(n2+n)。当以邻接表做图的存储结构时，找邻接点所需时间为O(e)，其中e为无向图中边的数或有向图中弧的数。因此，当以邻接表做存储结构时，深度优先搜索遍历图的时间复杂度为O(n+e)。,7.3 图的遍历,10,图中某顶点v出发：1）访问顶点v；2）访问v的所有未被访问的邻接点w1,w2,wk；3）依次从这些邻接点出发，访问它们的所有未被访问的邻接点;依此类推，直到图中所有访问过的顶点的邻接点都被访问；,广度优先遍历,7.3 图的遍历,11,V0,V1,V2,V3,V4,V7,V5,V6,若图的存储结构为邻接表，则访问邻接点的顺序不唯一，深度优先序列不是唯一的,求图G以V0为起点的的广度优先序列（设存储结构为邻接矩阵）,先被访问的顶点，其邻接点也要先被访问设一队列保存已访问的顶点,12,在邻接表存储结构上的广度优先搜索,V0,V1,V2,V3,V4,V7,V5,V6,V1,V2,V3,V0,V4,V7,V5,V6,7.3 图的遍历,13,void BFSTraverse(MGraph G)/*从v出发，广度优先遍历连通图G*/*使用辅助队列Q和访问标志数组visited*/for(v=0;vG.vexnum;+i)visitedv=0;InitQueue(Q,G.vexnum);/*初始化空的辅助队列Q*/for(v=0;vG.vexnum;+v)if(!visitedv)/*若v尚未访问*/visitedv=1;Visit(v);EnQueue(Q,v);while(!QueueEmpty_Sq(Q)DeQueue(Q,u);/*队头元素出队,并赋值给u*/*访问u所有未被访问的邻接点*/for(w=0;wG.vexnum;w+;)if(G.arcsu,w.adj/*while*/*BFSTraverse*/,7.3 图的遍历,14,第七 章 图,15,生成树,生成树：包含了无向图G所有顶点的极小连通子图。1）“极小”含义：一个有n个顶点的连通图的生成树有n-1条边，删除任何一条边，子图不再连通；在生成树中再加一条边必然形成回路。（生成树包含了图中的所有顶点，但只有足以构成生成树的n-1条边）2）一个图可以有许多棵不同的生成树；3）生成树中任意两个顶点间的路径是唯一的；4）含n个顶点n-1条边的图不一定是生成树。,7.4 最小的生成树,16,7.4 最小的生成树,生成树的含义：n个顶点的图最多可存在n(n-1)/2条边线路。求生成树是为了在网络中连通n个顶点而选择最少的边(n1)。例如：一个通信网络中，节点代表了路由器，为了使各路由器之间是连通的（数据可达），且不形成回路(数据回到发送方)，则需建立该网络的生成树。,17,求生成树的方法：利用遍历算法。从连通图中的任一顶点出发进行遍历时，除出发点外，其余顶点必须通过一条边才能到达，所以遍历过程中经历的边有n-1条，它和n个顶点组成了连通图的一棵生成树。由深度优先搜索得到的是深度优先生成树；由广度优先搜索得到的是广度优先生成树。,18,深度遍历：V0V1V3V4V7V2 V5V6,7.4 最小的生成树,19,广度遍历：V0 V1 V2 V3 V4 V7 V5 V6,7.4 最小的生成树,20,最小生成树的概念,由生成树的定义可知，无向连通图的生成树不是惟一的。问题的提出：设要在n个城市间建立通信联络网，顶点表示城市，权表示城市间建立通信线路所需花费代价。希望找到一棵生成树，它的每条边上的权值之和（即建立该通信网所需花费的总代价）最小最小代价生成树。,7.4 最小的生成树,21,最小生成树定义：对于一个网络，它的所有生成树中边权值最小的生成树称为最小生成树。问题分析：n个城市间建立通信网，如何在可能的线路中选择n-1条，能把所有城市（顶点）均连起来，且总耗费（各边权值之和）最小。即：如何在保证n点连通的前题下最节省经费?,22,1.Prim 法基本步骤 设连通网络G=V,E。集合U存放G的最小生成树中的顶点，集合T存放最小生成树之外的顶点。(1)从G中选择某一顶点u0出发，在与它关联的边中选择一个边权最小的边(u0,v);将顶点v加入最小生成树的顶点集合U，在集合T 中删除该顶点；(2)用顶点v到集合T中顶点的边权“更新”原集合U中顶点到集合T中顶点的最小边权；(3)从一个顶点在U中，而另一个顶点在T中的各条边中选择权值最小的边(u,v),把顶点v加入到集合U 中。(4)重复(2)、(3)，直到网络中的所有顶点都加入到生成树顶点集合U中为止。,构造最小生成树的Prim算法,7.4 最小的生成树,23,U=V1,7.4 最小的生成树,2.过程演示,24,7.4 最小的生成树,Prim 算法的时间复杂度为O(n2),25,7.4.3 构造最小生成树的Kruskal算法,1.基本思想：按网中权值递增的顺序构造最小生成树。2.基本步骤 1）设连通网G=(V,E)，令最小生成树初始状态是只有n个顶点而无边的非连通图T=(V,)，每个顶点自成一个连通分量；2）在E中选取代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中；否则，舍去此边，选取下一条代价最小的边；3）依此类推，直至T中所有顶点都在同一连通分量上为止。,7.4 最小的生成树,26,7.4 最小的生成树,3.过程演示,27,7.4 最小的生成树,Kruskal 算法的时间复杂度为O(ne)。,28,29,交通咨询系统、通讯网、计算机网络中经常要寻找两结点间最短路径。例如：交通咨询系统中：咨询A到B的最短路径；计算机网中如何发送E-mail才最节省费用（使E-mail由A到B沿最短路径传送）。设用带权的有向图表示一个交通运输网，图中：顶点表示城市 边表示城市间的交通联系 权表示此线路的长度或沿此线路运输所花的时间或费用等 这类问题归结为从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径最短路径。路径上的第一个顶点为源点，最后一个顶点为终点。,问题的提出:,7.5 最短路径,30,最短路径问题：如果从图中某一顶点(源点)到达另一顶点(终点)的路径可能不止一条，如何找到一条路径使沿此路径上各边上的权值总和达到最小。,31,从一个源点到其他各点的最短路径,1.问题的提法：给定一个带权有向图D与源点v，求从v到D中其它顶点的最短路径。,7.5 最短路径,2.迪杰斯特拉算法（Dijkstra）（1）基本思想 为求得这些最短路径，Dijkstra提出按路径长度的递增次序，逐步产生最短路径的算法。首先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依此类推，直到从顶点v到其它各顶点的最短路径全部求出为止。,32,依据算法的基本思想把V分成两组：（1）S：已求出最短路径的顶点的集合（2）V-S=T：尚未确定最短路径的顶点集合 将T中顶点按如下规则加入到S中：（1）按递增的次序产生最短路径：从源点V0到S中各顶点的最短路径长度都不大于从V0到T中任何顶点的最短路径长度;（2）待求的最短路径最多以已求出最短路径的顶点为中间点：从V0到某顶点的最短路径中，只将S中的顶点作为中间点,33,（2）Dijkstra 算法的基本步骤 设V0是源点，初使时令S=V0,T=其余顶点，T中顶点对应的距离值若存在，边权值为弧上的权值；若不存在，边权值为。1）从T中选取一个其距离值最小的顶点W，加入S；2）对T中顶点的距离值进行修改：先求出V0到Vi中间只经S中结点的最短路径；若加进W作中间顶点后从V0到Vi的距离值 比 不加W的路径要短，则修改此距离值；上述最短路径中长度最小者即为下一条长度最短的路径；将所求最短路径的终点加入S中；3）重复2）直到S中包含所有顶点，即S=V为止。,7.5 最短路径,34,1）图用带权邻接矩阵存储；2）引入一个辅助数组dist。它的每一个分量disti表示当前找到的从源点v0 到终点vi 的最短路径的长度 初始状态：若从源点v0 到顶点vi有边，则disti为该边上的权值；若从源点v0 到顶点vi 没有边，则disti为。3）数组path表示从V0到各终点的最短路径上，此顶点的前一顶点的序号；若从V0 到某终点无路径，则用-1 作为该结点前一顶点的序号4)数组s标识V0 到该结点的最短路径是否求出。0表示没求出，1表示已求出。,7.5 最短路径,(3)算法实现,35,7.5 最短路径,2,60,0,0,30,1,3,50,1,0,10,1,2,2,60,1,0,30,1,3,50,1,0,10,1,4,3,90,0,0,30,1,3,50,0,0,10,1,3,0,100,0,0,30,0,1,60,0,0,10,1,1,0,100,0,0,30,0,-1,0,0,10,0,0,P4,d4,S4,P3,d3,S3,P2,d2,S2,P1,d1,S1,顶点4,顶点3,顶点2,顶点1,选取点,01234,36,如何从表中读取源点0到终点的最短路径？以顶点4为例：(1)V0到顶点4的最短路径为60。(2)path4=2 path2=3 path3=0；反过来排列，得到路径0,3,2,4，即V0到顶点V4的最短路径。,7.5 最短路径,37,Dijkstra 算法的时间复杂度为O(n2),38,39,7.6.1 有向无环图的概念,1.有向无环图（directed acycline graph）：没有回路的有向图。含有公共子式的表达式 例如：表达式(a+b)*(a+b-e/f),流程图：工程流程、生产过程中工序流程、程序流程、课程的流程。常用的两种有向无环图是：AOV网，AOE网。,7.6 有向无环图及其应用,40,AOV网与拓扑排序,1.AOV网(Activity On Vertex network)用顶点表示活动，边表示活动的顺序关系的有向图称为AOV网。在AOV网中，若从顶点i到顶点j有一条有向路径。则顶点i是顶点j的前驱，j是i的后继。若是网中一条弧，则i是j的直接前驱，j是i的直接后继。在AOV网中，每一条弧表示了活动之间存在的制约关系。注：AOV网中不允许有回路，这意味着某项活动以自己为先决条件。例如：计算机专业的学生必须学习一系列的基本课和专业课。学生应按照怎样的顺序来学习呢？可以把这个问题看做一个大的工程，其活动就是学习每一门课程。,7.6 有向无环图及其应用,41,C1、C2是独立于其它课程的基础课，而另一些课程必须在学完作为它的基础课后才能开始，即有先行课。先行条件规定了课程之间的优先关系。,计算机专业的课程设置及其关系,7.6 有向无环图及其应用,42,顶点表示课程，弧表示前提条件活动。若课程i是课程j的先行课，则必然存在弧。由此得到如下AOV网：,在安排学习顺序时，必须保证在学习某门课前，已经学习了其先行课。,如何设置这些课程的学习顺序，才能无矛盾、顺利地完成学业？,7.6 有向无环图及其应用,43,2.拓扑排序 拓扑序列：有向图D的一个顶点序列称作一个拓扑序列，对于该序列中任两顶点v、u，若在D中v是u前趋，则在序列中v也是u前趋。拓扑排序：把AOV网络中各顶点按照它们相互之间的领先关系排列成一个线性序列的过程。,拓扑排序的应用：判断工程流程的是否合理.,利用拓扑排序检测AOV网中是否存在环：对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该AOV网必定不存在环。,7.6 有向无环图及其应用,44,3.拓扑排序算法（1）在AOV网中选一个没有前驱的顶点v并将其输出；（2）从网中删除顶点v和所有以v为尾的弧；（3）重复(1)、(2)，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止。,7.6 有向无环图及其应用,45,拓扑序列：C1,7.6 有向无环图及其应用,46,拓扑序列：C1，C2,拓扑序列：C1,7.6 有向无环图及其应用,47,拓扑序列：C1，C2,拓扑序列：C1，C2，C3,7.6 有向无环图及其应用,48,拓扑序列：C1，C2，C3,拓扑序列：C1，C2，C3，C9,7.6 有向无环图及其应用,49,拓扑序列：C1，C2，C3，C9,拓扑序列：C1，C2，C3，C9，C4,拓扑序列：C1，C2，C3，C9，C4，C5,拓扑序列：C1，C2，C3，C9，C4，C5，C7,拓扑序列：C1，C2，C3，C9，C4，C5，C7，C10，C6，C8，C11,一个AOV网的拓扑序列不是唯一的。,7.6 有向无环图及其应用,50,拓扑排序算法:（1）在AOV网中选一个没有前驱的顶点v并将其输出；（2）从网中删除顶点v和所有以v为尾的弧；（3）重复(1)、(2)，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止。,7.6 有向无环图及其应用,拓扑排序方法的另一种等价描述：（1）选择一入度为0顶点v，输出；（2）将v邻接到的顶点的入度减1；（3）重复(1)、(2)，直至全部顶点均已输出;或图中没有入度为0的顶点为止。,51,拓扑排序的数据结构：以邻接表存储有向图，并在顶点结点中增加该顶点的入度信息。算法：1）为方便查找入度为0的元素，将邻接表中所有入度为0的顶点进栈 2）栈非空时，输出栈顶元素Vj并退栈；3）在邻接表中查找Vj的直接后继Vk，把Vk的入度减1；若Vk的入度为0则进栈；重复上述操作直至栈空为止。若栈空时输出的顶点个数不是n，则有向图有环；否则，拓扑排序完毕。,52,7.6 有向无环图及其应用,53,输出序列：5,7.6 有向无环图及其应用,54,输出序列：5,7.6 有向无环图及其应用,55,输出序列：5,7.6 有向无环图及其应用,56,输出序列：5,7.6 有向无环图及其应用,57,输出序列：5,7.6 有向无环图及其应用,58,输出序列：5,7.6 有向无环图及其应用,59,输出序列：5 0,7.6 有向无环图及其应用,60,输出序列：5 0,7.6 有向无环图及其应用,61,输出序列：5 0,7.6 有向无环图及其应用,62,输出序列：5 0,7.6 有向无环图及其应用,63,输出序列：5 0,7.6 有向无环图及其应用,64,输出序列：5 0,7.6 有向无环图及其应用,65,输出序列：5 0,7.6 有向无环图及其应用,66,输出序列：5 0,7.6 有向无环图及其应用,67,输出序列：5 0 2,7.6 有向无环图及其应用,68,输出序列：5 0 2,7.6 有向无环图及其应用,69,输出序列：5 0 2,7.6 有向无环图及其应用,70,输出序列：5 0 2,7.6 有向无环图及其应用,71,输出序列：5 0 2,7.6 有向无环图及其应用,72,输出序列：5 0 2,7.6 有向无环图及其应用,73,输出序列：5 0 2 1,7.6 有向无环图及其应用,74,输出序列：5 0 2 1,7.6 有向无环图及其应用,75,输出序列：5 0 2 1 3,7.6 有向无环图及其应用,76,输出序列：5 0 2 1 3,7.6 有向无环图及其应用,77,输出序列：5 0 2 1 3,7.6 有向无环图及其应用,78,输出序列：5 0 2 1 3,7.6 有向无环图及其应用,79,输出序列：5 0 2 1 3 4,7.6 有向无环图及其应用,80,输出序列：5 0 2 1 3 4,7.6 有向无环图及其应用,81,拓扑排序算法分析:建邻接表：T(n)=O(n+e)搜索入度为0的顶点的时间：T(n)=O(n)拓扑排序：T(n)=O(n+e),7.6 有向无环图及其应用,82,7.7 AOE网和关键路径AOE网(Activity On Edges)如果在无有向环的带权有向图中,用有向边表示一个工程中的各项活动(Activity),用边上的权值表示活动的持续时间(Duration),用顶点表示事件(Event)，每个事件表示在它之前的活动已完成，在它之后的活动可以开始.这样的有向图叫做用边表示活动的网络，简称AOE网。AOE网在某些工程估算方面非常有用。用途1：计算完成整个工程至少需要多少时间(假设网络中没有环)?用途2：为缩短完成工程所需的时间,应当加快哪些活动?,7.6 有向无环图及其应用,83,顶点表示事件,边表示活动,事件Vj发生表示ak已结束,事件Vi发生表示活动ak可以开始,事件 V1表示整个工程开始事件 V6表示整个工程结束,7.6 有向无环图及其应用,84,说明：AOV网和AOE网，用都能表示工程各子工程的流程，一个用顶点表示活动，一个用边表示活动，但AOV网侧重表示活动的前后次序，AOE网除表示活动先后次序，还表示了活动的持续时间等，因此可利用AOE网解决工程所需最短时间及哪些子工程拖延会影响整个工程按时完成等问题。实际应用中采用那一种图，取决于要求解的问题。,AOE网具有两个性质:(1)只有在某顶点所代表的事件发生之后，从该顶点出发的弧所代表的活动才能开始;(2)只有在进入一个顶点的各弧所代表的活动都已经结束，该顶点所代表的事件才能发生。,7.6 有向无环图及其应用,85,2.关键路径(Critical Path)在AOE网中,有些活动顺序进行，有些活动并行进行。整个工程结束的条件：从源点到终点的有向路径可能不止一条，其长度也不尽相同，但只有各条路径上所有活动都完成了，整个工程才算完成。关键路径：完成整个工程所需的时间取决于从源点到终点的最长路径长度（该路径上所有活动的持续时间之和）。这条路径长度最长的路径就叫做关键路径。,7.6 有向无环图及其应用,86,关键路径长度是整个工程所需的最短工期,即要缩短整个工期，必须加快关键活动的进度。,87,3.关键路径的确定,设活动ai用弧表示，其持续时间记为：dut()。,(1)事件Vk 的最早可能开始时间Vek 是从源点V0 到顶点Vk的最长路径长度。决定了所有从顶点发出的弧所代表的活动能够开工的最早时间.根据AOE网的性质，只有进入VK的所有活动（1jn-1)都结束时,Vk代表的事件才能发生。计算Vk的的最早可能开始时间方法如下:,从Ve1=0开始递推，Vek=Maxvej+dut(),7.6 有向无环图及其应用,88,(2)事件Vk的最迟允许开始时间Vlk 是在保证终点Vn-1 在Ven-1 时刻完成的前提下(即不拖延工期)，事件Vk的允许的最迟开始时间。,从Vln=Ven开始递推，Vlk=Minvlj dut(),设弧代表从Vk出发的活动，为了不拖延工期，Vk发生的最迟时间必须保证不推迟从事件Vk出发的所有活动的终点Vj(2jn)的最迟时间,7.6 有向无环图及其应用,89,(3)活动ai的最早可能开始时间 ei 设活动 ai 由弧表示，根据AOE网的性质，只有事件Vk发生了，活动ai才能开始。也就是说，活动ai的最早开始时间等于是vk的最早发生时间。因此,ek=Vei。,(4)活动 ai的最迟开始时间li li是在不会引起时间延误的前提下，该活动允许的最迟开始时间。设活动ai 由弧表示，根据AOE网的性质，ai的最迟开始时间要保证时间vj的最迟发生时间不拖后。li=Vlj-dut(),(5)关键活动 活动ai的时间余量 为li-ei（最迟可能开始时间和最早允许开始时间的差）。定义li=ei的活动是没有时间余量的关键活动。,7.6 有向无环图及其应用,90,求关键路径步骤求Ve(i)求Vl(j)求e(i)求l(i)计算l(i)-e(i),V1V2V3V4V5V6V7V8V9,064577161418,0668710161418,a1a2a3a4a5a6a7a8a9a10a11,7.6 有向无环图及其应用,91,注意：网络中各项活动是互相牵涉的，影响关键活动的因素是多方面的，任何一项活动持续时间的改变都可能影响关键路径的改变。关键活动的速度是有限的，只有在不改变网络关键路径的情况下，提高关键活动的速度才有效。,92,算法实现以邻接表作存储结构从源点V1出发，令Ve1=0，按拓扑序列求各顶点的Vei从汇点Vn出发，令Vln=Ven，按逆拓扑序列求其余各顶点的Vli根据各顶点的Ve和Vl值，计算每条弧的ei和li,找出ei=li的关键活动,7.6 有向无环图及其应用,93,算法描述输入顶点和弧信息，建立其邻接表计算每个顶点的入度对其进行拓扑排序在拓扑排序过程中求顶点的Vei将得到的拓扑序列进栈按逆拓扑序列求顶点的Vli计算每条弧的ei和li,找出ei=li的关键活动,94,算法性能:在拓扑排序求Vei和逆拓扑有序求Vli时,所需时间为O(n+e),求各个活动的ek和lk时所需时间为O(e),总共花费时间仍然是O(n+e)。,7.6 有向无环图及其应用,95,本章小结图是一种多对多的数据结构，每个元素可以有零个或多个直接前趋；零个或多个直接后继。在图中存在两种关系：顶点之间的邻接关系和边与顶点间的关联关系。图的存储结构有邻接矩阵、邻接表、十字链表、邻接多重表等。无论哪一种存储结构都要存储图中的顶点和顶点间的关系。图的遍历方法有深度优先遍历和广度优先遍历两种，应用图的遍历可以判断图的连通性。,96,求生成树是为了在网络中连通n个顶点而选择最少的边（n1），应用图的遍历可以求图的生成树。求最小生成树是为了获得在网络中连通n个顶点的最低造价的方案，Prim算法的原理是每次向最小生成树中加顶点和边、Kruskal算法的原理是每次向最小生成树中加边。单源最短路径问题是在网络中求从某顶点出发到达其他各点的最短路径，Dijkstra算法可以有效解决该问题。每对顶点间的最短路径问题可以由Floyd算法解决。有向无环图包括AOV网和AOE网。利用AOV网可以进行拓扑排序，为项目中子任务分配可行进度安排。利用AOE网可求关键路径，估算完成项目的时间。,97,第七章 结束,98,考试题型,选择 待定判断填空 待定简答题编程题 110,99,题型示例,简答题：队列的状态变化由遍历序列恢复二叉树构造哈夫曼树画图的存储结构求连通网的最小生成树求单源最短路径求拓扑排序求关键路径编程题：关于单链表的运算,