5图论算法1专题培训课件.ppt
《5图论算法1专题培训课件.ppt》由会员分享,可在线阅读,更多相关《5图论算法1专题培训课件.ppt(49页珍藏版)》请在咨信网上搜索。
1、图论图论-算法算法图的遍历图的遍历BFS(广搜广搜)DFS(深搜深搜)最小生成树最小生成树PrimKruskal最短路径最短路径Bellman-FordDijkstraFloyd-WarshallnBFS练习练习nDFS练习练习nPrim练习练习nKruskal练习练习nBellman-Ford练习练习nDijkstra练习练习nFloyd-Warshall练习练习图的遍历图的遍历n遍历要访问到图中的遍历要访问到图中的每一个每一个顶点。顶点。nBFS(Breadth-First Search)nDFS(Depth-First Search)BFS思想思想 遍历篇遍历篇n1.从图中某顶点从图中某
2、顶点v0出发,在访问了出发,在访问了v0之后,搜索之后,搜索v0的的(所有未被访问的所有未被访问的)邻接顶点邻接顶点v1.v2n2.依次从这些邻接顶点出发,广搜图中其它顶点,依次从这些邻接顶点出发,广搜图中其它顶点,直至图中所有已被访问的顶点的邻接顶点都被访问直至图中所有已被访问的顶点的邻接顶点都被访问到。到。n3.若此时图中还有未被访问到的顶点,则再选择其若此时图中还有未被访问到的顶点,则再选择其中之一作为中之一作为v0重复上述过程。直到图中所有顶点均重复上述过程。直到图中所有顶点均被访问到。被访问到。/搜索过程没有回溯,是一种牺牲空间换取时间的方搜索过程没有回溯,是一种牺牲空间换取时间的方
3、法。时间复杂度:法。时间复杂度:O(V+E)BFS程序基本结构程序基本结构定义一个队列定义一个队列;起始点加入队列起始点加入队列;while(队列不空队列不空)取出队头结点取出队头结点;若它是所求的目标状态若它是所求的目标状态,跳出循环跳出循环;否则,从它扩展出子结点否则,从它扩展出子结点,全都添加到队尾全都添加到队尾;若循环中找到目标若循环中找到目标,输出结果输出结果;否则输出无解否则输出无解;BFS示例:示例:DFS思想思想 遍历篇遍历篇n1.将图将图G中每个顶点标记为未被访问,选取一个顶点中每个顶点标记为未被访问,选取一个顶点v作为搜索起点,标记其为已访问作为搜索起点,标记其为已访问n2
4、.递归地深搜递归地深搜v的每个未被访问过的邻接顶点,直到的每个未被访问过的邻接顶点,直到从从v出发所有可达的顶点都已被访问过。出发所有可达的顶点都已被访问过。n3.若此时图中还有未被访问到的顶点,则再选择其若此时图中还有未被访问到的顶点,则再选择其中之一作为中之一作为v重复上述过程。直到图中所有顶点均被重复上述过程。直到图中所有顶点均被访问到。访问到。/时间复杂度:时间复杂度:O(V+E)DFS程序基本结构程序基本结构void DFS(int step)for(i=0;iMax_Elements;i+)if(子结点符合条件子结点符合条件)新子结点入栈;新子结点入栈;if(是目标结点是目标结点)
5、输出输出elseDFS(step+1);子结点出栈子结点出栈DFS示例示例最小生成树最小生成树(Minimum Spanning Tree)nG(V,E)是无向连通赋权图,是无向连通赋权图,G(V,E)是包含是包含G中所中所有顶点的树,且树中各边权总和最小,则有顶点的树,且树中各边权总和最小,则G是最小是最小生成树生成树(可能不唯一可能不唯一)n容易想到,用容易想到,用贪心贪心策略。策略。PrimKruskalPrim思想思想 最小生成树篇最小生成树篇1.从从V中任取一结点放入中任取一结点放入V;2.在所有的端点分别在在所有的端点分别在(V-V)和和V中的边中,选一条中的边中,选一条权最小的加
6、入权最小的加入E;3.将边将边E在在(V-V)中的顶点从中的顶点从V中取出放入中取出放入V;4.重复步骤重复步骤23,直到,直到V与与V相等为止。相等为止。/该算法步步为营,每步生成的结果均为最终结果的该算法步步为营,每步生成的结果均为最终结果的一部分。它每次从连接一部分。它每次从连接V与与(V-V)的边中选最小边,的边中选最小边,所选出的不一定是所有尚未选出的属于最小生成树所选出的不一定是所有尚未选出的属于最小生成树的边中的最小者。时间复杂度:的边中的最小者。时间复杂度:O(ElgV)Prime程序基本结构程序基本结构void Prim()int i,j,k,min,lowcostvex,c
7、losestvex;for(i=2;i=n;i+)lowcosti=c1i;/第第1个点到其他点的代价个点到其他点的代价closesti=1;/初始时,所有点的起点都是点初始时,所有点的起点都是点1 for(i=2;i=n;i+)min=maxcost;/maxcost一个很大的数一个很大的数for(j=2;j=n;j+)if(closestj&lowcostj0)min=lowcostj;/在在v中找到最小的代价点中找到最小的代价点kk=j;closestk=0;/k归入归入u中中for(j=2;j=n;j+)if(closestj&ckj0)lowcostj=ckj;/以以k点为起点进行新
8、一轮的代价计算点为起点进行新一轮的代价计算,更新更新lowcost和和closestclosestj=k;无向连通图无向连通图,初始时初始时u只包只包含含1个点,后一步步将个点,后一步步将v中中的点添加到的点添加到u中来。中来。用用closesti=0表示表示i点在点在u集合中集合中,lowcosti当前当前起点到起点到i点的最小代价点的最小代价cij 顶点顶点i到到j的权的权(i到到j无边,则令无边,则令cij=-1),共有共有n个顶点个顶点(该模板中,该模板中,顶点从顶点从1开始计开始计)Prim示例:示例:V V2 2V V0 0V V3 3V V5 5V V4 4V V1 1V V2
9、2V V0 0V V3 3V V5 5V V4 4V V1 11U=v0U=v0,v2U=v0,v2,v5U=v0,v2,v5,v3U=v0,v2,v5,v3,v1U=v0,v2,v5,v3,v1,v4V V3 3V V4 4V V1 141V V0 0V V2 2V V5 5V V4 4V V1 1214V V0 0V V2 2V V5 5V V3 3V V4 41425V V2 2V V0 0V V5 5V V1 1V V3 335124V V2 2V V1 1V V0 0V V5 5V V3 3V V4 4Kruskal思想:思想:最小生成树篇最小生成树篇1.将边按边树由小到大排序。将边
10、按边树由小到大排序。2.每次加最小边每次加最小边&不构成回路。不构成回路。3.加进了加进了n-1条边就得到了最小生成树条边就得到了最小生成树/Kruskal算法并不保证每步生成的结果是连通的算法并不保证每步生成的结果是连通的(中间结果可能不是树)。(中间结果可能不是树)。Kruskal程序基本结构:程序基本结构:n优先队列优先队列+并查集并查集Kruscal 示例:示例:实例的执行过程实例的执行过程12435661655563421、初始连通分量:、初始连通分量:1,2,3,4,5,62、反复执行添加、放弃动作。、反复执行添加、放弃动作。条件:边数不等于条件:边数不等于 n-1时时 边边 动作
11、动作连通分量连通分量 (1,3)添加添加1,3,4,5,6,2 (4,6)添加添加1,3,4,6,2,5 (2,5)添加添加1,3,4,6,2,5 (3,6)添加添加1,3,4,6,2,5 (1,4)放弃放弃因构成回路因构成回路 (3,4)放弃放弃因构成回路因构成回路 (2,3)添加添加1,3,4,5,6,21243561534255算法实现要点:用并查集的相关操作:实现集合的并;判断新边的两端点是否处于同一集合,来确定是否构成回路。最短路径最短路径最短路径最短路径 (Shortest Path):(Shortest Path):n n最短路径问题:最短路径问题:如果从图中某一顶点如果从图中某
12、一顶点(称为源点称为源点)到达另一顶点到达另一顶点(称为终点称为终点)的路径可能不止一条,的路径可能不止一条,如何找到一条路径使得沿此路径上各边上的权值如何找到一条路径使得沿此路径上各边上的权值总和达到最小。总和达到最小。n n 边上边上权值非负权值非负情形的情形的单源单源最短路径问题最短路径问题 Dijkstra算法算法边上边上权值为任意值权值为任意值的的单源单源最短路径问题最短路径问题 Bellman-Ford算法算法所有顶点之间所有顶点之间的最短路径的最短路径 Floyd算法算法Dijkstra思想:思想:最短路径篇最短路径篇 初始化:初始化:S S v v0 0;distdist j
13、j EdgeEdge00j j,j j=1,2,=1,2,n n-1;1;1 1、求出最短路径的长度:、求出最短路径的长度:distdist k k min min distdist i i,i i V V-S S;S S S S U U k k ;2 2、修改:修改:distdist i i min min distdist i i,distdist k k+EdgeEdge k k i i,for ,for i i V V-S S;3 3、判断:判断:若若S=VS=V,则算法结束,否则转则算法结束,否则转1 1。n n引入一个辅助数组引入一个辅助数组distdist。distdist i
14、i 表示当前从源点表示当前从源点v v0 0到终点到终点v vi i 的最短路径的最短路径的长度。时间复杂度的长度。时间复杂度:O(V:O(V2 2)Dijkstra程序基本结构:程序基本结构:nvoid disktra(int v)/原点是原点是v nbool smaxn;register int i,j,k;nfor(i=1;i=n;i+)ndisti=cvi;nsi=0;/i不在集合不在集合S中中nif(disti=manint)/v to i没有边没有边nprevi=0;nelsenprevi=v;nnsv=1;distv=0;nfor(i=1;in;i+)nint temp=mani
15、nt,u=v;nfor(j=1;j=n;j+)nif(!sj&distj&distjtemp)nu=j;ntemp=distj;nnsu=1;nfor(j=1;j=n;j+)nif(!sj&cujmanint)nint newdist=distu+cuj;nif(newdist distj)ndistj=newdist;nprevj=u;nnnn结点从结点从1开始计,开始计,maxn为最大结点数为最大结点数,n为结点数,为结点数,manint是无穷大是无穷大,cij i到到j的的权,权,pre记录父结点记录父结点,disti源点到源点到i的最短的最短路径,路径,s表示左边的集合表示左边的集合c
16、onst int maxn=101,manint=99999999;int cmaxnmaxn,prevmaxn,distmaxn,n;DijkstraDijkstra逐步求解的过程逐步求解的过程逐步求解的过程逐步求解的过程Bellman-Ford思想:思想:最短路径篇最短路径篇n1.图中无负回路图中无负回路n2.最短路径长度数组序列最短路径长度数组序列 dist1u,distn-1u,其中其中distiu从从v到到u最多经过最多经过i条边条边n3.dist1u=Edgev,u distku=min distk-1u,min distk-1j+Edgej,u /时间复杂度:时间复杂度:O(VE
17、)Bellman-Ford程序基本结构:程序基本结构:nvoid Bellman-Ford()nint i;nfor(i=1;i=n;i+)ndi=manint;npari=0;nnds=0;nfor(i=1;idu+w(u,v)ndv=du+w(u,v);nparv=u;nnnfor each edge(u,v)nif(dvdu+w(u,v)nreturn false;nreturn true;ns为起点,为起点,di是是s到到i的最短路的最短路径长度,径长度,pari记录记录i结点的父结点的父节点节点.如果不存在从如果不存在从s可达可达的负权环,返回的负权环,返回true.Floyd-Wa
18、rshall思想:思想:最短路径篇最短路径篇n定定义义一一个个nn的的方方阵阵序序列列 A0,A1,An,其其中中Aki-1j-1表表示示从从vi到到vj允允许许k个个顶顶点点v0,v1,vk-1为为中中间间顶顶点点的的最最短短路路径径长长度度(A0 是是图图的的邻邻接接矩矩阵阵)。A0ij表表示示从从vi到到vj不不经经过过任任何何中中间间顶顶点点的的最最短短路路径径长长度度。Anij就是从就是从vi到到vj的最短路径长度。的最短路径长度。A0ij=arcsij0in-1,0jn-1Akij=minAk-1ij,Ak-1ik-1+Ak-1k-1j 1kn,加入第,加入第k个顶点个顶点vk-1
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 专题 培训 课件
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【w****g】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【w****g】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。