几个基本算法

《几个基本算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、(任取(i,j)∈E都有Wij≥0);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，即

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

5、径(从源点s到其它所有顶点v);b)有向图&无向图(无向图可以看作(u,v),(v,u)同属于边集E的有向图);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、

11、有证据，在与Zroge和Amber的讨论中没有能说明。但是，偶尔翻起一本书《DatastructuresandAlgorithmanalysis》，终于确定所谓SPFA就是Bellman-Ford（如果以上算法描述的确是SPFA的描述的话）。如有怀疑可以参考此书，网上有CHM电子书。既然是Bellman-Ford，它的算法复杂度就是O(VE)。而实际上，对于这个所谓“SPFA”是可以很轻易构造出使它复杂度为VE的例子的（有负权回路即可）。以上为我个人说法，有不同观点可以讨论。算法总结——图论菜鱼※QQ：155

12、1751571.TopologicalSort(拓扑排序)1)适用条件&范围：a)AOV网(ActivityOnVertexNetwork);b)有向图;c)作为某些算法的预处理过程(如DP)2)算法描述：很简单的算法：每次挑选入度为0的顶点输出(不计次序)。如果最后发现输出的顶点数小于

13、V

14、，则表明有回路存在3)算法实现：a)数据结构：adj:邻接表;有4个域{u,v,w,next}indgr[i]:顶点i的入度;stack[]:栈b)初始化:top=0(栈顶指针)c)将初始状态所有入度为0的顶点压栈d)I

15、=0(计数器)e)While栈非空(top>0)doi.顶点v出栈；输出v；计数器增1；ii.For与v邻接的顶点udo1.dec(indgr[u]);2.Ifindgr[u]=0then顶点u入栈f)EXIT(I=

16、V

17、)简单&高效&实用的算法。上述实现方法复杂度O(V+E)4)程序：算法总结——图论菜鱼※QQ：1551751571.SSSP(Single-sourceshortestpath)O