第7章图_4x数据库.ppt

《第7章图_4x数据库.ppt》由会员分享，可在线阅读，更多相关《第7章图_4x数据库.ppt（40页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第7章图_4x数据库 第七章第七章 图图k=minimum(closedge);/求出加入生成树的下一个顶点求出加入生成树的下一个顶点(k)printf(closedgek.adjvex,G.vexsk);/输出生成树上一条边输出生成树上一条边 closedgek.lowcost=0;/第第k顶点并入顶点并入U集集 for(j=0;jG.vexnum;+j)/修改其它顶点的最小边修改其它顶点的最小边 if(G.arcskj.adj closedgej.lowcost)closedgej=G.vexsk,G.arcskj.adj;第七章第七章 图图 第七章第七章 图图 第七章第七章 图图 第七章

2、第七章 图图克鲁斯卡尔算法克鲁斯卡尔算法时间复杂度时间复杂度普里姆算法普里姆算法O(n2)O(eloge)稠密图稠密图稀疏图稀疏图算法名算法名适应范围适应范围比较两种算法 第七章第七章 图图7.5 7.5 有向无环图及应用有向无环图及应用7.5.1 7.5.1 拓扑排序拓扑排序 判断一个判断一个无向图无向图是否存在环：可深度优先遍历是否存在环：可深度优先遍历图，如果在遍历的过程中取到的邻接点是一个不是其图，如果在遍历的过程中取到的邻接点是一个不是其双亲的已访问过的顶点，则说明存在环。双亲的已访问过的顶点，则说明存在环。对于对于有向图有向图怎样来判断其是否存在环呢？可以怎样来判断其是否存在环呢？

3、可以用求拓扑排序来判断。用求拓扑排序来判断。例例V1V1V5V5V3V3V2V2V4V4G2G2例例G1G1V2V2V4V4V1V1V3V3 第七章第七章 图图有向图的一个拓扑序列有向图的一个拓扑序列：设有向图有：设有向图有n个顶点，个顶点，P1,P2,P3,Pn ;顶点的一个序列顶点的一个序列Pj1,Pj2,Pjn叫做叫做该图的拓扑序列，如果满足对于该图的拓扑序列，如果满足对于 1i ,k=n ,ik 有有Pji不是不是Pjk的后继，的后继，j1,j2,jn是是1，2，3，n的的一个排列。一个排列。例：例：A AB BC CD DE EF FA，F，D，C，B，EH，A，C，D，E，BA A

4、B BC CD DE EF F 第七章第七章 图图C1C2C3C4C5C6C7C8C9C10C11C12C1C1C2C2C3C3C4C4C5C5C6C6C7C7C8C8C9C9C10C10C11C11C12C12无无C1C1C1,C2C1,C2C1C1C3,C4C3,C4C11C11C3.C5C3.C5C3,C6C3,C6无无C9C9C9C9C1,C9,C10C1,C9,C10课程代号课程代号 课程名称课程名称 先修棵先修棵程序设计基础程序设计基础离散数学离散数学数据结构数据结构汇编语言汇编语言语言的设计和分析语言的设计和分析计算机原理计算机原理编译原理编译原理操作系统操作系统高等数学高等数学

5、线性代数线性代数普通物理普通物理数值分析数值分析拓扑序列拓扑序列:C1-C2-C3-C4-C5-C7-C9-C10-C11-C6-C12-C8:C1-C2-C3-C4-C5-C7-C9-C10-C11-C6-C12-C8或：或：C9-C10-C11-C6-C1-C12-C4-C2-C3-C5-C7-C8C9-C10-C11-C6-C1-C12-C4-C2-C3-C5-C7-C8 第七章第七章 图图 AOV AOV网：网：用顶点表示活动，用弧表示活动间优先关系用顶点表示活动，用弧表示活动间优先关系的有向图称为顶点表示活动的网的有向图称为顶点表示活动的网(Activity On Vertex(Ac

6、tivity On Vertex network)network)，简称，简称AOVAOV网。网。若若V 是图中有向边，则是图中有向边，则V Vi i是是V Vj j的直接前驱；的直接前驱；V Vj j是是V Vi i的直接后继。的直接后继。AOVAOV网中不允许有回路，若有回路，则这意味着某项活网中不允许有回路，若有回路，则这意味着某项活动以自己为先决条件。动以自己为先决条件。拓扑排序拓扑排序:求一个有向无环图的拓扑序列的过程叫拓求一个有向无环图的拓扑序列的过程叫拓扑排序。扑排序。第七章第七章 图图拓扑排序拓扑排序(求拓扑序列）的方法求拓扑序列）的方法:1.1.在有向图中选一个没有前驱的顶点

7、且输出在有向图中选一个没有前驱的顶点且输出2.2.从图中删除该顶点和所有以它为尾的弧。从图中删除该顶点和所有以它为尾的弧。3.3.重复上述两步，直至全部顶点均已输出；或者当图中重复上述两步，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止。（后一种情况则说明有向图不存在无前驱的顶点为止。（后一种情况则说明有向图中存在环）中存在环）头结点结构头结点结构data indegree firstarcadjvex info nextarc表结点结构表结点结构 第七章第七章 图图abcghdfeabhcdgfecabghdfe没有前驱的顶点：没有前驱的顶点：就是就是入度为零的顶点入度为零的顶点删除

8、顶点及以它为尾的弧删除顶点及以它为尾的弧 ：就是让弧头顶点的入度减就是让弧头顶点的入度减1 1 第七章第七章 图图adjvex info nextarc表结点结构表结点结构以邻接表作存储结构以邻接表作存储结构头结点结构头结点结构data indegree firstarc例：例：A AB BC CD DE EF FA 0B 2C 1D 2E 3F 0012345321 41443 第七章第七章 图图算法实现算法实现2.2.扫描表头向量，让所有入度为扫描表头向量，让所有入度为0 0的顶点进栈。的顶点进栈。3.3.输出点的计数器输出点的计数器count=0;count=0;1.1.初始化一个栈初始

9、化一个栈S S；4.while(4.while(栈栈S S不空不空)弹出栈顶元素弹出栈顶元素i i，并输出之，并使，并输出之，并使count+1count+1；在邻接；在邻接表中查找表中查找ViVi的直接后继的直接后继VkVk，把，把VkVk的入度减的入度减1 1；若；若VkVk的入的入度变为度变为0 0，则进栈。，则进栈。5.5.重复上述操作直至栈空为止。若栈空时输出的顶点个重复上述操作直至栈空为止。若栈空时输出的顶点个数不是数不是n n，则返回不存在拓扑序列即图有环的标志。否，则返回不存在拓扑序列即图有环的标志。否则，拓扑排序完毕，返回存存在拓扑序列则，拓扑排序完毕，返回存存在拓扑序列 第

10、七章第七章 图图例：例：A AB BC CD DE EF FA 0B 2C 1D 2E 3F 0012345321 41443 010S 05TopTopTop5 5出栈出栈S 0Top输出：输出：F210出栈出栈STopA03Top2Top2出栈出栈S3TopC11Top1出栈出栈S3TopB3出栈出栈STopD04Top4出栈出栈STopE 第七章第七章 图图Status Topological(ALGraph G)/有向图采用邻接表存储结构有向图采用邻接表存储结构/若若G无回路，则输出拓扑序列，并返回无回路，则输出拓扑序列，并返回OK，否则返回，否则返回ERRORInitStack(S)

11、;/初始化一个栈初始化一个栈for(i=0;inextarc)k=p-adivex;/删除弧，且使新入度为删除弧，且使新入度为0 0的顶点入栈的顶点入栈 if(!(-G.verticesk.indegree)Push(S,k);/for /whileIf(countG.vexnum)return ERROR else OK;/Topological 第七章第七章 图图7.5.2 7.5.2 关键路径关键路径问题提出问题提出:把工程计划表示为有向图，用顶点表示事件，弧表把工程计划表示为有向图，用顶点表示事件，弧表示活动；每个事件表示在它之前的活动已完成，在它之示活动；每个事件表示在它之前的活动已

12、完成，在它之后的活动可以开始后的活动可以开始.例例:设一个工程有设一个工程有1111项活动，项活动，9 9个事件个事件事件事件 V1 V1表示整个工程开始表示整个工程开始事件事件 V9 V9表示整个工程结束表示整个工程结束问题：（问题：（1 1）完成整项工程至少需要多少时间？）完成整项工程至少需要多少时间？（2 2）哪些活动是影响工程进度的关键。）哪些活动是影响工程进度的关键。第七章第七章 图图V9V8V7V6V4V5V3V2V1a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4图图7.29 7.29 一个一个AOE AOE 网网987645321a1

13、=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4 第七章第七章 图图定义：定义：AOEAOE网网(Activity On Edge)(Activity On Edge)：也叫边表示活动的网。：也叫边表示活动的网。AOEAOE网是一个带权的有向无环图，其中顶点表示事件，弧表网是一个带权的有向无环图，其中顶点表示事件，弧表示活动，权表示活动持续时间。示活动，权表示活动持续时间。路径长度：路径长度：路径上各活动持续时间之和路径上各活动持续时间之和关键路径：路径长度最长的路径叫关键路径：路径长度最长的路径叫 Ve(j)Ve(j)：表示事件表示事件VjVj的最早发

14、生时间的最早发生时间Vl(j)Vl(j)：表示事件表示事件VjVj的最迟发生时间的最迟发生时间e(i)e(i)：表示活动表示活动aiai的最早开始时间的最早开始时间l(i)l(i)：表示活动表示活动aiai的最迟开始时间的最迟开始时间l(i)-e(i)l(i)-e(i)：表示完成活动：表示完成活动aiai的时间余量的时间余量关键活动关键活动：关键路径上的活动叫关键路径上的活动叫，即，即l(i)=e(i)l(i)=e(i)的活动的活动 第七章第七章 图图 设活动设活动aiai用弧用弧表示，其持续时间记为：表示，其持续时间记为：dut()dut()则有：（则有：（1 1）e(i)=Ve(j)e(i

15、)=Ve(j)（2 2）l(i)=Vl(k)-dut()l(i)=Vl(k)-dut()jkai如何找如何找e(i)=l(i)e(i)=l(i)的关键活动？的关键活动？如何求如何求Ve(j)Ve(j)和和Vl(j)Vl(j)？(1)(1)从从Ve(1)=0Ve(1)=0开始向前递推开始向前递推其中其中T T是所有以是所有以j j为头的弧的集合为头的弧的集合(2)(2)从从Vl(n-1)=Ve(n-1)Vl(n-1)=Ve(n-1)开始向后递推开始向后递推其中其中S S是所有以是所有以i i为尾的弧的集合为尾的弧的集合 第七章第七章 图图求关键路径步骤v求Ve(i)v求Vl(j)v求e(i)v求

16、l(i)v计算l(i)-e(i)987645321a2=4a3=5a5=1a6=2a9=4a1=6a4=1a7=9a8=7a10=2a11=4V1V2V3V4V5V6V7V8V9顶点顶点 Ve Vl0645771614180668710161418a1a2a3a4a5a6a7a8a9a10a11活动活动 e l l-e 00002266046258377077071031616014140033 第七章第七章 图图算法实现算法实现:1.1.以邻接表作存储结构以邻接表作存储结构2.2.从源点从源点V1V1出发，令出发，令Ve1=0,Ve1=0,按拓扑序列求各顶按拓扑序列求各顶点的点的VeiVei

17、3.3.从汇点从汇点VnVn出发，令出发，令Vln=Ven,Vln=Ven,按逆拓扑序列按逆拓扑序列求其余各顶点的求其余各顶点的VliVli4.4.根据各顶点的根据各顶点的VeVe和和VlVl值，计算每条弧的值，计算每条弧的eiei和和li,li,找出找出ei=liei=li的关键活动的关键活动头结点结构头结点结构data indegree firstarcadjvex info nextarc表结点结构表结点结构 第七章第七章 图图算法描述算法描述v计算每个顶点的入度计算每个顶点的入度v对其进行拓扑排序对其进行拓扑排序l排序过程中求顶点的排序过程中求顶点的VeiVeil将得到的拓扑序列进栈将

18、得到的拓扑序列进栈v按逆拓扑序列求顶点的按逆拓扑序列求顶点的VliVliv计算每条弧的计算每条弧的eiei和和li,li,找出找出ei=liei=li的的关键活动关键活动V9V8V7V6V4V5V3V2V1a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4 第七章第七章 图图Status TopologicalSort(ALGraph G,Stack&T)/T/T为拓扑序列顶点栈为拓扑序列顶点栈/采用邻接表存储结构，求各顶点的最早发生时间采用邻接表存储结构，求各顶点的最早发生时间Ve若若G无回路，无回路，/则用则用T返回一个拓扑序列，并返回返回一个拓扑

19、序列，并返回OK，否则返回，否则返回ERRORfor(i=0;inextarc)k=p-adivex;/删除弧、使新入度为删除弧、使新入度为0 0的顶点入栈的顶点入栈 if(!(-G.verticesk.indegree)Push(S,k);/重新计算重新计算k k的的VeVe if(Vei+*(p-info)Vek Vek=Vei+*(p-info);/for /whileIf(countnextarc)k=p-adjvex;dut=*(p-info);/dut if(VljVlk-dut)Vlj=Vlk-dut;/forfor(j=0;jnextarc)k=p-adjvex;dut=*(p

20、-info);ee=Vej;el=Vlk-dut;求弧的求弧的e、l if(ee=el)printf(j,k,dut);/输出关键活动输出关键活动/CriticalPath 第七章第七章 图图012345678v1v2v3v4v5v6v7v8v901112112216 2435 694152 4177 74 810 84V9V8V7V6V4V5V3V2V1a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=7a9=4a10=2a11=4 第七章第七章 图图7.6 7.6 最短路径最短路径1.1.求从某个源点求从某个源点(V0)(V0)到其余各点的最短路径到其余各点的最短路径2.2.每

21、一对顶点之间的最短路径每一对顶点之间的最短路径V0V5V4V1V2V31003060102010550长度长度最短路径最短路径1010505030306060无无 第七章第七章 图图迪杰斯特拉迪杰斯特拉(Dijkstra)(Dijkstra)算法思想：算法思想：按路径长度递增次序产生最短路径算法按路径长度递增次序产生最短路径算法源点源点vj1Vjnvj2V0V5V4V1V2V31003060102010550 第七章第七章 图图 1.1.第一条路径长度最短的路径的特点第一条路径长度最短的路径的特点:在这条路径上，必定只含一条弧，并且这条弧的权值在这条路径上，必定只含一条弧，并且这条弧的权值最小

22、。最小。（设为（设为(v,vj)几个事实几个事实(紧紧围绕紧紧围绕路径长度递增）路径长度递增）：2.下一条路径长度次短的最短路径下一条路径长度次短的最短路径(vvk)的特点的特点:它只可能有两种情况它只可能有两种情况:或者是直接从源点到该点或者是直接从源点到该点(v,vk)；或者是，从源点经过顶点或者是，从源点经过顶点vj，再到达该顶点，再到达该顶点(v0,vj,vk);3.一般情况下，假设一般情况下，假设S为已求的最短路径的顶点的集为已求的最短路径的顶点的集合，则下一条最短路径（设其终点为合，则下一条最短路径（设其终点为x）或者是弧）或者是弧(v,x),或者是中间只经过或者是中间只经过S中的

23、顶点而最后到达顶点中的顶点而最后到达顶点x的路径。的路径。（用反证法）（用反证法）第七章第七章 图图顶点顶点从从v0到各顶点的到各顶点的D值和最短路径的求解过程值和最短路径的求解过程i=1i=2i=3i=4i=5v1v2v3v4v5vS 10 (v0,v2)30 (v0,v4)100 (v0,v4)v2v0,v2 50 (v0,v2,v3)30 (v0,v4)100 (v0,v4)v4v0,v2,v4 50 (v0,v4,v3)90 (v0,v4,v5)v3v0,v2,v4 v3 60 (v0,v4,v3,v5)v5v0,v2,v4 v3,v5无无V0V5V4V1V2V310030601020

24、10550 第七章第七章 图图求最短路径的迪杰斯特拉算法的实现：求最短路径的迪杰斯特拉算法的实现：1.1.用带权的邻接矩阵来表示带权有向图用带权的邻接矩阵来表示带权有向图G G（用数组表示（用数组表示法存储），法存储），G.arcijG.arcij表示弧表示弧(Vi,Vj)(Vi,Vj)的权值。若弧的权值。若弧(Vi,Vj)(Vi,Vj)不存在，则置不存在，则置G.arcijG.arcij为为 ,2.2.设置辅助数组设置辅助数组D D，其中每个分量，其中每个分量DiDi表示表示当前当前所求得所求得的从源点的从源点v v到其余各顶点到其余各顶点ViVi的最短路径。其初值为：的最短路径。其初值为：

25、Di=G.arcLocate(G,V)i Vi Di=G.arcLocate(G,V)i ViVV3.S3.S为已找到从为已找到从V V出发的最短路径的终点的集合，它的初出发的最短路径的终点的集合，它的初态为空集。用一全布尔数组态为空集。用一全布尔数组final0.G.vexnumfinal0.G.vexnum表示集表示集合合S S中的元素，如果中的元素，如果finaljfinalj为为TRUETRUE，说明编号为，说明编号为j j的顶的顶点在点在S S中。中。第七章第七章 图图4.4.重复第重复第2 2、3 3步步n-1n-1次，求得从源点到其余次，求得从源点到其余n-1n-1个顶点个顶点的

26、最短路径。的最短路径。算法：算法：1.1.初始化初始化D D和和S;S;2.2.选择路径长度最短的路径的终点选择路径长度最短的路径的终点v vj j即：即：Dj=minDi|vDj=minDi|vi i V-S V-S 将将vjvj加入到加入到S S中，即中，即S=SS=S jj3.3.修改从修改从v v出发到集合出发到集合V-SV-S上任一顶点上任一顶点vkvk可达的最短路可达的最短路径长度。径长度。即：如果即：如果Dj+G.arcjkDk Dj+G.arcjkDk 则修改为则修改为DkDk为为:Dk=Dj+G.arcjk Dk=Dj+G.arcjk 第七章第七章 图图v算法描述627543

27、185623013717329D0 1 2 3 4 5 60 13 8 30 32P0 1 2 3 4 5 60 1 1 0 1 0 1(1)k=11133122 20221941215111长度长度最短路径最短路径13813192120v算法分析：T(n)=O(n)第七章第七章 图图void ShortestPath(MGgraph G,int v0,PathMatrix&P,ShortPathTable&D)/P189算法算法7.15/用用Dijkstra算法求从顶点算法求从顶点v0到其余顶点的最短路径到其余顶点的最短路径Pv及其带权及其带权/长度，若长度，若Pvw为为TRUE，则说明，则

28、说明w在从在从v0到到v的最短路径上的的最短路径上的/顶点。顶点。for(v=0;vG.vexnum;v+)finalv=FALSE;/初始化初始化S、D Dv=G.arcv0v;for(w=0;wG.vexnum;w+)Pvw=FALSE;/设空路径设空路径if(DvINFINITY)Pvv0=Pvv=TRUE;/若存在弧（若存在弧（v0,v)，则初始路径为，则初始路径为v0,v/for 第七章第七章 图图for(i=0;iG.vexnum;i+)/最多循环最多循环n-1次次 min=INFINITY;for(w=0;wG.vexnum;w+)/求路径长度最短者求路径长度最短者 if(!fi

29、nalw)/w V-S if(Dwmin)v=w;min=Dw;if(min INFINITY)/v是找到的路径长度最短的顶点，若是找到的路径长度最短的顶点，若v存在存在 finalv=TRUE;/S=S v for(w=0;wG.vexnum;w+)/修改修改Dw和和Pw if(!finalw&(min+G.arcvwDw)Dw=min+G.arcvw;Pw=Pv;Pww=TRUE;/Pw=Pv w /if else break;/退出退出/for/ShortestPath 第七章第七章 图图V0V5V4V1V2V31003060102010550v0v1v2v3v4v5v0 v1 v2 v

30、3 v4v5 第七章第七章 图图2.2.每一对顶点之间的最短路径每一对顶点之间的最短路径解决方法：解决方法：1 1）用用DijkstraDijkstra方法，对每一个顶点调用算方法，对每一个顶点调用算法法7.157.15一次即可求出每一对顶点之间的最短路径。一次即可求出每一对顶点之间的最短路径。2 2）弗洛伊德算法：弗洛伊德算法：弗洛伊德算法其基本思想是：弗洛伊德算法其基本思想是：从从 vi vi 到到 vj vj 的所有可能存在的路径中，选出一条长的所有可能存在的路径中，选出一条长度最短的路径，度最短的路径，若若存在，则存在路径存在，则存在路径vi,vjvi,vj /路径中不含其它顶点路径中

31、不含其它顶点若若,存在，则存在路径存在，则存在路径vi,v1,vjvi,v1,vj /路径中所含顶点序号不大于路径中所含顶点序号不大于1 1 第七章第七章 图图若若vi,v2,v2,vjvi,v2,v2,vj存在，存在，则存在一条路径则存在一条路径vi,v2,vjvi,v2,vj /路径中所含顶点序号不大于路径中所含顶点序号不大于2 2 依次类推，则依次类推，则 vi vi 至至 vj vj 的最短路径应是上述这些路径的最短路径应是上述这些路径中，路径长度最小者。中，路径长度最小者。第七章第七章 图图本章小结：本章小结：1.熟悉图的各种存储结构及其构造算法，了解实际熟悉图的各种存储结构及其构造

32、算法，了解实际问题的求解效率与采用何种存储结构和算法有密切问题的求解效率与采用何种存储结构和算法有密切联系。联系。2.熟练掌握图的两种搜索路径的遍历：遍历的逻辑熟练掌握图的两种搜索路径的遍历：遍历的逻辑定义、深度优先搜索和广度优先搜索的算法。定义、深度优先搜索和广度优先搜索的算法。在学习中应注意图的遍历算法与树的遍历算法之在学习中应注意图的遍历算法与树的遍历算法之间的类似和差异。间的类似和差异。3.应用图的遍历算法求解各种简单路径问题。应用图的遍历算法求解各种简单路径问题。4.理解教科书中讨论的各种图的算法。理解教科书中讨论的各种图的算法。此此课件下件下载可自行可自行编辑修改，修改，仅供参考！供参考！感感谢您的支持，我您的支持，我们努力做得更好！努力做得更好！谢谢!