《图论算法干货分享》由会员分享，可在线阅读，更多相关《图论算法干货分享（53页珍藏版）》请在金锄头文库上搜索。
1、图论算法1图论算法2图论-算法图的遍历BFS()DFS(深搜)最小生成树PrimKruskal最短路径Bellman-FordDijkstraFloyd-WarshallBFS练习DFS练习Prim练习Kruskal练习Bellman-Ford练习Dijkstra练习Floyd-Warshall练习3图的遍历遍历要访问到图中的每一个顶点。BFS (Breadth-First Search)DFS (Depth-First Search)4BFS思想 遍历篇1.从图中某顶点v0出发，在访问了v0之后，搜索v0的(所有未被访问的)邻接顶点v1.v22.依次从这些邻接顶点出发，广搜图中其它顶点，直至
2、图中所有已被访问的顶点的邻接顶点都被访问到。3.若此时图中还有未被访问到的顶点，则再选择其中之一作为v0重复上述过程。直到图中所有顶点均被访问到。/搜索过程没有回溯，是一种牺牲空间换取时间的方法。时间复杂度：O(V+E)5BFS程序基本结构定义一个队列;起始点加入队列;while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则，从它扩展出子结点,全都添加到队尾;若循环中找到目标,输出结果;否则输出无解;6BFS示例：7DFS思想 遍历篇1.将图G中每个顶点标记为未被访问，选取一个顶点v作为搜索起点，标记其为已访问2.递归地深搜v的每个未被访问过的邻接顶点，直到从v出发所有可
3、达的顶点都已被访问过。3.若此时图中还有未被访问到的顶点，则再选择其中之一作为v重复上述过程。直到图中所有顶点均被访问到。 /时间复杂度：O(V+E)8DFS程序基本结构void DFS(int step)for(i=0; iMax_Elements; i+)if(子结点符合条件)新子结点入栈；if(是目标结点)输出elseDFS(step+1); 子结点出栈9DFS示例10最小生成树(Minimum Spanning Tree)G(V,E)是无向连通赋权图，G(V,E)是包含G中所有顶点的树，且树中各边权总和最小，则G是最小生成树(可能不唯一)容易想到，用贪心策略。PrimKruskal11
4、Prim思想 最小生成树篇1.从V中任取一结点放入V；2.在所有的端点分别在(V-V)和V中的边中，选一条权最小的加入E；3.将边E在(V-V)中的顶点从V中取出放入V；4.重复步骤23，直到V与V相等为止。/该算法步步为营，每步生成的结果均为最终结果的一部分。它每次从连接V与(V-V)的边中选最小边，所选出的不一定是所有尚未选出的属于最小生成树的边中的最小者。时间复杂度：O(ElgV)12Prime程序基本结构void Prim() int i,j,k,min,lowcostvex,closestvex;for(i=2;i=n;i+) lowcosti=c1i;/第1个点到其他点的代价clo
5、sesti=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点为起点进行新一轮的代价计算,更新lowcost和closestclosestj=k;无向连通图无向连通图,初始时初始时u只包只包含含1个点，后一步步将个点，后一步步将v中中的点添加到的点添加到u中来
6、。中来。用用closesti=0表示表示i点在点在u集合中集合中, lowcosti当前当前起点到起点到i点的最小代价点的最小代价cij 顶点顶点i到到j的权的权(i到到j无边，则令无边，则令cij=-1)，共有共有n个顶点个顶点 (该模板中，该模板中，顶点从顶点从1开始计开始计)13Prim示例：V V2 2V V0 0V V3 3V V5 5V V4 4V V1 1V2V2V0V0V 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 4
7、V V1 141V0V0V2V2V5V5V V4 4V V1 1214V0V0V2V2V5V5V3V3V V4 41425V2V2V0V0V5V5V1V1V3V335124V2V2V1V1V0V0V5V5V3V3V4V414Kruskal思想： 最小生成树篇1.将边按边树由小到大排序。2.每次加最小边 & 不构成回路。3.加进了n-1条边就得到了最小生成树/Kruskal算法并不保证每步生成的结果是连通的（中间结果可能不是树）。15Kruskal程序基本结构：优先队列+并查集16Kruscal示例： 实例的执行过程实例的执行过程12435661655563421、初始连通分量：、初始连通分量：
8、1,2,3,4,5,62、反复执行添加、放弃动作。条件：边数不等、反复执行添加、放弃动作。条件：边数不等于于 n-1时时 边边 动作动作连通分量连通分量 (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算法实现要点: 用并查集的相关操作：实现集合的并；判断新边的两端点是否处于同一集合，来确定是否构成
9、回路。17最短路径最短路径 (Shortest Path):(Shortest Path): 最短路径问题：如果从图中某一顶点最短路径问题：如果从图中某一顶点( (称为源点称为源点) )到达另一顶点到达另一顶点( (称为终称为终点点) )的路径可能不止一条，如何找到一条路径使得沿此路径上各边上的的路径可能不止一条，如何找到一条路径使得沿此路径上各边上的权值总和达到最小。权值总和达到最小。 边上权值非负情形的单源最短路径问题边上权值非负情形的单源最短路径问题 DijkstraDijkstra算法算法算法算法边上权值为任意值的单源最短路径问题边上权值为任意值的单源最短路径问题边上权值为任意值的单源
10、最短路径问题边上权值为任意值的单源最短路径问题 Bellman-FordBellman-Ford算法算法算法算法所有顶点之间的最短路径所有顶点之间的最短路径所有顶点之间的最短路径所有顶点之间的最短路径 FloydFloyd算法算法算法算法18Dijkstra思想： 最短路径篇 初始化：初始化： S S v v0 0 ;distdist j 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- -
11、 S S ; ; S S S S U U k k ;2 2、 修改：修改： distdist i i min min distdist i i, , distdist k k + + Edge Edge k k i i , for , for i i V V- - S S ; ; 3 3、 判断：判断： 若若S = VS = V, , 则算法结束，否则转则算法结束，否则转1 1。 引入一个辅助数组引入一个辅助数组distdist。distdist i i 表示当前从源点表示当前从源点v v0 0到终点到终点v vi i 的最短路径的最短路径的长度。时间复杂度的长度。时间复杂度:O(V:O(V2
12、 2) )19Dijkstra程序基本结构：void disktra(int v)/原点是v bool smaxn; register int i,j,k;for(i=1;i=n;i+)disti = cvi;si = 0; / i不在集合S中if(disti=manint)/v to i没有边previ = 0;elseprevi = v; sv = 1; distv = 0;for(i=1;in;i+)int temp = manint, u = v;for(j=1;j=n;j+)if(!sj&distj&distjtemp)u = j;temp = distj;su = 1;for(j=
13、1;j=n;j+)if(!sj&cujmanint)int newdist = distu + cuj;if(newdist distj)distj = newdist;prevj = u;结点从结点从1开始计，开始计，maxn为最大结点为最大结点数数,n为结点数，为结点数，manint是无穷大是无穷大, cij i到到j的权，的权，pre记录父结点记录父结点,disti源点到源点到i的最短路径，的最短路径，s表表示左边的集合示左边的集合const int maxn = 101, manint = 99999999;int cmaxnmaxn,prevmaxn,distmaxn,n;20Dij
14、kstraDijkstra逐步求解的过程逐步求解的过程逐步求解的过程逐步求解的过程21Bellman-Ford思想： 最短路径篇1.图中无负回路2.最短路径长度数组序列 dist1u,distn-1u，其中distiu从v到u最多经过i条边3. dist1u = Edgev,u distku = min distk-1u, min distk-1j+Edgej,u /时间复杂度：O(VE)22Bellman-Ford程序基本结构：void Bellman-Ford() int i;for(i=1;i=n;i+) di=manint;pari=0;ds=0;for(i=1;idu+w(u,v)
15、dv=du+w(u,v);parv=u;for each edge(u,v)if(dvdu+w(u,v)return false;return true;s为起点，为起点，di是是s到到i的最短路径长的最短路径长度，度，pari记录记录i结点的父节点结点的父节点.如果不存在从如果不存在从s可达的负可达的负权环，返回权环，返回true.2324Floyd-Warshall思想： 最短路径篇定义一个nn的方阵序列A0，A1，An，其中Aki-1j-1表示从vi到vj允许k个顶点v0, v1,vk-1为中间顶点的最短路径长度（A0 是图的邻接矩阵）。A0ij表示从vi到vj不经过任何中间顶点的最短路
16、径长度。Anij就是从vi到vj的最短路径长度。A0ij=arcsij0in-1, 0jn-1Akij=minAk-1ij,Ak-1ik-1+Ak-1k-1j 1kn，加入第k个顶点vk-1为中间顶点。/时间复杂度O(n3)25Floyd-Warshall程序基本结构：for(k=0;kn;k+) for(i=0;in;i+) for( j=0;jdik+dkj) dij=dik+dkj; ( dij=Min(dij, dik+dkj) )26Floyd示例：执行Floyd算法后:061211941058071496091001316872201416171110830712345985106
17、877618327Exercise Practice makes perfect! The more, the better!28BFS： zoj(1091)国际象棋棋盘上有一个马，要跳到指定目标，最少跳几步？ a b c d e f g h12345678h8a1输入：a1 h8输出：To get from a1 to h8 takes 6 knight moves. 29跳马的规则 a b c d e f g h12345678在23的矩形里：30BFS： a b c d e f g h1234567803321322312332233323333333233332例如：从a1到e4当目标
18、出现在所扩展出的结点里，结果就找到了。To get from a1 to e4 takes 3 knight moves. 31BFS：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,1,-2,2,-1,2,1, -1,2,-1,-2,-2,-1,-2,1;int m88;/给走过的点
19、标记char c1,c2,d1,d2;void proc();32void 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(); if(x = dx & y = dy)break; for(int i
20、=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)程序实现33双向BFS a b c d e f g h123456780212212122211112012从起点、终点同时开始双向BFS,有效地提高了时空效率。从起点找2步能跳
21、到的点从终点找1步能跳到的点34DFS： pku2258给无向图，求此图中的最长路径。要求路不能重复走，但节点可以重复地到达。如输入输入输出？输出？35/best用来记录最长路径的长度，griji到j的边长为1，以每一个结点为源点进行深搜#include #includeint gr2525,best,n,m;void dfs(int p,int depth) /p为源点，depth为深度 int i;bool flag=true;for(i=0;ibest)best=depth;return; main() int i,a,b;while(scanf(%d %d,&n,&m)!=EOF) i
22、f(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 #include using namespace std;#define Min(a,b) (a)(b)?(b):(a)#define Max(a,b) (a)(b)?(a):(b)double
23、 d201201;38Prim: double lowcost200,min,answer; memset(lowcost,0,sizeof(lowcost); answer=d01; for(i=1;in;i+)/与集合邻接的边长初始化，现在集合中只有一个点0 lowcosti=d0i; /初始化lowcost answer=Min(answer,d0i); /同时找出最短边 for(i=1;in;i+) min=1000000;j=-1; for(k=1;kn;k+) if(lowcostk!=0 & lowcostkmin)/找有最小边权的邻接点 min=lowcostk; j=k; a
24、nswer=Max(answer,min); if(j=1)/当集合加进了点1，可以结束 break; 39Prim: lowcostj=0;/集合加进点j for(k=1;kn;k+)/更新邻接点边权 if(djklowcostk & lowcostk!=0) lowcostk=djk; printf(Scenario #%dn,T+); printf(Frog Distance = %.3lfnn,answer); return 0;40Kruscal: zju1942class Edge/边类，记录三个信息：端点、边长public: int e,s; double dis; Edge()
25、 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(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 namesp
26、ace std;43Kruscal: 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(Frog Distance = %.3lfnn,edgei.dis); return 0;44Bellman-Ford:HomeWorkvoid Initialize_Single_S
27、ource(int s)for(i=1;idu+wuv)dv=du+wuv;Pav=u;Its to examine whether there exits negative 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 45Bellman-Ford:bool Bellman_Ford
28、(int s)Initialize_Single_Source(s);for(i=1;in;i+)for(j=1;j=n;j+) for(k=1;k=n;k+)if(wjk!=65535)Relax(j,k);for(j=1;j=n;j+) for(k=1;kdj+wjk ) return false;return true;int 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
29、here .);else printf(There exits negative cycles !);printf(n);return 0;/*565535 6 65535 7 6553565535 65535 5 8 -465535 -2 65535 65535 6553565535 65535 -3 65535 92 65535 7 65535 655351*/46Dijkstra: pku2387void Dijkstra(int n,int v)for(int i=1;i=n;i+)disti=cvi;si=false;if(disti=MAX) previ=0;else previ=
30、v;distv=0;sv=true;for(i=1;in-1;i+)int temp=MAX;int u=v;for(int j=1;j=n;j+)if(!sj)&(distjtemp)u=j;temp=distj;su=true;for(j=1;j=n;j+)if(!sj)&(cujMAX)int newdist=distu+cuj;if(newdistdistj)distj=newdist;prevj=u;#include #include #includeusing namespace std;const MAX=100002;int dist1001,c10011001,prev100
31、1;bool s1001;47Dijkstra:int main()int n,t,i,j;cintn;int x,y,len;for(i=1;i=n;i+)for(j=1;j=n;j+)if(i=j) continue;cij=MAX;for(i=1;i=n;i+) cii=0;for(i=0;ixylen;if(lencxy)cxy=cyx=len;Dijkstra(n,n);coutdist1endl;return 0;48Floyd-Warshall: zju1942（青蛙）#include #include #include using namespace std;#define M
32、ax(a,b) (a)(b)?(a):(b)#define Min(a,b) (a)(b)?(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); 49Floyd-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算法505152感谢您的阅览感谢您的阅览【此课件下载后可自行编辑修改此课件下载后可自行编辑修改此课件下载后可自行编辑修改此课件下载后可自行编辑修改关注我关注我关注我关注我每天分享干货每天分享干货每天分享干货每天分享干货】53
