《图基本算法》PPT课件.ppt

《《图基本算法》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《图基本算法》PPT课件.ppt（55页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、图的基本算法的基本算法 目目录1.图的基本概念2.最小生成树算法3.最短路问题4.拓扑排序5.浅析SPFA的优化 栈栈6.时间允许的情况下，讲tarjan算法 图的基本概念的基本概念图：二元组 称为图(graph)。V V为结点(node)点(vertex)集。E E为图中结点之间的边的集合。简单图环：端点重合为一点的边。重边：两条边连接同一对顶点。简单图：没有环和重边的图。无向图和有向图如果边都是双向的，则这个图叫做无向图。如果边都是单向的，则这个图叫做有向图。图的基本概念的基本概念子图：连通性无向图中，如果两个顶点之间存在一条路经，就称这两个顶点是连通的。有向图中，如果两个顶点之间相互都存

2、在一条路，则称它们是强连通的。如果一个图的任意两个顶点都是连通的，就称这个图是连通的。顶点的度无向图中，一个顶点相连的边数称为该顶点的度。有向图中，从一个顶点出发的边数称为该顶点得出度；到达该顶点的边数称为它的入度。顶点的最大度数称为图的度数。路和回路一个连接两个顶点的，顶点与边交替的序列称为路。除了起始与终止顶点，其他顶点都不相同，这样的路称为简单路径。起始与终止顶点相同的简单路径称为圈。图的基本概念的基本概念 完全图、稠密图和稀疏图任何两个顶点之间都有边（弧）相连称为完全图边（弧）很少的图称为稀疏图反之为稠密图图的表示方法的表示方法邻接矩阵邻接表邻接矩接矩阵邻接表接表邻接表表示法常用于稀疏

3、图需要记录的信息：结点首指针，边的权值和下一条边的指针邻接表的接表的实现 Struct Edgeint vertex;/记录结点编号int val;/边的权值Edge*next;/记录链表的下一个元素;Edge*edge=new Edgen;for(int i=0;iuvw)/(u,v)表示一条边,w表示权值L=new Edge;L-vertex=v;L-val=w;L-next=edgeu;edgeu=L;/将(u,v)插入到以u起点的链表中 遍历与u相邻的节点：L=edgeu;while(L!=NULL).L=L-next;最小生成最小生成树问题生成树：由G的n-1条边构成的无环的子图，这

4、些边的集合成为生成树。最小生成树：所有生成树中权值最小的一个边集T为最小生成树，确定树T的问题成为最小生成树问题。prim算法kruskal算法prim算法的基本思想算法的基本思想任取一个顶点加入生成树；在那些一个端点在生成树里，另一个端点不在生成树里的边中，取权最小的边，将它和另一个端点加进生成树。重复上一步骤，直到所有的顶点都进入了生成树为止。int prim(int s)/s为初始加入的点int i,j,sum=0;for(i=1;i=n;i+)closesti=10000000;for(i=1;i=n;i+)closesti=mapsi;closests=0;int now;for(i

5、=1;in;i+)int min=INT_MAX;for(j=1;j=n;j+)if(closestj&closestjmin)min=closestj;now=j;sum+=min;closestnow=0;for(j=1;j=n;j+)if(mapnowj&mapnowj ranky2 then py x3 else px y4 if rankx=ranky5 then ranky ranky+1The FIND-SET procedure with path compression is quite simple.FIND-SET(x)1 if x px2 then px FIND-SE

6、T(px)3 return pxMST-KRUSKAL(G,w)1.A2.for 每个结点vVG3.do MAKE-SET(v)4.根据权w的非递减顺序对E的边进行排序5.for 每条边(u,v)E，按权的非递减次序6.do if FIND-SET(u)FIND-SET(v)7.then AA(u,v)8.UNION(u,v)9.return A复杂度E*logE例例题 POJ3522题目大意：给出一个由n个点m条边构成的无向图，找出一棵生成树，使得这个生成树上的最大边与最小边权值之差最小思路：思路：用Kruskal！由于kruskal算法是将边排序后从最小权值边开始不断地加入不形成环的边，我

7、们可以由小到大枚举每次形成的生成树中的最小边来求的若干棵生成树。每次更新一下差值。求得最优解。练习 Prim POJ 1258 POJ 2485 Kruskal POJ1861最短路最短路问题单源最短路径bellman-ford算法 spfa算法 dijkstra算法每对顶点的最短路径 floyd-washall算法 单源最短路径源最短路径已知图G=(V,E),我们希望找出从某给定源顶点sV到每个顶点vV的最短路径。在单源最短路径问题的某些实例中，可能存在着权值为负的边，如果图不包含从s可达的负权回路，则对所有的vV，最短路径的权的定义依然正确。如果存在一条从s可达的负权回路，则最短路径的定义

8、就不成立了。易知，一条最短路径不能包含回路。松弛技松弛技术bellman-ford，spfa，dijkstra算法都使用了松弛技术，对每个顶点vV,都设置一个属性dv,用来描述从源点s到v的最短路径上权值的上界。伪代码：初始化：Init(G,s)for each vertex vVG do dv=;ds=0;松弛：Relax(u,v,w)if(dvdu+w(u,v)dv=du+w(u,v)Bellman-Ford算法算法Bellman-Ford(G,w,s)Init(G,s)For i 1 to|VG|-1 Do For 每条边(u,v)EG Do Relax(u,v,w)For每条边(u,v

9、)EG Do If dv du+w(u,v)Then Return FALSEReturn TRUE/时间复杂度为O(V*E);Bellman-Ford算法能在一般的情况（存在负边权的情况）下解决单源最短路径问题，对于给定的带权有向图G=(V,E)，其源点为s，对该图运行Bellman-Ford算法后可以返回一个bool值表明图中是否存在着一个从源点可达的权为负的回路，若存在这样的回路的话，算法说明该问题无解，若不存在这样的回路，算法将产生最短路径及其权值。对bellman-ford算法的说明：如果没有负权回路，运行一次bellmanford算法，将得到源点到任意点的最短路：由于源点到任意一点

10、至多n-1条边，我们经过n-1次循环，每重循环对所有的边进行松弛，能保证每次至少得到一个di，其值为源点到i点的最短路，最终n-1次循环之后就能求得所有的di。如果包含负权回路，那么n-1次循环之后还会存在点u，v，使得dvdu+wu,v，这样我们就能判断是否存在负权回路。例例题：POJ 3259题目大意：农场上有N块田地（N =500），M条路径（M=2500）可以从i到达j花费t单位时间。另外还有W个虫洞（W=200），虫洞可以从一块地i到达另一块地j并且时间倒退t！注意路径是双向的，虫洞是单向的。现在农夫John希望知道能否从某块地出发并且回到这块地，使得他回来的时间早于出发的时间（可以

11、遇到他自己）。2 /农场个数 (text cases)3 3 1 /田地 路径 虫洞 他们的个数1 2 2 /田地路径 u，v，以及经过需要的时间1 3 42 3 13 1 3 /虫洞路径 u，v，以及倒流的时间3 2 11 2 32 3 43 1 8题目分析：此题题意是判断有向图中是否存在负权回路，怎样构造图呢？对于双向路径(u,v),可以构造成两条边(u,v,t)和(v,u,t)，对于虫洞单向路径(u,v)，可以构造一条边(u,v,-t)，这样运行bellman-ford算法就可以判断出是否存在负权回路。代码附后Dijkstra算法算法Dijkstra算法解决了有向图G=(V,E)上带权的

12、单源最短路径问题，但要求所有边的权值非负。Djikstra算法中设置了一顶点集合S，从源点s到集合中的顶点的最终最短路径的权值均已确定，算法反复选择具有最短路径估计的顶点uV-S,并将u加入S中，对u的所有出边进行松弛。算法算法执行行过程程int dijkstra(int s,int n)int i,j;int vMAX;int dMAX;for(i=1;i=n;i+)di=map1i;v1=1;for(i=1;in;i+)int now,min=INT_MAX;for(j=1;jdj)min=dj;now=j;vnow=1;for(j=1;j=n;j+)/松弛if(!vj&dnow+mapn

13、owjd(u)+w(u,v)则改进，pre(v)=u，由于d(v)减少了，v可能在以后改进其他的点，所以若v不在Q中，则将v入队。3.一直迭代2，直到队列Q为空(正常结束)，或有的点的入队次数=n（含有负圈）。一般用于找负圈(效率高于Bellman-Ford)，稀疏图的最短路由于点可能多次入队，但队列中同时不会超过n个点。所以用一个长度为n的循环队列来实现这个队。SPFA在形式上和宽度优先搜索非常类似，不同的是宽度优先搜索中一个点出了队列就不可能重新进入队列，但是SPFA中一个点可能在出队列之后再次被放入队列，也就是一个点改进过其它的点之后，过了一段时间可能本身被改进，于是再次用来改进其它的点

14、，这样反复迭代下去。设一个点用来作为迭代点对其它点进行改进的平均次数为k，有办法证明对于通常的（不含负圈，较稀疏）情况，k在2左右。算法复杂度理论上同Bellman-Ford，O(nm)，但实际上却是O(km)。例题：看晴子大牛的体型知道他一定又馋又懒，他有n-1个小弟，每天都让他的n-1个小弟去n-1个不同的饭馆给他买回山珍海味，已知饭馆之间是以有向图连接起来的，我们可以保证每两个饭馆之间可以互相可达，问他的小弟帮他买回饭来总共走的最短路程是多少（假设晴子大牛所在顶点为点1，饭馆为2n）？n=m=1000000由于数据范围很大，Dijkstra算法和Bellman-Ford超时，我们可以用s

15、pfa算法求得由点1到其他点的距离，那么怎么求从其他点到点1的距离呢？我们可以把每条有向边反向，这样再用spfa在反向的图中求一次源点到其他的点的距离就求出了从每个点到源点的距离。代码附后单源最短路源最短路问题小小结Dijkstra算法的效率高，但是也有局限性，就是对于含负权的图无能为力。Bellman-Ford算法对于所有最短路长存在的图都适用，但是效率常常不尽人意。SPFA算法可以说是综合了上述两者的优点。它的效率同样很不错，而且对于最短路长存在的图都适用，无论是否存在负权。它的编程复杂度也很低，是性价比极高的算法。对于绝大多数最短路问题，我们只需套用经典算法就行了。所以往往我们的难点是在

16、模型的建立上。每每对顶点的最短路径点的最短路径floyd-washall算法的基本思想算法的基本思想递推产生矩阵序列f(0),f(1),f(n)。其中f(0)i,j=mapi,jf(k)i,j的值表示从vi到vj，中间结点编号不超过k的最短路径长度。f(n)i,j的值就是从vi到vj的最短路径长度。递推推过程程-动态规划划如果f(k)i,j中间节点编号经过k，则f(k)i,j=f(k-1)i,k+f(k-1)k,j。如果f(k)i,j中间节点不经过k，则f(k)i,j=f(k-1)i,j如果f(k-1)i,jf(k-1)i,k+f(k-1)k,j，那么就令f(k)i,j=f(k-1)i,k+f

17、(k-1)k,j实现：for(k=1;k=n;k+)for(i=1;i=n;i+)for(j=1;jF(u)+W_Cost(u,v)thenF(v)=F(u)+W_Cost(u,v);SPFA的核心正是松弛操作：.A1TAnS但松弛操作直接得出的Bellman-Ford算法效率低下 For Time=1 to N For(u,v)ERelax(u,v)上图数据中，总运算量高达N2而边(S,A1)虽然被调用N次。但实际有用的只有一次SPFA则使用队列进行了优化！思想：只保存被更新但未扩展的节点。减少了大量无用的计算，效率大大提高！A1A2.A4An-1A3AnHeadTail当前待扩展元素在上图

18、的例子中，每个节点只进队一次，只需N次运算。相比Bellman-Ford优势明显。.A1TAnS但有负环时依然退化为O(NM)在1000000个点，2000000条边的随机数据中SPFA甚至比使用堆优化的Dijkstra还要快。A1TAnS.长期以来基于队列的SPFA并未取得突破传统的队列实现:缺点：NewNode需要之前的元素全部出队后才能扩展 中断了迭代的连续性A1A2.A4An-1A3AnHeadTailNew Node猜想：猜想：能否把能否把NewNode放在放在Head后面进行下一次扩展？后面进行下一次扩展？猜想程序图论中的基本算法 ：深度优先搜索 基本数据结构：栈SPFA_Dfs(Node)For(Node,v)E If disv disNode+w(Node,v)then disv=disNode+w(Node,v);SPFA_Dfs(v);核心思想:每次从刚刚被更新的节点开始递归进行下一次迭代！后进先出！后进先出！判断存在负环的条件：判断存在负环的条件：重新经过某个在重新经过某个在当前搜索栈中的节点当前搜索栈中的节点A1TAnS.相比队列，深度优先有着先天优势：在环上走一圈，回到已遍历过的点即有负环。绝大多数情况下时间为O(M)级别。一个简洁的数据结构和算法在一定程度上解决了大问题。优美的SPFA！