文档介绍：算法总结——图论 菜鱼※QQ：155175157
一、图论算法
Relaxation(松弛操作)：
procedure relax(u,v,w:integer);//多数情况下不需要单独写成procedure。
begin
i顶点v出栈；输出v；计数器增1；
For 与v邻接的顶点u do
dec(indgr[u]);
If indgr[u]=0 then 顶点u入栈
EXIT(I=|V|)
简单&高效&实用的算法。上述实现方法复杂度O(V+E)
程序：
算法总结——图论 菜鱼※QQ：155175157
SSSP On DAG
适用条件&范围：
DAG(Directed Acyclic Graph,有向无环图);
边权可正可负
算法描述：
Toposort;
If Toposort=False Then HALT(Not a DAG)
For 拓扑序的每个顶点u do
For u的每个邻接点v do
Relax(u,v,w);
算法结束后：如有环则输出错误信息；否则dis[i]为s到i的最短距离，pre[i]为前驱顶点。
算法实现：
基本从略。此算法时间复杂度O(V+E)，时间&编程 复杂度低，如遇到符合条件的题目(DAG)，推荐使用。
还有，此算法的步骤c可以在toposort中实现，这样即减小了此算法复杂度的一个系数。
程序：
算法总结——图论 菜鱼※QQ：155175157
Floyd-Warshall
适用范围：
APSP(All Pairs Shortest Paths)
稠密图效果最佳
边权可正可负
算法描述：
初始化：dis[u,v]=w[u,v]
For k:=1 to n
For i:=1 to n
For j:=1 to n
If dis[i,j]>dis[i,k]+dis[k,j] Then
Dis[I,j]:=dis[I,k]+dis[k,j];
算法结束：dis即为所有点对的最短路径矩阵
算法小结：
此算法简单有效，由于三重循环结构紧凑，对于稠密图，效率要高于执行|V|次Dijkstra算法。时间复杂度O(n^3)。
考虑下列变形：如(I,j)∈E则dis[I,j]初始为1,else初始为0，这样的Floyd算法最后的最短路径矩阵即成为一个判断I,j是否有通路的矩阵。更简单的，我们可以把dis设成boolean类型，则每次可以用“dis[I,j]:=dis[I,j]or(dis[I,k]and dis[k,j])”来代替算法描述中的蓝色部分，可以更直观地得到I,j的连通情况。
与Dijkstra算法类似地，算法中蓝色的部分可以加上对Pre数组的更新，不再赘述。
程序：
算法总结——图论 菜鱼※QQ：155175157
Prim
适用范围：
MST(Minimum Spanning Tree,最小生成树)
无向图(有向图的是最小树形图)
多用于稠密图
算法描述：
初始化：