5-图论算法1.ppt

ACM/ICPC程序设计,简单算法,图论-算法,图的遍历BFS(广搜)DFS(深搜)最小生成树PrimKruskal最短路径Bellman-FordDijkstraFloyd-Warshall,BFS练习DFS练习Prim练习Kruskal练习Bellman-Ford练习Dijkstra练习Floyd-Warshall练习,图的遍历,遍历要访问到图中的每一个顶点。BFS(Breadth-FirstSearch)DFS(Depth-FirstSearch),BFS思想遍历篇,1.从图中某顶点v0出发，在访问了v0之后，搜索v0的(所有未被访问的)邻接顶点v1.v22.依次从这些邻接顶点出发，广搜图中其它顶点，直至图中所有已被访问的顶点的邻接顶点都被访问到。3.若此时图中还有未被访问到的顶点，则再选择其中之一作为v0重复上述过程。直到图中所有顶点均被访问到。/搜索过程没有回溯，是一种牺牲空间换取时间的方法。时间复杂度：O(V+E),BFS程序基本结构,定义一个队列;起始点加入队列;while(队列不空)取出队头结点;若它是所求的目标状态,跳出循环;否则，从它扩展出子结点,全都添加到队尾;若循环中找到目标,输出结果;否则输出无解;,BFS示例：,DFS思想遍历篇,1.将图G中每个顶点标记为未被访问，选取一个顶点v作为搜索起点，标记其为已访问2.递归地深搜v的每个未被访问过的邻接顶点，直到从v出发所有可达的顶点都已被访问过。3.若此时图中还有未被访问到的顶点，则再选择其中之一作为v重复上述过程。直到图中所有顶点均被访问到。/时间复杂度：O(V+E),DFS程序基本结构,voidDFS(intstep)for(i=0;iMax_Elements;i+)if(子结点符合条件)新子结点入栈；if(是目标结点)输出elseDFS(step+1);子结点出栈,DFS示例,最小生成树(MinimumSpanningTree),G(V,E)是无向连通赋权图，G(V,E)是包含G中所有顶点的树，且树中各边权总和最小，则G是最小生成树(可能不唯一)容易想到，用贪心策略。PrimKruskal,Prim思想最小生成树篇,1.从V中任取一结点放入V；2.在所有的端点分别在(V-V)和V中的边中，选一条权最小的加入E；3.将边E在(V-V)中的顶点从V中取出放入V；4.重复步骤23，直到V与V相等为止。/该算法步步为营，每步生成的结果均为最终结果的一部分。它每次从连接V与(V-V)的边中选最小边，所选出的不一定是所有尚未选出的属于最小生成树的边中的最小者。时间复杂度：O(ElgV),Prime程序基本结构,voidPrim()inti,j,k,min,lowcostvex,closestvex;for(i=2;i0)min=lowcostj;/在v中找到最小的代价点kk=j;closestk=0;/k归入u中for(j=2;j0)lowcostj=ckj;/以k点为起点进行新一轮的代价计算,更新lowcost和closestclosestj=k;,Prim示例：,U=v0,U=v0,v2,U=v0,v2,v5,U=v0,v2,v5,v3,U=v0,v2,v5,v3,v1,U=v0,v2,v5,v3,v1,v4,Kruskal思想：最小生成树篇,1.将边按边树由小到大排序。2.每次加最小边distjEdge0j,j=1,2,n-1;1、求出最短路径的长度：distkmindisti,iV-S;SSUk;2、修改：distimindisti,distk+Edgeki,foriV-S;3、判断：若S=V,则算法结束，否则转1。引入一个辅助数组dist。disti表示当前从源点v0到终点vi的最短路径的长度。时间复杂度:O(V2),Dijkstra程序基本结构：,voiddisktra(intv)/原点是vboolsmaxn;registerinti,j,k;for(i=1;i=n;i+)disti=cvi;si=0;/i不在集合S中if(disti=manint)/vtoi没有边previ=0;elseprevi=v;sv=1;distv=0;for(i=1;ic1)break;cind1c2d2;/输入起点、终点。for(inti=0;in,#include#include#includeusingnamespacestd;#defineMin(a,b)(a)(b)?(b):(a)#defineMax(a,b)(a)(b)?(a):(b)doubled201201;,Prim:,doublelowcost200,min,answer;memset(lowcost,0,sizeof(lowcost);answer=d01;for(i=1;in;i+)/与集合邻接的边长初始化，现在集合中只有一个点0lowcosti=d0i;/初始化lowcostanswer=Min(answer,d0i);/同时找出最短边for(i=1;in;i+)min=1000000;j=-1;for(k=1;kn;k+)if(lowcostk!=0,Prim:,lowcostj=0;/集合加进点jfor(k=1;kn;k+)/更新邻接点边权if(djkn/标准库的函数，对边进行从小到大排序,#include#include#include#includeusingnamespacestd;,Kruscal:,for(i=0;in;i+)/并查集的初始化，刚开始，每个点自成集合。si=i;for(i=0;iL;i+)/从最小边长的边开始，把边两端点所在集合合并起来Unite(edgei.e,edgei.s);if(Find(0)=Find(1)/当0与1处同一集合，当前所加边长就是所求break;printf(Scenario#%dn,T+);printf(FrogDistance=%.3lfnn,edgei.dis);return0;,Bellman-Ford:HomeWork,voidInitialize_Single_Source(ints)for(i=1;idu+wuv)dv=du+wuv;Pav=u;,Bellman-Ford:,boolBellman_Ford(ints)Initialize_Single_Source(s);for(i=1;idj+wjk)returnfalse;returntrue;,Dijkstra:pku2387,voidDijkstra(intn,intv)for(inti=1;i=n;i+)disti=cvi;si=false;if(disti=MAX)previ=0;elseprevi=v;distv=0;sv=true;for(i=1;itn;intx,y,len;for(i=1;ixylen;if(lencxy)cxy=cyx=len;Dijkstra(n,n);coutdist1(b)?(b):(a)intmain()intn,i,j,k,x201,y201,T=1;doubled201201;while(cinn,Floyd-Warshall,for(k=0;kn;k+)for(i=0;in;i+)if(i=k)continue;for(j=0;jn;j+)if(i=j|j=k)continue;dij=Min(dij,Max(dik,dkj);printf(Scenario#%dn,T+);printf(FrogDistance=%.3lfnn,d01);return0;,Floyd算法,相关题目：,图的遍历：BFS+DFSPKU:1348,2258,ZJU:1