《图论算法.ppt》由会员分享,可在线阅读,更多相关《图论算法.ppt(50页珍藏版)》请在三一文库上搜索。
1、ACM/ICPC程序设计,简单算法 计算机学院 张淑平,图论-算法,图的遍历 BFS(广搜) DFS(深搜) 最小生成树 Prim Kruskal 最短路径 Bellman-Ford Dijkstra Floyd-Warshall,BFS练习 DFS练习 Prim练习 Kruskal练习 Bellman-Ford练习 Dijkstra练习 Floyd-Warshall练习,图的遍历,遍历要访问到图中的每一个顶点。 BFS (Breadth-First Search) DFS (Depth-First Search),BFS思想 遍历篇,1.从图中某顶点v0出发,在访问了v0之后,搜索v0的(所
2、有未被访问的)邻接顶点v1.v2 2.依次从这些邻接顶点出发,广搜图中其它顶点,直至图中所有已被访问的顶点的邻接顶点都被访问到。 3.若此时图中还有未被访问到的顶点,则再选择其中之一作为v0重复上述过程。直到图中所有顶点均被访问到。 /搜索过程没有回溯,是一种牺牲空间换取时间的方法。时间复杂度:O(V+E),BFS程序基本结构,定义一个队列; 起始点加入队列; while(队列不空) 取出队头结点; 若它是所求的目标状态,跳出循环; 否则,从它扩展出子结点,全都添加到队尾; 若循环中找到目标,输出结果; 否则输出无解;,BFS示例:,DFS思想 遍历篇,1.将图G中每个顶点标记为未被访问,选取
3、一个顶点v作为搜索起点,标记其为已访问 2.递归地深搜v的每个未被访问过的邻接顶点,直到从v出发所有可达的顶点都已被访问过。 3.若此时图中还有未被访问到的顶点,则再选择其中之一作为v重复上述过程。直到图中所有顶点均被访问到。 /时间复杂度:O(V+E),DFS程序基本结构,void DFS(int step) for(i=0; iMax_Elements; i+) if(子结点符合条件) 新子结点入栈; if(是目标结点) 输出 else DFS(step+1); 子结点出栈 ,DFS示例,最小生成树(Minimum Spanning Tree),G(V,E)是无向连通赋权图,G(V,E)是
4、包含G中所有顶点的树,且树中各边权总和最小,则G是最小生成树(可能不唯一) 容易想到,用贪心策略。 Prim Kruskal,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程序基本结构,void Prim() int i,j,k,mi
5、n,lowcostvex,closestvex; for(i=2;i0) min=lowcostj;/在v中找到最小的代价点k k=j; closestk=0;/k归入u中 for(j=2;j0) lowcostj=ckj; /以k点为起点进行新一轮的代价计算,更新lowcost和closest closestj=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.每次加最小边 & 不构成回路。 3.加进
6、了n-1条边就得到了最小生成树 /Kruskal算法并不保证每步生成的结果是连通的(中间结果可能不是树)。,Kruskal程序基本结构:,优先队列+并查集,Kruscal 示例:,实例的执行过程,1,2,4,3,5,6,6,1,6,5,5,5,6,3,4,2,1、初始连通分量:1,2,3,4,5,6 2、反复执行添加、放弃动作。条件:边数不等于 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) 放弃
7、因构成回路 (2,3) 添加 1,3,4,5,6,2,1,2,4,3,5,6,1,5,3,4,2,5,5,最短路径 (Shortest Path):,最短路径问题:如果从图中某一顶点(称为源点)到达另一顶点(称为终点)的路径可能不止一条,如何找到一条路径使得沿此路径上各边上的权值总和达到最小。 边上权值非负情形的单源最短路径问题 Dijkstra算法 边上权值为任意值的单源最短路径问题 Bellman-Ford算法 所有顶点之间的最短路径 Floyd算法,Dijkstra思想: 最短路径篇,初始化: S v0 ;distj Edge0j, j = 1, 2, , n-1; 1、求出最短路径的长
8、度: distk min disti , i V- S ; S S U k ; 2、 修改: disti min disti, distk + Edgeki , for iV- S ; 3、 判断: 若S = V, 则算法结束,否则转1。 引入一个辅助数组dist。disti表示当前从源点v0到终点vi 的最短路径的长度。时间复杂度:O(V2),Dijkstra程序基本结构:,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(dis
9、ti=manint)/v to i没有边 previ = 0; else previ = v; sv = 1; distv = 0; for(i=1;in;i+) int temp = manint, u = v; for(j=1;j=n;j+) if(!sj ,Dijkstra逐步求解的过程,Bellman-Ford思想: 最短路径篇,1.图中无负回路 2.最短路径长度数组序列 dist1u,distn-1u,其中distiu从v到u最多经过i条边 3. dist1u = Edgev,u distku = min distk-1u, min distk-1j+Edgej,u /时间复杂度:O
10、(VE),Bellman-Ford程序基本结构:,void Bellman-Ford() int i; for(i=1;idu+w(u,v) dv=du+w(u,v); parv=u; for each edge(u,v) if(dvdu+w(u,v) return false; return true; ,Floyd-Warshall思想: 最短路径篇,定义一个nn的方阵序列A0,A1,An,其中Aki-1j-1表示从vi到vj允许k个顶点v0, v1,vk-1为中间顶点的最短路径长度(A0 是图的邻接矩阵)。A0ij表示从vi到vj不经过任何中间顶点的最短路径长度。Anij就是从vi到vj
11、的最短路径长度。 A0ij=arcsij 0in-1, 0jn-1 Akij=minAk-1ij,Ak-1ik-1+Ak-1k-1j 1kn,加入第k个顶点vk-1为中间顶点。 /时间复杂度O(n3),Floyd-Warshall程序基本结构:,for(k=0;kdik+dkj) dij=dik+dkj; ( dij=Min(dij, dik+dkj) ),Floyd示例:,执行Floyd算法后:,Exercise,Practice makes perfect! The more, the better!,BFS: zoj(1091),国际象棋棋盘上有一个马,要跳到指定目标,最少跳几步?,a
12、b c d e f g h,1 2 3 4 5 6 7 8,h8,a1,输入: a1 h8 输出: To get from a1 to h8 takes 6 knight moves.,跳马的规则,a b c d e f g h,1 2 3 4 5 6 7 8,在23的矩形里:,BFS:,例如:从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
13、+) 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;/给走过的点标记 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
14、.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 ,初始点入队,取出队头元素,新点加入队尾,Knight Moves zoj(1091)程序实现,双向BFS,从起点、终点同时开始,双向BFS,有效地提高了时空效率。,从起点找2步能跳到的点,从终点找1步能跳到的点,DFS: pku2258,给无向图,求此图中的最长路径。要求路不能重复走,但节点可以重复地到达。如,/best
15、用来记录最长路径的长度,griji到j的边长为1,以每一个结点为源点进行深搜 #include #include int gr2525,best,n,m; void dfs(int p,int depth) /p为源点,depth为深度 int i; bool flag=true; for(i=0;ibest) best=depth; return; ,青蛙(zju1942),湖中有一些石头露出水面。青蛙Freddy蹲在其中一块上面,他女朋友Fiona在另一块上。Freddy想跳到Fiona那里。 Freddy可以在两石头间跳跃,有不同的路径选择;他希望找到一条路,路上跳跃的最大距离最小。 输
16、入这些石头的坐标,输出这个最小值。,Prim: zju1942,int main() int n,i,j,k,x200,y200,T=1; ifstream fin(“frogger.in“); #define cin fin while(cinn ,#include #include #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(low
17、cost,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 ,Prim:,lowcostj=0;/集合加进点j for(k=1;kn;k+)/更新邻接点边权 if(djklowcostk ,Kruscal: zju1942,class Edge/边类,记录三个信息:
18、端点、边长 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.dise2.dis; ,Kruscal: (并查集的操作),int s200; int Find(int k)/寻找k的祖先 int r,t,tmp; for(r=k;sr!=r;r=sr); for(t=k;t!=r;t=tmp) tmp=st;st=r; /路径压缩 return r
19、; void Unite(int a,int b) /把a、b所在的集合合并 a=Find(a);b=Find(b); if(a!=b)/当a,b属于不同的集合,合并这两个集合 sb=a; ,合并只需要一个操作:修改父节点。,Kruscal:,int main() int n,i,j,x200,y200,T=1,L; while(cinn /标准库的函数,对边进行从小到大排序,#include #include #include #include using namespace std;,Kruscal:,for(i=0;in;i+) /并查集的初始化,刚开始,每个点自成集合。 si=i; f
20、or(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; ,Bellman-Ford: HomeWork,void Initialize_Single_Source(int s) for(i=1;idu+wuv) dv=du+wuv; Pav=u; ,Bellman-
21、Ford:,bool Bellman_Ford(int s) Initialize_Single_Source(s); for(i=1;idj+wjk ) return false; return true; ,Dijkstra: pku2387,void Dijkstra(int n,int v) for(int i=1;i=n;i+) disti=cvi; si=false; if(disti=MAX) previ=0; else previ=v; distv=0;sv=true; for(i=1;in-1;i+) int temp=MAX; int u=v; for(int j=1;j=
22、n;j+) if(!sj) ,Dijkstra:,int main() int n,t,i,j; cintn; int x,y,len; for(i=1;ixylen; if(lencxy) cxy=cyx=len; Dijkstra(n,n); coutdist1endl; return 0; ,Floyd-Warshall: zju1942(青蛙),#include #include #include using namespace std; #define Max(a,b) (a)(b)?(a):(b) #define Min(a,b) (a)(b)?(b):(a) int main()
23、 int n,i,j,k,x201,y201,T=1; double d201201; 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(“Frog Distance = %.3lfnn“,d01); return 0; ,Floyd算法,相关题目:,图的遍历:BFS + DFS PKU:1348,2258, ZJU:1004,1204,1267,1457,1711,1984,1990, 最小生成树:Prim + Kruskal PKU:1251,2421, ZJU:1942, 最短路径:Bellman-Ford+Dijkstra+Floyd PKU:1125,2387, ZJU:1221, 1333, 1589, 1942,1952,
链接地址:https://www.31doc.com/p-3290110.html