图论主流算法总结

图论主流算法总结

ID:16296903

大小:131.00 KB

页数:8页

时间:2018-08-09

图论主流算法总结_第1页
图论主流算法总结_第2页
图论主流算法总结_第3页
图论主流算法总结_第4页
图论主流算法总结_第5页
资源描述:

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

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

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。