图论算法.docx
《图论算法.docx》由会员分享，可在线阅读，更多相关《图论算法.docx（13页珍藏版）》请在冰点文库上搜索。
图论算法
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） Fori:
=1ton
1.取V-S中的一顶点u使得dis[u]=min{dis[v]|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）㏒V）。
推荐对稀疏图使用。
使用FibonacciHeap（或其他Decrease操作O
（1）,DeleteMin操作O（logn）的数据结构）可以将复杂度降到O（E+V㏒V）；如果边权值均为不大于C的正整数，则使用RadixHeap可以达到O（E+V㏒C）。
但因为它们编程复杂度太高，不推荐在信息学竞赛中使用。
注：
程序使用二叉堆
程序：
programmtx_grp;
constnum=10;max=10000;
type
grp=array[1..num,1..num]ofinteger;
rcd=setof1..num;
arr=array[1..num]ofinteger;
arr2=array[1..num]ofrcd;
var
i,j,w,m,n,e,k:
integer;
g:
grp;
visited:
array[1..num]ofboolean;
path:
arr2;
dist,s:
arr;
procedurecreatemtx;
vari,j,k:
integer;
begin
fori:
=1tondo
forj:
=1tondo
g[i,j]:
=max;
fork:
=1toedo
begin
readln（i,j,w）;
g[i,j]:
=w;
g[j,i]:
=w;
end;
end;
procedureprint（g:
grp）;
begin
fori:
=1tondo
begin
forj:
=1tondo
ifg[i,j]=maxthenwrite（'oo':
4）
elsewrite（g[i,j]:
4）;
writeln;
end;
end;
proceduredijkstra（vardist:
arr;varpath:
arr2;i:
integer）;
begin
e:
=i;
forj:
=1tondobegin
ifj<>ithens[j]:
=0elses[j]:
=1;
dist[j]:
=g[i,j];
ifdist[j] thenpath[j]:
=[i]+[j]
elsepath[j]:
=[];
end;
fork:
=1ton-2do
begin
w:
=max;m:
=i;
forj:
=1tondo
if（s[j]=0）and（dist[j]=j;w:
=dist[j];end;
ifm<>ithens[m]:
=1elseexit;
forj:
=1tondo
if（s[j]=0）and（dist[m]+g[m,j] thenbegin
dist[j]:
=dist[m]+g[m,j];
path[j]:
=path[m]+[j];
end;
end;
fori:
=1tondo
ifi<>ethenbegin
forj:
=1tondo
ifjinpath[i]thenwrite（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（AllPairsShortestPaths）
b） 稠密图效果最佳
c） 边权可正可负
2） 算法描述：
a） 初始化：
dis[u,v]=w[u,v]
b） Fork:
=1ton
Fori:
=1ton
Forj:
=1ton
Ifdis[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]anddis[k,j]）”来代替算法描述中的蓝色部分，可以更直观地得到I,j的连通情况。
与Dijkstra算法类似地，算法中蓝色的部分可以加上对Pre数组的更新，不再赘述。
4） 程序（直接写上的。
或许有小错误）
programfloyd
vari,j,k,n,m:
longint;
leng:
array[0..1001,0..1001]oflongint;
begin
readln（n）;
fori:
=1tondo
beginforj:
=1tondo
read（a[i,j]）;
readln;
end;
fork:
=1tondo
fori:
=1tondo
forj:
=1tondo
ifleng[i,k]+leng[k,j]begin
leng[i,j]:
=leng[i,k]+leng[k,j];
end;
end.
3.Prim
1） 适用范围：
a） MST（MinimumSpanningTree,最小生成树）
b） 无向图（有向图的是最小树形图）
c） 多用于稠密图
2） 算法描述：
a） 初始化：
dis[v]=maxint（v∈V,v≠s）;dis[s]=0;pre[s]=s;S={s};tot=0
b） Fori:
=1ton
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.ForV-S中每个顶点vdoRelax（u,v,Wu,v）
c） 算法结束：
tot为MST的总权值
注意：
这里的Relax不同于求最短路径时的松弛操作。
它的代码如下：
procedurerelax（u,v,w:
integer）;//松弛操作
begin
ifwbegin
pre[v]:
=u;
dis[v]:
=w;
end;
end;
可以看到，虽然不同，却也十分相似。
3） 算法优化：
使用二叉堆（BinaryHeap）来实现每步的DeleteMin（ExtractMin）操作
算法复杂度从O（V^2）降到O（（V+E）㏒V）。
推荐对稀疏图使用。
使用FibonacciHeap可以将复杂度降到O（E+V㏒V），但因为编程复杂度太高，不推荐在信息学竞赛中使用。
（不要问我为什么和Dijkstra一样……观察我的prim和dijkstra程序，会发现基本上只有relax和输出不一样……）
程序：
programmintree_prim（input）;
const
maxn=100;
var
a:
array[1..maxn,1..maxn]ofinteger;
b:
array[1..maxn]ofboolean;
d:
array[1..maxn]ofinteger;
n,tot,i,j,k,min:
integer;
begin
assign（input,'prim.in'）;
reset（input）;
tot:
=0;
readln（n）;
fori:
=1tondo
b[i]:
=true;
b[1]:
=false;
fori:
=1tondo
forj:
=1tondo
begin
read（a[i,j]）;
ifa[i,j]=-1then
a[i,j]:
=maxint;
end;
fori:
=2tondo
d[i]:
=a[1,i];
fori:
=1ton-1do
begin
min:
=maxint;
forj:
=1tondo
if（b[j]）and（d[j] begin
k:
=j;
min:
=d[j];
end;
tot:
=tot+d[k];
b[k]:
=false;
forj:
=1tondo
if（b[j]）and（d[j]>a[k,j]）then
d[j]:
=a[k,j];
end;
writeln（tot）;
close（input）;
end.
4.TopologicalSort（拓扑排序）
1） 适用条件&范围：
a） AOV网（ActivityOnVertexNetwork）;
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邻接的顶点udo
1. dec（indgr[u]）;
2. Ifindgr[u]=0then顶点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]of1..maxn;
var
adj :
array[1..maxn]oflink; //邻接表
tsort,indgr :
arr; //拓扑序列;入度
n,s,i :
integer;
procedureinit;
var
u,v,w:
integer;
p :
link;
begin
assign（input,'g.in'）;reset（input）;
readln（n,s）;
whilenoteofdo
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;
functiontoposort（indgr:
arr）:
boolean;
var
i,top :
integer;
p :
link;
stack :
array[1..maxn]ofinteger;
begin
top:
=0;
fori:
=1tondo
ifindgr[i]=0then
begininc（top）;stack[top]:
=iend;
i:
=0;
whiletop>0do
begin
inc（i）;tsort[i]:
=stack[top];dec（top）;
p:
=adj[tsort[i]];
whilep<>nildo
begin
dec（indgr[p^.v]）;
ifindgr[p^.v]=0then
begininc（top）;stack[top]:
=p^.vend;
p:
=p^.next;
end;
end;
exit（i=n）
end;
{===========main===========}
begin
init;
iftoposort（indgr）then
fori:
=1tondowrite（tsort[i],''）
elsewriteln（'Acirclefound'）
end.
5.Kruskal
1） 适用范围：
a） MST（MinimumSpanningTree,最小生成树）
b） 无向图（有向图的是最小树形图）
c） 多用于稀疏图
d） 边已经按权值排好序给出
2） 算法描述：
基本思想：
每次选不属于同一连通分量（保证无圈）且边权值最小的2个顶点，将边加入MST，并将所在的2个连通分量合并，直到只剩一个连通分量
3） 算法实现：
a） 将边按非降序排列（Quicksort,O（E㏒E））
b） While合并次数少于|V|-1
i. 取一条边（u,v）（因为已经排序，所以必为最小）
ii. Ifu,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） 程序：
programkruskal;
typearr=array[0..100,1..3]oflongint;
var
n,m,i,j,k,min,vt:
longint;
s,t:
array[0..100]oflongint;
g:
arr;
procedureheap（varr:
arr;nn,ii:
longint）;
varfr,en,i,j,x:
longint;
begin
i:
=ii;x:
=r[i,3];
fr:
=r[i,1];en:
=r[i,2];j:
=2*ii;
whilej<=nndo
begin
if（j if x r[i,3]:
=r[j,3];r[i,2]:
=r[j,2];r[i,1]:
=r[j,1];
i:
=j;j:
=2*i;
end
elsej:
=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）;
fori:
=1tomdo
readln（g[i,1],g[i,2],g[i,3]）;
fori:
=mdiv2downto1do
heap（g,m,i）;
fori:
=mdownto2do
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;
fori:
=1ton-1do
begin
min:
=maxlongint;
{ k:
=0; }
forj:
=1tomdo
ifs[j]=0then
if（（t[g[j,1]]=0）xor（t[g[j,2]]=0））or（i=1）then
ifg[j,3] 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;
fori:
=1tomdo
ifs[i]=1then
begin
writeln（g[i,1],'->',g[i,2]）;
end;
writeln（vt）;
end.
升级会员 