图论主流算法总结.doc

算法总结图论菜鱼QQ：155175157一、图论算法1. Relaxation(松弛操作)：procedure relax(u,v,w:integer);/多数情况下不需要单独写成procedure。begin if disu+wdisv then begin disv:=disu+w; prev:=u; endend;2. Dijkstra1) 适用条件&范围：a) 单源最短路径(从源点s到其它所有顶点v);b) 有向图&无向图(无向图可以看作(u,v),(v,u)同属于边集E的有向图)c) 所有边权非负(任取(i,j)E都有Wij0);2) 算法描述：a) 初始化：disv=maxint(vV,vs); diss=0; pres=s; S=s;b) For i:=1 to n1.取V-S中的一顶点u使得disu=mindisv|vV-S2.S=S+u3.For V-S中每个顶点v do Relax(u,v,Wu,v)c) 算法结束：disi为s到i的最短距离；prei为i的前驱节点3) 算法优化：使用二叉堆(Binary Heap)来实现每步的DeleteMin(ExtractMin，即算法步骤b中第1步)操作，算法复杂度从O(V2)降到O(V+E)V)。推荐对稀疏图使用。使用Fibonacci Heap(或其他Decrease操作O(1),DeleteMin操作O(logn)的数据结构)可以将复杂度降到O(E+VV)；如果边权值均为不大于C的正整数，则使用Radix Heap可以达到O(E+VC)。但因为它们编程复杂度太高，不推荐在信息学竞赛中使用。4) 程序：注：程序使用二叉堆3. Bellman-Ford1) 适用条件&范围：a) 单源最短路径(从源点s到其它所有顶点v);b) 有向图&无向图(无向图可以看作(u,v),(v,u)同属于边集E的有向图);c) 边权可正可负(如有负权回路输出错误提示);d) 差分约束系统;2) 算法描述：对每条边进行|V|次Relax操作;完成后，如果存在(u,v)E使得disu+wdisv,则存在负权回路;否则disv即为s到v的最短距离,prev为前驱。3) 算法实现：For i:=1 to |V| doFor 每条边(u,v)E do Relax(u,v,w);For每条边(u,v)E doIf disu+w0) doi. 顶点v出栈；输出v；计数器增1；ii. For 与v邻接的顶点u do1. dec(indgru);2. If indgru=0 then 顶点u入栈f) EXIT(I=|V|)简单&高效&实用的算法。上述实现方法复杂度O(V+E)4) 程序：5. SSSP On DAG1) 适用条件&范围：a) DAG(Directed Acyclic Graph,有向无环图);b) 边权可正可负2) 算法描述：a) Toposort;b) If Toposort=False Then HALT(Not a DAG)c) For 拓扑序的每个顶点u doFor u的每个邻接点v do Relax(u,v,w);算法结束后：如有环则输出错误信息；否则disi为s到i的最短距离，prei为前驱顶点。3) 算法实现：基本从略。此算法时间复杂度O(V+E)，时间&编程 复杂度低，如遇到符合条件的题目(DAG)，推荐使用。还有，此算法的步骤c可以在toposort中实现，这样即减小了此算法复杂度的一个系数。4) 程序：6. Floyd-Warshall1) 适用范围：a) APSP(All Pairs Shortest Paths)b) 稠密图效果最佳c) 边权可正可负2) 算法描述：a) 初始化：disu,v=wu,vb) For k:=1 to nFor i:=1 to nFor j:=1 to nIf disi,jdisi,k+disk,j ThenDisI,j:=disI,k+disk,j;c) 算法结束：dis即为所有点对的最短路径矩阵3) 算法小结：此算法简单有效，由于三重循环结构紧凑，对于稠密图，效率要高于执行|V|次Dijkstra算法。时间复杂度O(n3)。考虑下列变形：如(I,j)E则disI,j初始为1,else初始为0，这样的Floyd算法最后的最短路径矩阵即成为一个判断I,j是否有通路的矩阵。更简单的，我们可以把dis设成boolean类型，则每次可以用“disI,j:=disI,jor(disI,kand disk,j)”来代替算法描述中的蓝色部分，可以更直观地得到I,j的连通情况。与Dijkstra算法类似地，算法中蓝色的部分可以加上对Pre数组的更新，不再赘述。4) 程序：7. Prim1) 适用范围：a) MST(Minimum Spanning Tree,最小生成树)b) 无向图(有向图的是最小树形图)c) 多用于稠密图2) 算法描述：a) 初始化：disv=maxint(vV,vs); diss=0; pres=s; S=s;tot=0b) For i:=1 to n1.取顶点vV-S使得W(u,v)=minW(u,v)|uS,vV-S,(u,v)E2.S=S+v;tot=tot+W(u,v);输出边(u,v)3.For V-S中每个顶点v do Relax(u,v,Wu,v)c) 算法结束：tot为MST的总权值注意：这里的Relax不同于求最短路径时的松弛操作。它的代码如下：procedure relax(u,v,w:integer); /松弛操作begin if wdisv then begin prev:=u; disv:=w; end;end;可以看到，虽然不同，却也十分相似。3) 算法优化：使用二叉堆(Binary Heap)来实现每步的DeleteMin(ExtractMin)操作算法复杂度从O(V2)降到O(V+E)V)。推荐对稀疏图使用。使用Fibonacci Heap可以将复杂度降到O(E+VV)，但因为编程复杂度太高，不推荐在信息学竞赛中使用。（不要问我为什么和Dijkstra一样观察我的prim和dijkstra程序，会发现基本上只有relax和输出不一样）4) 程序：程序二叉堆实现8. Kruskal1) 适用范围：a) MST(Minimum Spanning Tree,最小生成树)b) 无向图(有向图的是最小树形图)c) 多用于稀疏图d) 边已经按权值排好序给出2) 算法描述：基本思想：每次选不属于同一连通分量(保证无圈)且边权值最小的2个顶点，将边加入MST，并将所在的2个连通分量合并，直到只剩一个连通分量3) 算法实现：a) 将边按非降序排列(Quicksort,O(EE)b) While 合并次数少于|V|-1i. 取一条边(u,v)(因为已经排序，所以必为最小)ii. If u,v不属于同一连通分量 then1) 合并u,v所在的连通分量2) 输出边(u,v)3) 合并次数增1；tot=tot+W(u,v)c) 算法结束：tot为MST的总权值4) 分析总结：检查2个顶点是否在同一连通分量可以使用并查集实现(连通分量看作等价类)。我们可以看到，算法主要耗时在将边排序上。如果边已经按照权值顺序给出，那太棒了另外一种可以想到的实现方法为：O(n)时间关于边权建二叉小根堆；每次挑选符合条件的边时使用堆的DelMin操作。这种方法比用Qsort预排序的方法稍微快一些，编程复杂度基本一样。附程序。另外，如果边权有一定限制，即=某常数c，则可以使用线性时间排序以获得更好的时间效率。5) 程序：以上程序使用并查集来检查2个顶点是否在同一连通分量且使用快速排序预处理。以上程序使用并查集来检查2个顶点是否在同一连通分量且使用二叉小根堆的DelMin操作来选边9. 后记写这东西还真是累很久前就开始写，却因为本人的惰性唉。到底二分图和网络流都没有加上。这个总结将不断更新，