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

19、为中间顶点。为中间顶点。n/时间复杂度时间复杂度O(n3)Floyd-Warshall程序基本结构：程序基本结构：for(k=0;kn;k+)for(k=0;kn;k+)for(i=0;in;i+)for(i=0;in;i+)for(j=0;jn;j+)for(j=0;jdik+dkj)if(dijdik+dkj)dij=dik+dkj;dij=dik+dkj;(dij=Min(dij,dik+dkj)dij=Min(dij,dik+dkj)Floyd示例：示例：n执行执行Floyd算法后算法后:0612 11 9410580714 960910 013 16 8722 01416 17 11

20、 10 8307123459851068776183Exercisen Practice makes perfect!n The more,the better!BFS：zoj(1091)n国际象棋棋盘上有一个马，要跳到指定目标，最少跳几步国际象棋棋盘上有一个马，要跳到指定目标，最少跳几步？a b c d e f g h12345678h8a1输入：a1 h8输出：To get from a1 to h8 takes 6 knight moves.跳马的规则跳马的规则 a b c d e f g h12345678在23的矩形里：BFS：a b c d e f g h123456780 332

21、 13 22 31 233 22 3332 33333332 33332例如：从a1到e4当目标出现在所扩展出的结点里，结果就找到了。To get from a1 to e4 takes 3 knight moves.BFS：int main()for(;)if(!(cinc1)break;cind1c2d2;/输入起点、终点。输入起点、终点。for(int i=0;i8;i+)for(int j=0;j8;j+)mij=0;/所有点都标记为所有点都标记为“没走没走”proc();return 0;#include#include using namespace std;int d82=1,2

22、,1,-2,2,-1,2,1,-1,2,-1,-2,-2,-1,-2,1;int m88;/给走过的点标记char c1,c2,d1,d2;void proc();void proc()int x,y,nx,ny,sx,sy,dx,dy,step=0;sx=c1-a;sy=d1-1;dx=c2-a;dy=d2-1;queue tq;tq.push(sx);tq.push(sy);tq.push(step);msxsy=1;while(!tq.empty()x=tq.front();tq.pop();y=tq.front();tq.pop();step=tq.front();tq.pop();i

23、f(x=dx&y=dy)break;for(int i=0;i8;i+)nx=x+di0;ny=y+di1;if(nx=8|ny=8|mnxny)continue;tq.push(nx);tq.push(ny);tq.push(step+1);mnxny=1;coutTo get from c1d1 to c2d2 takes step knight moves.endl;初始点入队取出队头元素新点加入队尾Knight Moves zoj(1091)程序实现程序实现双向双向BFS a b c d e f g h1234567802 1221 2122211112012n从起点、终点同时开始从起

24、点、终点同时开始双向BFS,有效地提高了时空效率。从起点找2步能跳到的点从终点找1步能跳到的点DFS：pku2258n给无向图，求此图中的最长路径。要求路不能重复给无向图，求此图中的最长路径。要求路不能重复走，但节点可以重复地到达。如走，但节点可以重复地到达。如输入输入输出？输出？n/best用来记录最长路径的长度，用来记录最长路径的长度，griji到到j的边长为的边长为1，以每一个结点为源点进行深搜，以每一个结点为源点进行深搜n#include#includenint gr2525,best,n,m;nvoid dfs(int p,int depth)/p为源点，为源点，depth为深度为深

25、度 nint i;nbool flag=true;nfor(i=0;ibest)nbest=depth;nreturn;nn main()int i,a,b;while(scanf(%d%d,&n,&m)!=EOF)if(n=0&m=0)break;best=0;memset(gr,0,sizeof(gr);for(i=0;im;i+)scanf(%d%d,&a,&b);grab=grba=1;for(i=0;in&n)for(i=0;ixiyi;for(j=0;ji;j+)dij=dji=sqrt(xi-xj)*(xi-xj)+(yi-yj)*(yi-yj);#include#include

26、#include using namespace std;#define Min(a,b)(a)(b)?(b):(a)#define Max(a,b)(a)(b)?(a):(b)double d201201;Prim:double lowcost200,min,answer;memset(lowcost,0,sizeof(lowcost);answer=d01;for(i=1;in;i+)/与集合邻接的边长初始化，现在集合中只有一个点与集合邻接的边长初始化，现在集合中只有一个点0 lowcosti=d0i;/初始化初始化lowcost answer=Min(answer,d0i);/同时找出最

27、短边同时找出最短边 for(i=1;in;i+)min=1000000;j=-1;for(k=1;kn;k+)if(lowcostk!=0&lowcostkmin)/找有最小边权的邻接点找有最小边权的邻接点 min=lowcostk;j=k;answer=Max(answer,min);if(j=1)/当集合加进了点当集合加进了点1，可以结束，可以结束 break;Prim:lowcostj=0;/集合加进点集合加进点j for(k=1;kn;k+)/更新邻接点边权更新邻接点边权 if(djklowcostk&lowcostk!=0)lowcostk=djk;printf(Scenario#%

28、dn,T+);printf(Frog Distance=%.3lfnn,answer);return 0;Kruscal:zju1942class Edge/边类，记录三个信息：端点、边长边类，记录三个信息：端点、边长public:int e,s;double dis;Edge()Edge(int a,int b,double c):e(a),s(b),dis(c)edge40000;/用一个数组保存边用一个数组保存边bool cmp(Edge e1,Edge e2)/排序时，需要比较边的长短排序时，需要比较边的长短 return e1.disn&n)L=0;for(i=0;ixiyi;for

29、(j=0;ji;j+)edgeL+=Edge(i,j,sqrt(xi-xj)*(xi-xj)+(yi-yj)*(yi-yj);sort(edge,edge+L,cmp);/标准库的函数，对边进行从小到大排序标准库的函数，对边进行从小到大排序#include#include#include#include using namespace std;Kruscal:for(i=0;in;i+)/并查集的初始化，刚开始，每个点自成集合。并查集的初始化，刚开始，每个点自成集合。si=i;for(i=0;iL;i+)/从最小边长的边开始，把边两端点所在集合合并起来从最小边长的边开始，把边两端点所在集合合并

30、起来 Unite(edgei.e,edgei.s);if(Find(0)=Find(1)/当当0与与1处同一集合，当前所加边长就是所求处同一集合，当前所加边长就是所求 break;printf(Scenario#%dn,T+);printf(Frog Distance=%.3lfnn,edgei.dis);return 0;Bellman-Ford:HomeWorknvoid Initialize_Single_Source(int s)nnfor(i=1;idu+wuv)nndv=du+wuv;nPav=u;nnIts to examine whether there exits negat

31、ive cycles in G,is exist-false;no exist-true#include#define MAX 100int i,j,k,n,s;int dMAX,PaMAX,wMAXMAX;/d is an upper bound on the weight of a shortest path from source s to v Bellman-Ford:nbool Bellman_Ford(int s)nnInitialize_Single_Source(s);nfor(i=1;in;i+)nnfor(j=1;j=n;j+)n for(k=1;k=n;k+)nif(wj

32、k!=65535)nRelax(j,k);nnfor(j=1;j=n;j+)n for(k=1;kdj+wjk)n return false;nreturn true;nint main()scanf(%d,&n);for(i=1;i=n;i+)for(j=1;j=n;j+)scanf(%d,&wij);scanf(%d,&s);/s=n;if(Bellman_Ford(s)printf(No negative cycles exits here.);else printf(There exits negative cycles!);printf(n);return 0;/*565535 6

33、65535 7 6553565535 65535 5 8-465535-2 65535 65535 6553565535 65535-3 65535 92 65535 7 65535 655351*/Dijkstra:pku2387nvoid Dijkstra(int n,int v)nnfor(int i=1;i=n;i+)nndisti=cvi;nsi=false;nif(disti=MAX)previ=0;nelse previ=v;nndistv=0;sv=true;nfor(i=1;in-1;i+)nnint temp=MAX;nint u=v;nfor(int j=1;j=n;j+

34、)nif(!sj)&(distjtemp)nnu=j;temp=distj;nnsu=true;nfor(j=1;j=n;j+)nif(!sj)&(cujMAX)nnint newdist=distu+cuj;nif(newdistdistj)nndistj=newdist;nprevj=u;nnnn#include#include#includeusing namespace std;const MAX=100002;int dist1001,c10011001,prev1001;bool s1001;Dijkstra:nint main()nnint n,t,i,j;ncintn;nint

35、 x,y,len;nfor(i=1;i=n;i+)nfor(j=1;j=n;j+)nnif(i=j)continue;ncij=MAX;nnfor(i=1;i=n;i+)cii=0;nfor(i=0;ixylen;nif(lencxy)ncxy=cyx=len;nnDijkstra(n,n);ncoutdist1endl;nreturn 0;nFloyd-Warshall:zju1942（青蛙）（青蛙）#include#include#include using namespace std;#define Max(a,b)(a)(b)?(a):(b)#define Min(a,b)(a)(b)

36、?(b):(a)int main()int n,i,j,k,x201,y201,T=1;double d201201;while(cinn&n)for(i=0;ixiyi;for(j=0;ji;j+)dij=dji=sqrt(xi-xj)*(xi-xj)+(yi-yj)*(yi-yj);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(Frog Distance=%.3lfnn,d01);return 0;Floyd算法相关题目：相关题目：n图的遍历：图的遍历：BFS+DFSnPKU:1348,2258,nZJU:1004,1204,1267,1457,1711,1984,1990,n最小生成树：最小生成树：Prim+KruskalnPKU:1251，2421,nZJU:1942,n最短路径：最短路径：Bellman-Ford+Dijkstra+FloydnPKU:1125,2387,nZJU：1221,1333,1589,1942,1952,