图论主流算法总结

《图论主流算法总结》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、算法总结——图论菜鱼※QQ：155175157一、图论算法1.Relaxation(松弛操作)：procedurerelax(u,v,w:integer);//多数情况下不需要单独写成procedure。beginifdis[u]+w

2、);2)算法描述：a)初始化：dis[v]=maxint(v∈V,v≠s);dis[s]=0;pre[s]=s;S={s};b)Fori:=1ton1.取V-S中的一顶点u使得dis[u]=min{dis[v]

3、v∈V-S}2.S=S+{u}3.ForV-S中每个顶点vdoRelax(u,v,Wu,v)c)算法结束：dis[i]为s到i的最短距离；pre[i]为i的前驱节点3)算法优化：使用二叉堆(BinaryHeap)来实现每步的DeleteMin(ExtractMin，即算法步骤b中第1步)操作，算法复杂度从O(V^2)降到O((V+E)

4、㏒V)。推荐对稀疏图使用。使用FibonacciHeap(或其他Decrease操作O(1),DeleteMin操作O(logn)的数据结构)可以将复杂度降到O(E+V㏒V)；如果边权值均为不大于C的正整数，则使用RadixHeap可以达到O(E+V㏒C)。但因为它们编程复杂度太高，不推荐在信息学竞赛中使用。4)程序：注：程序使用二叉堆算法总结——图论菜鱼※QQ：1551751571.Bellman-Ford1)适用条件&范围：a)单源最短路径(从源点s到其它所有顶点v);b)有向图&无向图(无向图可以看作(u,v),(v,u)同属于边集E的

5、有向图);c)边权可正可负(如有负权回路输出错误提示);d)差分约束系统;2)算法描述：对每条边进行

6、V

7、次Relax操作;完成后，如果存在(u,v)∈E使得dis[u]+w

8、V

9、doFor每条边(u,v)∈EdoRelax(u,v,w);For每条边(u,v)∈EdoIfdis[u]+w

10、错，仍不失为一个很实用的算法。4)程序：5)菜鱼有话说：这个……N久前有人提出个叫“SPFA”的东西，主要思想是：维护一队列，对队头的顶点u，枚举它的邻接边，如果它可以用来更新顶点v，则更新v的dis。更新后，如果顶点不在队中，则加入队。重复，直至队列空。有人说这个算法是O(kE)，k平均为2。看完算法的描述，我直观上就感觉这是bellman-ford的一种实现方式，但无奈没有证据，在与Zroge和Amber的讨论中没有能说明。但是，偶尔翻起一本书《DatastructuresandAlgorithmanalysis》，终于确定所谓SPFA就

11、是Bellman-Ford（如果以上算法描述的确是SPFA的描述的话）。如有怀疑可以参考此书，网上有CHM电子书。既然是Bellman-Ford，它的算法复杂度就是O(VE)。而实际上，对于这个所谓“SPFA”是可以很轻易构造出使它复杂度为VE的例子的（有负权回路即可）。以上为我个人说法，有不同观点可以讨论。算法总结——图论菜鱼※QQ：1551751571.TopologicalSort(拓扑排序)1)适用条件&范围：a)AOV网(ActivityOnVertexNetwork);b)有向图;c)作为某些算法的预处理过程(如DP)2)算法描述

12、：很简单的算法：每次挑选入度为0的顶点输出(不计次序)。如果最后发现输出的顶点数小于

13、V

14、，则表明有回路存在3)算法实现：a)数据结构：adj:邻接表;有4个域{u,v,w,next}indgr[i]:顶点i的入度;stack[]:栈b)初始化:top=0(栈顶指针)c)将初始状态所有入度为0的顶点压栈d)I=0(计数器)e)While栈非空(top>0)doi.顶点v出栈；输出v；计数器增1；ii.For与v邻接的顶点udo1.dec(indgr[u]);2.Ifindgr[u]=0then顶点u入栈f)EXIT(I=

15、V

16、)简单&高效&实

17、用的算法。上述实现方法复杂度O(V+E)4)程序：算法总结——图论菜鱼※QQ：1551751571.SSSPOnDAG1)适用条件&范围：a)DAG(Directe