图论的基本算法
1.Dijkstra
1) 适用条件&范围：
a) 单源最短路径(从源点s到其它所有顶点v);
b) 有向图&无向图(无向图可以看作(u,v),(v,u)同属于边集E的有向图)
c) 所有边权非负(任取(i,j)∈E都有Wij≥0);
2) 算法描述：
a) 初始化：dis[v]=maxint(v∈V,v≠s); dis[s]=0; pre[s]=s; S={s};
b) For i:=1 to n
1.取V-S中的一顶点u使得dis[u]=min{dis[v]|v∈V-S}
2.S=S+{u}
3.For V-S中每个顶点v do Relax(u,v,Wu,v)
c) 算法结束：dis[i]为s到i的最短距离；pre[i]为i的前驱节点
3) 算法优化：
使用二叉堆(Binary Heap)来实现每步的DeleteMin(ExtractMin，即算法步骤b中第1步)操作，算法复杂度从O(V^2)降到O((V+E)㏒V)。推荐对稀疏图使用。
使用Fibonacci Heap(或其他Decrease操作O(1),DeleteMin操作O(logn)的数据结构)可以将复杂度降到O(E+V㏒V)；如果边权值均为不大于C的正整数，则使用Radix Heap可以达到O(E+V㏒C)。但因为它们编程复杂度太高，不推荐在信息学竞赛中使用。
注：程序使用二叉堆
程序：
program mtx_grp;
const num=10; max=10000;
type
grp=array[1..num,1..num] of integer;
rcd=set of 1..num;
arr=array[1..num] of integer;
arr2=array[1..num] of rcd;
var
i,j,w,m,n,e,k:integer;
g:grp;
visited:array[1..num] of boolean;
path:arr2;
dist,s:arr;
procedure createmtx;
var i,j,k:integer;
begin
for i:=1 to n do
for j:=1 to n do
g[i,j]:=max;
for k:=1 to e do
begin
readln(i,j,w);
g[i,j]:=w;
g[j,i]:=w;
end;
end;
procedure print( g:grp);
begin
for i:=1 to n do
begin
for j:=1 to n do
if g[i,j]=max then write('oo':4)
else write(g[i,j]:4);
writeln;
end;
end;
procedure dijkstra(var dist:arr;var path:arr2;i:integer);
begin
e:=i;
for j:=1 to n do begin
if j<>i then s[j]:=0 else s[j]:=1;
dist[j]:=g[i,j];
if dist[j]<max
then path[j]:=[i]+[j]
else path[j]:=[];
end;
for k:=1 to n-2 do
begin
w:=max;m:=i;
for j:=1 to n do
if (s[j]=0) and (dist[j]<w) then begin m:=j;w:=dist[j];end;
if m<>i then s[m]:=1 else exit;
for j:=1 to n do
if (s[j]=0) and (dist[m]+g[m,j]<dist[j])
then begin
dist[j]:=dist[m]+g[m,j];
path[j]:=path[m]+[j];
end;
end;
for i:=1 to n do
if i<>e then begin
for j:=1 to n do
if j in path[i] then write(j:3);
writeln('w=':4,dist[i]);
end;
end;
begin
assign(input,'nodelst5.in');
reset(input);
readln(n,e);
createmtx;
writeln;
readln(i);
dijkstra(dist,path,i);
writeln;
end.
2.Floyd-Warshall
1) 适用范围：
a) APSP(All Pairs Shortest Paths)
b) 稠密图效果最佳
c) 边权可正可负
2) 算法描述：
a) 初始化：dis[u,v]=w[u,v]
b) 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];
c) 算法结束：dis即为所有点对的最短路径矩阵
3) 算法小结：
此算法简单有效，由于三重循环结构紧凑，对于稠密图，效率要高于执行|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数组的更新，不再赘述。
4) 程序（直接写上的。或许有小错误）
program floyd
var i,j,k,n,m:longint;
leng:array[0..1001,0..1001]of longint;
begin
readln(n);
for i:=1 to n do
begin for j:=1 to n do
read(a[i,j]);
readln;
end;
for k:=1 to n do
for i:=1 to n do
for j:=1 to n do
if leng[i,k]+leng[k,j]<leng[i,j] then
begin
leng[i,j]:=leng[i,k]+leng[k,j];
end;
end.
3.Prim
1) 适用范围：
a) MST(Minimum Spanning Tree,最小生成树)
b) 无向图(有向图的是最小树形图)
c) 多用于稠密图
2) 算法描述：
a) 初始化：dis[v]=maxint(v∈V,v≠s); dis[s]=0; pre[s]=s; S={s};tot=0
b) For i:=1 to n
1.取顶点v∈V-S使得W(u,v)=min{W(u,v)|u∈S,v∈V-S,(u,v)∈E}
2.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 w<dis[v] then
begin
pre[v]:=u;
dis[v]:=w;
end;
end;
可以看到，虽然不同，却也十分相似。
3) 算法优化：
使用二叉堆(Binary Heap)来实现每步的DeleteMin(ExtractMin)操作
算法复杂度从O(V^2)降到O((V+E)㏒V)。推荐对稀疏图使用。
使用Fibonacci Heap可以将复杂度降到O(E+V㏒V)，但因为编程复杂度太高，不推荐在信息学竞赛中使用。
（不要问我为什么和Dijkstra一样……观察我的prim和dijkstra程序，会发现基本上只有relax和输出不一样……）
程序：
program mintree_prim(input);
const
maxn=100;
var
a:array[1..maxn,1..maxn]of integer;
b:array[1..maxn]of boolean;
d:array[1..maxn]of integer;
n,tot,i,j,k,min:integer;
begin
assign(input,'prim.in');
reset(input);
tot:=0;
readln(n);
for i:=1 to n do
b[i]:=true;
b[1]:=false;
for i:=1 to n do
for j:=1 to n do
begin
read(a[i,j]);
if a[i,j]=-1 then
a[i,j]:=maxint;
end;
for i:=2 to n do
d[i]:=a[1,i];
for i:=1 to n-1 do
begin
min:=maxint;
for j:=1 to n do
if(b[j])and(d[j]<min)then
begin
k:=j;
min:=d[j];
end;
tot:=tot+d[k];
b[k]:=false;
for j:=1 to n do
if(b[j])and(d[j]>a[k,j])then
d[j]:=a[k,j];
end;
writeln(tot);
close(input);
end.
4.Topological Sort(拓扑排序)
1) 适用条件&范围：
a) AOV网(Activity On Vertex Network);
b) 有向图;
c) 作为某些算法的预处理过程(如DP)
2) 算法描述：
很简单的算法：每次挑选入度为0的顶点输出(不计次序)。
如果最后发现输出的顶点数小于|V|，则表明有回路存在
3) 算法实现：
a) 数据结构： adj:邻接表;有4个域{u,v,w,next}
indgr[i]:顶点i的入度;
stack[]:栈
b) 初始化:top=0 (栈顶指针)
c) 将初始状态所有入度为0的顶点压栈
d) I=0 (计数器)
e) While 栈非空(top>0) do
i. 顶点v出栈；输出v；计数器增1；
ii. For 与v邻接的顶点u do
1. dec(indgr[u]);
2. If indgr[u]=0 then 顶点u入栈
f) EXIT(I=|V|)
简单&高效&实用的算法。上述实现方法复杂度O(V+E)
4) 程序：
{
有向图的拓扑排序
每次找入度为0的顶点入栈
成功返回true,有环返回false
总复杂度O(n+e)
}
const
maxn=100;
type
link=^node;
node=record
v,w :integer;
next :link;
end;
arr=array[1..maxn]of 1..maxn;
var
adj :array[1..maxn]of link; //邻接表
tsort,indgr :arr; //拓扑序列;入度
n,s,i :integer;
procedure init;
var
u,v,w :integer;
p :link;
begin
assign(input,'g.in');reset(input);
readln(n,s);
while not eof do
begin
readln(u,v,w);
new(p);
p^.v:=v;p^.w:=w; p^.next:=adj[u];
adj[u]:=p; inc(indgr[v])
end;
end;
function toposort(indgr:arr):boolean;
var
i,top :integer;
p :link;
stack :array[1..maxn]of integer;
begin
top:=0;
for i:=1 to n do
if indgr[i]=0 then
begin inc(top); stack[top]:=i end;
i:=0;
while top>0 do
begin
inc(i); tsort[i]:=stack[top]; dec(top);
p:=adj[tsort[i]];
while p<>nil do
begin
dec(indgr[p^.v]);
if indgr[p^.v]=0 then
begin inc(top); stack[top]:=p^.v end;
p:=p^.next;
end;
end;
exit(i=n)
end;
{===========main===========}
begin
init;
if toposort(indgr) then
for i:=1 to n do write(tsort[i],' ')
else writeln('A circle found')
end.
5.Kruskal
1) 适用范围：
a) MST(Minimum Spanning Tree,最小生成树)
b) 无向图(有向图的是最小树形图)
c) 多用于稀疏图
d) 边已经按权值排好序给出
2) 算法描述：
基本思想：每次选不属于同一连通分量(保证无圈)且边权值最小的2个顶点，将边加入MST，并将所在的2个连通分量合并，直到只剩一个连通分量
3) 算法实现：
a) 将边按非降序排列(Quicksort,O(E㏒E))
b) While 合并次数少于|V|-1
i. 取一条边(u,v)(因为已经排序，所以必为最小)
ii. If u,v不属于同一连通分量 then
1) 合并u,v所在的连通分量
2) 输出边(u,v)
3) 合并次数增1；tot=tot+W(u,v)
c) 算法结束：tot为MST的总权值
4) 分析总结：
检查2个顶点是否在同一连通分量可以使用并查集实现(连通分量看作等价类)。
我们可以看到，算法主要耗时在将边排序上。如果边已经按照权值顺序给出，那太棒了……
另外一种可以想到的实现方法为：O(n)时间关于边权建二叉小根堆；每次挑选符合条件的边时使用堆的DelMin操作。这种方法比用Qsort预排序的方法稍微快一些，编程复杂度基本一样。附程序。
另外，如果边权有一定限制，即<=某常数c，则可以使用线性时间排序以获得更好的时间效率。
5) 程序：
program kruskal;
type arr=array[0..100,1..3]of longint;
var
n,m,i,j,k,min,vt:longint;
s,t:array[0..100]of longint;
g:arr;
procedure heap(var r:arr;nn,ii:longint);
var fr,en,i,j,x:longint;
begin
i:=ii;x:=r[i,3];
fr:=r[i,1];en:=r[i,2];j:=2*ii;
while j<=nn do
begin
if (j<nn)and(r[j,3]<r[j+1,3]) then inc(j);
if x<r[j,3] then begin
r[i,3]:=r[j,3];r[i,2]:=r[j,2];r[i,1]:=r[j,1];
i:=j;j:=2*i;
end
else j:=nn+1;
end;
r[i,3]:=x; r[i,2]:=en;r[i,1]:=fr;
end;
begin
assign(input,'kruskal.in');
reset(input);
readln(n,m);
for i:=1 to m do
readln(g[i,1],g[i,2],g[i,3]);
for i:=m div 2 downto 1 do
heap(g,m,i);
for i:= m downto 2 do
begin
k:=g[i,1];g[i,1]:=g[1,1];g[1,1]:=k;
k:=g[i,2];g[i,2]:=g[1,2];g[1,2]:=k;
k:=g[i,3];g[i,3]:=g[1,3];g[1,3]:=k;
heap(g,i-1,1);
end;
fillchar(s,sizeof(s),0);
fillchar(t,sizeof(t),0);
vt:=0;
for i:=1 to n-1 do
begin
min:=maxlongint;
{ k:=0; }
for j:=1 to m do
if s[j]=0 then
if((t[g[j,1]]=0)xor(t[g[j,2]]=0))or(i=1)then
if g[j,3]<min then
begin
min:=g[j,3];
k:=j; break;
end;
s[k]:=1;
t[g[k,1]]:=1;
t[g[k,2]]:=1;
vt:=vt+min;
end;
for i:=1 to m do
if s[i]=1 then
begin
writeln(g[i,1],'->',g[i,2]);
end;
writeln(vt);
end.
来源：
