图论算法Word格式.docx
《图论算法Word格式.docx》由会员分享，可在线阅读，更多相关《图论算法Word格式.docx（13页珍藏版）》请在冰点文库上搜索。
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:
begin
fori:
=1tondo
forj:
g[i,j]:
=max;
fork:
=1toedo
begin
readln（i,j,w）;
=w;
g[j,i]:
end;
end;
procedureprint（g:
grp）;
ifg[i,j]=maxthenwrite（'
oo'
:
4）
elsewrite（g[i,j]:
4）;
writeln;
proceduredijkstra（vardist:
varpath:
i:
integer）;
e:
=i;
=1tondobegin
ifj<
>
ithens[j]:
=0elses[j]:
=1;
dist[j]:
=g[i,j];
ifdist[j]<
max
thenpath[j]:
=[i]+[j]
elsepath[j]:
=[];
=1ton-2do
w:
m:
if（s[j]=0）and（dist[j]<
w）thenbeginm:
=j;
w:
=dist[j];
ifm<
ithens[m]:
=1elseexit;
if（s[j]=0）and（dist[m]+g[m,j]<
dist[j]）
thenbegin
=dist[m]+g[m,j];
path[j]:
=path[m]+[j];
ifi<
ethenbegin
ifjinpath[i]thenwrite（j:
3）;
writeln（'
w='
4,dist[i]）;
assign（input,'
nodelst5.in'
）;
reset（input）;
readln（n,e）;
createmtx;
readln（i）;
dijkstra（dist,path,i）;
end.
2.Floyd-Warshall
适用范围：
APSP（AllPairsShortestPaths）
稠密图效果最佳
边权可正可负
dis[u,v]=w[u,v]
Fork:
Fori:
Forj:
Ifdis[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]anddis[k,j]）”来代替算法描述中的蓝色部分，可以更直观地得到I,j的连通情况。
与Dijkstra算法类似地，算法中蓝色的部分可以加上对Pre数组的更新，不再赘述。
4）
程序（直接写上的。
或许有小错误）
programfloyd
vari,j,k,n,m:
longint;
leng:
array[0..1001,0..1001]oflongint;
readln（n）;
fori:
beginforj:
read（a[i,j]）;
readln;
ifleng[i,k]+leng[k,j]<
leng[i,j]then
leng[i,j]:
=leng[i,k]+leng[k,j];
3.Prim
MST（MinimumSpanningTree,最小生成树）
无向图（有向图的是最小树形图）
多用于稠密图
tot=0
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）
tot为MST的总权值
注意：
这里的Relax不同于求最短路径时的松弛操作。
它的代码如下：
procedurerelax（u,v,w:
//松弛操作
ifw<
dis[v]then
pre[v]:
=u;
dis[v]:
可以看到，虽然不同，却也十分相似。
使用二叉堆（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;
a:
array[1..maxn,1..maxn]ofinteger;
b:
array[1..maxn]ofboolean;
d:
array[1..maxn]ofinteger;
n,tot,i,j,k,min:
prim.in'
tot:
=0;
readln（n）;
b[i]:
=true;
b[1]:
=false;
read（a[i,j]）;
ifa[i,j]=-1then
a[i,j]:
=maxint;
=2tondo
d[i]:
=a[1,i];
=1ton-1do
min:
if（b[j]）and（d[j]<
min）then
k:
=d[j];
=tot+d[k];
b[k]:
if（b[j]）and（d[j]>
a[k,j]）then
d[j]:
=a[k,j];
writeln（tot）;
close（input）;
4.TopologicalSort（拓扑排序）
AOV网（ActivityOnVertexNetwork）;
有向图;
作为某些算法的预处理过程（如DP）
很简单的算法：
每次挑选入度为0的顶点输出（不计次序）。
如果最后发现输出的顶点数小于|V|，则表明有回路存在
算法实现：
数据结构：
adj:
邻接表;
有4个域{u,v,w,next}
indgr[i]:
顶点i的入度;
stack[]:
栈
初始化:
top=0（栈顶指针）
将初始状态所有入度为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）
程序：
{
有向图的拓扑排序
每次找入度为0的顶点入栈
成功返回true,有环返回false
总复杂度O（n+e）
}
maxn=100;
link=^node;
node=record
v,w
:
next
link;
arr=array[1..maxn]of1..maxn;
adj
array[1..maxn]oflink;
//邻接表
tsort,indgr
//拓扑序列;
入度
n,s,i
procedureinit;
u,v,w:
p
g.in'
reset（input）;
readln（n,s）;
whilenoteofdo
readln（u,v,w）;
new（p）;
p^.v:
=v;
p^.w:
p^.next:
=adj[u];
adj[u]:
=p;
inc（indgr[v]）
functiontoposort（indgr:
arr）:
boolean;
i,top
stack
top:
ifindgr[i]=0then
begininc（top）;
stack[top]:
=iend;
i:
whiletop>
0do
inc（i）;
tsort[i]:
=stack[top];
dec（top）;
p:
=adj[tsort[i]];
whilep<
nildo
dec（indgr[p^.v]）;
ifindgr[p^.v]=0then
=p^.vend;
=p^.next;
exit（i=n）
{===========main===========}
init;
iftoposort（indgr）then
=1tondowrite（tsort[i],'
'
）
elsewriteln（'
Acirclefound'
5.Kruskal
多用于稀疏图
边已经按权值排好序给出
基本思想：
每次选不属于同一连通分量（保证无圈）且边权值最小的2个顶点，将边加入MST，并将所在的2个连通分量合并，直到只剩一个连通分量
将边按非降序排列（Quicksort,O（E㏒E））
While合并次数少于|V|-1
取一条边（u,v）（因为已经排序，所以必为最小）
Ifu,v不属于同一连通分量then
合并u,v所在的连通分量
输出边（u,v）
合并次数增1；
tot=tot+W（u,v）
分析总结：
检查2个顶点是否在同一连通分量可以使用并查集实现（连通分量看作等价类）。
我们可以看到，算法主要耗时在将边排序上。
如果边已经按照权值顺序给出，那太棒了……
另外一种可以想到的实现方法为：
O（n）时间关于边权建二叉小根堆；
每次挑选符合条件的边时使用堆的DelMin操作。
这种方法比用Qsort预排序的方法稍微快一些，编程复杂度基本一样。
附程序。
另外，如果边权有一定限制，即<
=某常数c，则可以使用线性时间排序以获得更好的时间效率。
5）
programkruskal;
typearr=array[0..100,1..3]oflongint;
n,m,i,j,k,min,vt:
s,t:
array[0..100]oflongint;
procedureheap（varr:
nn,ii:
longint）;
varfr,en,i,j,x:
=ii;
x:
=r[i,3];
fr:
=r[i,1];
en:
=r[i,2];
j:
=2*ii;
whilej<
=nndo
if（j<
nn）and（r[j,3]<
r[j+1,3]）theninc（j）;
if
x<
r[j,3]thenbegin
r[i,3]:
=r[j,3];
r[i,2]:
=r[j,2];
r[i,1]:
=r[j,1];
=2*i;
end
elsej:
=nn+1;
=x;
r[i,2]:
=en;
=fr;
assign（input,'
kruskal.in'
readln（n,m）;
=1tomdo
readln（g[i,1],g[i,2],g[i,3]）;
=mdiv2downto1do
heap（g,m,i）;
=mdownto2do
=g[i,1];
g[i,1]:
=g[1,1];
g[1,1]:
=k;
=g[i,2];
g[i,2]:
=g[1,2];
g[1,2]:
=g[i,3];
g[i,3]:
=g[1,3];
g[1,3]:
heap（g,i-1,1）;
fillchar（s,sizeof（s）,0）;
fillchar（t,sizeof（t）,0）;
vt:
=maxlongint;
{
}
ifs[j]=0then
if（（t[g[j,1]]=0）xor（t[g[j,2]]=0））or（i=1）then
ifg[j,3]<
minthen
=g[j,3];
break;
s[k]:
t[g[k,1]]:
t[g[k,2]]:
=vt+min;
ifs[i]=1then
writeln（g[i,1],'
->
'
g[i,2]）;
writeln（vt）;
升级会员 