《图基本算法.ppt》由会员分享，可在线阅读，更多相关《图基本算法.ppt（55页珍藏版）》请在三一办公上搜索。
1、图的基本算法,目录,1.图的基本概念2.最小生成树算法3.最短路问题4.拓扑排序5.浅析SPFA的优化 栈6.时间允许的情况下，讲tarjan算法,图的基本概念,图：二元组 称为图(graph)。V为结点(node)点(vertex)集。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=1;in;i+)int min=INT_MAX;for(j=1;
5、j=n;j+)if(closestj,时间复杂度为O(n2)。(用堆维护最小优先级队列可以达到O(vlogv+elogv),有兴趣的同学可以自己实现),kruskal算法的基本思想,对所有边从小到大排序；依次试探将边和它的端点加入生成树，如果加入此边后不产生圈，则将边和它的端点加入生成树；否则，将它删去；直到生成树中有了n-1条边，即告终止。算法的时间复杂度O(eloge),kruskal算法实现的数据结构,一维数组，将所有边按从小到大的顺序存在数组里面并查集先把每一个对象看作是一个单元素集合，然后按一定顺序将相关联的元素所在的集合合并。能够完成这种功能的集合就是并查集。对于并查集来说，每个集
6、合用一棵树表示。它支持以下操作：Union(Root1,Root2)/合并两个集合；Findset(x)/搜索操作（搜索编号为x所在树的根）。树的每一个结点有一个指向其父结点的指针。,并查集的处理过程,MAKE-SET(x)1 px x2 rankx 0UNION(x,y)1 LINK(FIND-SET(x),FIND-SET(y)LINK(x,y)1 if rankx ranky2 then py x3 else px y4 if rankx=ranky5 then ranky ranky+1The FIND-SET procedure with path compression is qu
7、ite simple.FIND-SET(x)1 if x px2 then px FIND-SET(px)3 return px,MST-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条边构成的无向图，找出一棵生成树，使得这个生成树上的最大边与最小边权值之差最小,思路
8、：,用Kruskal！由于kruskal算法是将边排序后从最小权值边开始不断地加入不形成环的边，我们可以由小到大枚举每次形成的生成树中的最小边来求的若干棵生成树。每次更新一下差值。求得最优解。,练习,Prim POJ 1258 POJ 2485 Kruskal POJ1861,最短路问题,单源最短路径bellman-ford算法 spfa算法 dijkstra算法每对顶点的最短路径 floyd-washall算法,单源最短路径,已知图G=(V,E),我们希望找出从某给定源顶点sV到每个顶点vV的最短路径。在单源最短路径问题的某些实例中，可能存在着权值为负的边，如果图不包含从s可达的负权回路，则
9、对所有的vV，最短路径的权的定义依然正确。如果存在一条从s可达的负权回路，则最短路径的定义就不成立了。易知，一条最短路径不能包含回路。,松弛技术,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
10、 Do For 每条边(u,v)EG Do Relax(u,v,w)For每条边(u,v)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算法的说明：如果没有负
11、权回路，运行一次bellmanford算法，将得到源点到任意点的最短路：由于源点到任意一点至多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！注意路径是双向的，虫洞是单向的。现
12、在农夫John希望知道能否从某块地出发并且回到这块地，使得他回来的时间早于出发的时间（可以遇到他自己）。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算法就可以判断出是否存在负权回路。代码
13、附后,Dijkstra算法,Dijkstra算法解决了有向图G=(V,E)上带权的单源最短路径问题，但要求所有边的权值非负。Djikstra算法中设置了一顶点集合S，从源点s到集合中的顶点的最终最短路径的权值均已确定，算法反复选择具有最短路径估计的顶点uV-S,并将u加入S中，对u的所有出边进行松弛。,算法执行过程,int dijkstra(int s,int n)int i,j;int vMAX;int dMAX;for(i=1;idj)min=dj;now=j;vnow=1;for(j=1;j=n;j+)/松弛if(!vj,依然是O(n2)的算法，依然可以用堆优化到O(elogv+vlog
14、v),spfa算法,ShortestpathfasteralgorithmSPFA 其实就是Bellman-Ford的一种队列实现，减少了冗余，即松驰的边至少不会以一个d为的点为起点。算法：1.队列Q=s2.取出队头u,枚举所有的u的临边.若d(v)d(u)+w(u,v)则改进，pre(v)=u，由于d(v)减少了，v可能在以后改进其他的点，所以若v不在Q中，则将v入队。3.一直迭代2，直到队列Q为空(正常结束)，或有的点的入队次数=n（含有负圈）。一般用于找负圈(效率高于Bellman-Ford)，稀疏图的最短路由于点可能多次入队，但队列中同时不会超过n个点。所以用一个长度为n的循环队列来实
15、现这个队。SPFA在形式上和宽度优先搜索非常类似，不同的是宽度优先搜索中一个点出了队列就不可能重新进入队列，但是SPFA中一个点可能在出队列之后再次被放入队列，也就是一个点改进过其它的点之后，过了一段时间可能本身被改进，于是再次用来改进其它的点，这样反复迭代下去。设一个点用来作为迭代点对其它点进行改进的平均次数为k，有办法证明对于通常的（不含负圈，较稀疏）情况，k在2左右。算法复杂度理论上同Bellman-Ford，O(nm)，但实际上却是O(km)。,例题：看晴子大牛的体型知道他一定又馋又懒，他有n-1个小弟，每天都让他的n-1个小弟去n-1个不同的饭馆给他买回山珍海味，已知饭馆之间是以有向
16、图连接起来的，我们可以保证每两个饭馆之间可以互相可达，问他的小弟帮他买回饭来总共走的最短路程是多少（假设晴子大牛所在顶点为点1，饭馆为2n）？n=m=1000000,由于数据范围很大，Dijkstra算法和Bellman-Ford超时，我们可以用spfa算法求得由点1到其他点的距离，那么怎么求从其他点到点1的距离呢？我们可以把每条有向边反向，这样再用spfa在反向的图中求一次源点到其他的点的距离就求出了从每个点到源点的距离。代码附后,单源最短路问题小结,Dijkstra算法的效率高，但是也有局限性，就是对于含负权的图无能为力。Bellman-Ford算法对于所有最短路长存在的图都适用，但是效率
17、常常不尽人意。SPFA算法可以说是综合了上述两者的优点。它的效率同样很不错，而且对于最短路长存在的图都适用，无论是否存在负权。它的编程复杂度也很低，是性价比极高的算法。对于绝大多数最短路问题，我们只需套用经典算法就行了。所以往往我们的难点是在模型的建立上。,每对顶点的最短路径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(
18、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(k-1)k,j实现：for(k=1;k=n;k+)for(i=1;i=n;i+)for(j=1;j=n;j+)fij=min(fij,fik+fkj);,floyd计算图的传递闭包,如果将每一对顶点间的最短路问题进行简化，只要判断每一对点间是否存在一条路径，这样的问题称作图的传递闭包。用bool类型的数组ti,j来记录vi到vj是否有路径。递推计算t(0)i,j,t(1)i,j,
19、t(n)i,j。t(k)i,j表示从vi到vj是否存在中间顶点的编号都不超过k的路径。递推公式：t(k)i,j=t(k-1)i,j or(t(k-1)i,k and t(k-1)k,j),例题：POJ1975,练习 POJ 1125(floyd求最短路)代码附后,拓扑排序,拓扑排序是对有向无回路图(DAG)顶点的一种排序，它使得如果存在u,v的有向路径，那么满足序中u在v前。一个有向图的拓扑序列不唯一，而且可能不存在拓扑序列。无圈的有向图都可以构造出拓扑序列。,拓扑排序,基本思想从图中选择一个入度为0的顶点加入拓扑序列；从图中删除该顶点和它的所有出边；重复上面两个步骤，直到所有的顶点都进入了拓
20、扑序列为止。,晴子大牛穿衣服的例子,课后练习题,POJ 2387 POJ 1847POJ 1062POJ 2253ZOJ 1589ZOJ 1952,Relax(u,v)If F(v)F(u)+W_Cost(u,v)thenF(v)=F(u)+W_Cost(u,v);,SPFA的核心正是松弛操作：,但松弛操作直接得出的Bellman-Ford算法效率低下 For Time=1 to N For(u,v)ERelax(u,v),上图数据中，总运算量高达N2而边(S,A1)虽然被调用N次。但实际有用的只有一次,SPFA则使用队列进行了优化！,思想：只保存被更新但未扩展的节点。减少了大量无用的计算，效
21、率大大提高！,在上图的例子中，每个节点只进队一次，只需N次运算。相比Bellman-Ford优势明显。,但有负环时依然退化为O(NM),在1000000个点，2000000条边的随机数据中SPFA甚至比使用堆优化的Dijkstra还要快。,能够改进吗？,长期以来基于队列的SPFA并未取得突破,传统的队列实现:,缺点：NewNode需要之前的元素全部出队后才能扩展 中断了迭代的连续性,Tail,New 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);,核心思想:每次从刚刚被更新的节点开始递归进行下一次迭代！,后进先出！,判断存在负环的条件：重新经过某个在当前搜索栈中的节点,相比队列，深度优先有着先天优势：在环上走一圈，回到已遍历过的点即有负环。绝大多数情况下时间为O(M)级别。,一个简洁的数据结构和算法在一定程度上解决了大问题。,优美的SPFA！,
