经典图论算法.docx
《经典图论算法.docx》由会员分享，可在线阅读，更多相关《经典图论算法.docx（38页珍藏版）》请在冰点文库上搜索。
经典图论算法
图论中的常用经典算法
第一节最小生成树算法
一、生成树的概念
若图是连通的无向图或强连通的有向图，则从其中任一个顶点出发调用一次bfs或dfs后便可以系统地访问图中所有顶点；若图是有根的有向图，则从根出发通过调用一次dfs或bfs亦可系统地访问所有顶点。
在这种情况下，图中所有顶点加上遍历过程中经过的边所构成的子图称为原图的生成树。
对于不连通的无向图和不是强连通的有向图，若有根或者从根外的任意顶点出发，调用一次bfs或dfs后不能系统地访问所有顶点，而只能得到以出发点为根的连通分支（或强连通分支）的生成树。
要访问其它顶点则还需要从没有访问过的顶点中找一个顶点作为起始点，再次调用bfs或dfs，这样得到的是生成森林。
由此可以看出，一个图的生成树是不唯一的，不同的搜索方法可以得到不同的生成树，即使是同一种搜索方法，出发点不同亦可导致不同的生成树。
如下图：
但不管如何，我们都可以证明：
具有n个顶点的带权连通图，其对应的生成树有n-1条边。
二、求图的最小生成树算法
严格来说，如果图G=（V，E）是一个连通的无向图，则把它的全部顶点V和一部分边E’构成一个子图G’，即G’=（V，E’），且边集E’能将图中所有顶点连通又不形成回路，则称子图G’是图G的一棵生成树。
对于加权连通图，生成树的权即为生成树中所有边上的权值总和，权值最小的生成树称为图的最小生成树。
求图的最小生成树具有很高的实际应用价值，比如下面的这个例题。
例1、城市公交网
[问题描述]
有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权为在这两个城市之间修建高速公路的造价，研究后发现，这个地图有一个特点，即任一对城市都是连通的。
现在的问题是，要修建若干高速公路把所有城市联系起来，问如何设计可使得工程的总造价最少。
[输入]
n（城市数，1<=n<=100）
e（边数）
以下e行，每行3个数i,j,wij，表示在城市i,j之间修建高速公路的造价。
[输出]
n-1行，每行为两个城市的序号，表明这两个城市间建一条高速公路。
[举例]
下面的图（A）表示一个5个城市的地图，图（B）、（C）是对图（A）分别进行深度优先遍历和广度优先遍历得到的一棵生成树，其权和分别为20和33，前者比后者好一些，但并不是最小生成树，最小生成树的权和为19。
[问题分析]
出发点：
具有n个顶点的带权连通图，其对应的生成树有n-1条边。
那么选哪n-1条边呢？
设图G的度为n，G=（V，E），我们介绍两种基于贪心的算法，Prim算法和Kruskal算法。
1、用Prim算法求最小生成树的思想如下：
①设置一个顶点的集合S和一个边的集合TE，S和TE的初始状态均为空集；
②选定图中的一个顶点K，从K开始生成最小生成树，将K加入到集合S；
③重复下列操作，直到选取了n-1条边：
选取一条权值最小的边（X，Y），其中X∈S，not（Y∈S）；
将顶点Y加入集合S，边（X，Y）加入集合TE；
④得到最小生成树T=（S，TE）
上图是按照Prim算法，给出了例题中的图（A）最小生成树的生成过程（从顶点1开始）。
其中图（E）中的4条粗线将5个顶点连通成了一棵最小生成树。
Prim算法的正确性可以通过反证法证明。
因为操作是沿着边进行的，所以数据结构采用边集数组表示法，下面给出Prim算法构造图的最小生成树的具体算法框架。
①从文件中读入图的邻接矩阵g；
②边集数组elist初始化；
Fori:
=1Ton-1Do
Begin
elist[i].fromv:
=1；elist[i].endv:
=i+1；elist[i].weight:
=g[1,i+1]；
End；
③求出最小生成树的n-1条边；
Fork:
=1Ton-1Do
Begin
min:
=maxint；m:
=k；
Forj:
=kTon-1Do{查找权值最小的一条边}
Ifelist[j].weight=elist[j].weight；m:
=j；End；
Ifm<>kThenBegint:
=elist[k]；elist[k]:
=elist[m]；elist[m]:
=t；End；
{把权值最小的边调到第k个单元}
j:
=elist[k].endv；{j为新加入的顶点}
Fori:
=k+1Ton-1Do{修改未加入的边集}
Begins:
=elist[i].endv；w:
=g[j,s]；
IfwThenBeginelist[i].weight:
=w；elist[i].fromv:
=j；End；
End；
End；
④输出；
2、用Kruskal算法求最小生成树的思想如下：
设最小生成树为T=（V，TE），设置边的集合TE的初始状态为空集。
将图G中的边按权值从小到大排好序，然后从小的开始依次选取，若选取的边使生成树T不形成回路，则把它并入TE中，保留作为T的一条边；若选取的边使生成树形成回路，则将其舍弃；如此进行下去，直到TE中包含n-1条边为止。
最后的T即为最小生成树。
如何证明呢？
下图是按照Kruskal算法给出了例题中图（A）最小生成树的生成过程：
Kruskal算法在实现过程中的关键和难点在于：
如何判断欲加入的一条边是否与生成树中已保留的边形成回路？
我们可以将顶点划分到不同的集合中，每个集合中的顶点表示一个无回路的连通分量，很明显算法开始时，把所有n个顶点划分到n个集合中，每个集合只有一个顶点，表明顶点之间互不相通。
当选取一条边时，若它的两个顶点分属于不同的集合，则表明此边连通了两个不同的连通分量，因每个连通分量无回路，所以连通后得到的连通分量仍不会产生回路，因此这条边应该保留，且把它们作为一个连通分量，即把它的两个顶点所在集合合并成一个集合。
如果选取的一条边的两个顶点属于同一个集合，则此边应该舍弃，因为同一个集合中的顶点是连通无回路的，若再加入一条边则必然产生回路。
下面给出利用Kruskal算法构造图的最小生成树的具体算法框架。
1将图的存储结构转换成边集数组表示的形式elist，并按照权值从小到大排好序；
2设数组C[1..n-1]用来存储最小生成树的所有边，C[i]是第i次选取的可行边在排好序的elist中的下标；
③设一个数组S[1..n]，S[i]都是集合，初始时S[i]=[i]。
i:
=1；{获取的第i条最小生成树的边}
j:
=1；{边集数组的下标}
Whilei<=n-1Do
Begin
Fork:
=1TonDoBegin{取出第j条边，记下两个顶点分属的集合序号}
Ifelist[j].fromvins[k]Thenm1:
=k；
Ifelist[j].endvins[k]Thenm2:
=k；
End；
Ifm1<>m2ThenBegin{找到的elist第j条边满足条件，作为第i条边保留}
C[i]:
=j；
i:
=i+1；
s[m1]:
=s[m1]+s[m2]；{合并两个集合}
s[m2]:
=[]；{另一集合置空}
End；
j:
=j+1；{取下条边，继续判断}
End；
④输出最小生成树的各边：
elist[C[i]]
3、总结
以上两个算法的时间复杂度均为O（n*n）。
参考程序见Prim.pas和Kruskal.pas。
请大家用以上两种算法完成例1。
三、应用举例
例2、最优布线问题（wire.pas，wire.exe）
[问题描述]
学校有n台计算机，为了方便数据传输，现要将它们用数据线连接起来。
两台计算机被连接是指它们时间有数据线连接。
由于计算机所处的位置不同，因此不同的两台计算机的连接费用往往是不同的。
当然，如果将任意两台计算机都用数据线连接，费用将是相当庞大的。
为了节省费用，我们采用数据的间接传输手段，即一台计算机可以间接的通过若干台计算机（作为中转）来实现与另一台计算机的连接。
现在由你负责连接这些计算机，你的任务是使任意两台计算机都连通（不管是直接的或间接的）。
[输入格式]
输入文件wire.in，第一行为整数n（2<=n<=100），表示计算机的数目。
此后的n行，每行n个整数。
第x+1行y列的整数表示直接连接第x台计算机和第y台计算机的费用。
[输出格式]
输出文件wire.out，一个整数，表示最小的连接费用。
[样例输入]
3
012
101
210
[样例输出]
2（注：
表示连接1和2，2和3，费用为2）
[问题分析]
本题是典型的求图的最小生成树问题，我们可以利用Prim算法或者Kruskal算法求出，下面的程序在数据结构上对Kruskal算法做了一点修改，具体细节请看程序及注解。
[参考程序]
Programwire（Input,Output）；
varg:
Array[1..100,1..100]OfInteger；{邻接矩阵}
l:
Array[0..100]OfInteger；{l[i]存放顶点i到当前已建成的生成树中
任意一顶点j的权值g[i,j]的最小值}
u:
Array[0..100]OfBoolean；{u[i]=True，表示顶点i还未加入到生成树中；
u[i]=False，表示顶点I已加入到生成树中}
n,i,j,k,total:
Integer；
Begin
Assign（Input,'wire.in'）；
Reset（Input）；
Assign（Output,'wire.out'）；
Rewrite（Output）；
Readln（n）；
Fori:
=1TonDoBegin
Forj:
=1TonDoRead（g[i，j]）；
Readln；
End；
Fillchar（l,sizeof（l）,$7F）；{初始化为maxint}
l[1]:
=0；{开始时生成树中只有第1个顶点}
Fillchar（u,sizeof（u）,1）；{初始化为True，表示所有顶点均未加入}
Fori:
=1TonDo
Begin
k:
=0；
Forj:
=1TonDo{找一个未加入到生成树中的顶点，记为k，
要求k到当前生成树中所有顶点的代价最小}
Ifu[j]And（l[j]=j；
u[k]:
=False；{顶点k加入生成树}
Forj:
=1TonDo{找到生成树中的顶点j，要求g[k,j]最小}
Ifu[j]And（g[k，j]=g[k，j]；
End；
total:
=0；
Fori:
=1TonDoInc（total,l[i]）；{累加}
Writeln（total）；
Close（Input）；
Close（Output）；
End.
第二节最短路径算法
最短路径是图论中的一个重要问题，具有很高的实用价值，也是信息学竞赛中常见的一类中等难度的题目，这类问题很能联系实际，考察学生的建模能力，反映出学生的创造性思维，
因为有些看似跟最短路径毫无关系的问题也可以归结为最短路径问题来求解。
本文就简要分析一下此类问题的模型、特点和常用算法。
在带权图G=（V，E）中，若顶点Vi,Vj是图G的两个顶点，从顶点Vi到Vj的路径长度定义为路径上各条边的权值之和。
从顶点Vi到Vj可能有多条路径，其中路径长度最小的一条路径称为顶点Vi到Vj的最短路径。
一般有两类最短路径问题：
一类是求从某个顶点（源点）到其它顶点（终点）的最短路径；另一类是求图中每一对顶点间的最短路径。
对于不带权的图，只要人为的把每条边加上权值1，即可当作带权图一样处理了。
例1、假设A、B、C、D、E各个城市之间旅费如下图所示。
某人想从城市A出发游览各城市一遍，而所用旅费最少，试编程输出结果。
[问题分析]
解这类问题时，很多同学往往不得要领，采用穷举法把所有可能的情况全部列出，再找出其中旅费最少的那条路径；或者采用递归（深搜）找出所有路径，再找出旅费最少的那条。
但这两种方法都是费时非常多的解法，如果城市数目多的话则很可能要超时了。
实际上我们知道，递归（深搜）之类的算法一般用于求所有解问题（例如求从A出发每个城市都要走一遍一共有哪几种走法？
），所以这些算法对于求最短路径这类最优解问题显然是不合适的。
首先，对于这类图，我们都应该先建立一个邻接矩阵，存放任意两点间的数据（距离、费用、时间等），以便在程序中方便调用，上图的邻接矩阵如下：
constdis:
array[1..5,1..5]ofinteger=（（0,7,3,10,15）,
（7,0,5,13,12）,
（3,5,0,6,5）,
（10,13,6,0,11）,
（15,12,5,11,0））；
以下介绍几种常见的、更好的算法。
一、宽度优先搜索
宽搜也并不是解决这类问题的优秀算法，这里只是简单介绍一下算法思路，为后面的优秀算法做个铺垫。
具体如下：
1、从A点开始依次展开得到AB、AC、AD、AE四个新结点（第二层结点），当然每个新结点要记录下其旅费；
2、再次由AB展开得到ABC、ABD、ABE三个新结点（第三层结点），而由AC结点可展开得到ACB、ACD、ACE三个新结点，自然由AD可以展开得到ADB、ADC、ADE，由AE可以展开得到AEB、AEC、AED等新结点，对于每个结点也须记录下其旅费；
3、再把第三层结点全部展开，得到所有的第四层结点：
ABCD、ABCE、ABDC、ABDE、ABEC、ABED、……、AEDB、AEDC，每个结点也需记录下其旅费；
4、再把第四层结点全部展开，得到所有的第五层结点：
ABCDE、ABCED、……、AEDBC、AEDCB，每个结点也需记录下其旅费；
5、到此，所有可能的结点均已展开，而第五层结点中旅费最少的那个就是题目的解了。
由上可见，这种算法也是把所有的可能路径都列出来，再从中找出旅费最少的那条，显而易见也是一种很费时的算法。
二、A＊算法
A＊算法是在宽度优先搜索算法的基础上，每次并不是把所有可展开的结点展开，而是对所有没有展开的结点，利用一个自己确定的估价函数对所有没展开的结点进行估价，从而找出最应该被展开的结点（也就是说我们要找的答案最有可能是从该结点展开），而把该结点展开，直到找到目标结点为止。
这种算法最关键的问题就是如何确定估价函数，估价函数越准，则能越快找到答案。
A＊算法实现起来并不难，只不过难在找准估价函数，大家可以自已找相关资料学习A*算法。
三、等代价搜索法
等代价搜索法也是在宽度优先搜索的基础上进行了部分优化的一种算法，它与A＊算法的相似之处都是每次只展开某一个结点（不是展开所有结点），不同之处在于：
它不需要去另找专门的估价函数，而是以该结点到A点的距离作为估价值，也就是说，等代价搜索法是A＊算法的一种简化版本。
它的大体思路是：
1、从A点开始依次展开得到AB（7）、AC（3）、AD（10）、AE（15）四个新结点，把第一层结点A标记为已展开，并且每个新结点要记录下其旅费（括号中的数字）；
2、把未展开过的AB、AC、AD、AE四个结点中距离最小的一个展开，即展开AC（3）结点，得到ACB（8）、ACD（16）、ACE（13）三个结点，并把结点AC标记为已展开；
3、再从未展开的所有结点中找出距离最小的一个展开，即展开AB（7）结点，得到ABC（12）、ABD（20）、ABE（19）三个结点，并把结点AB标记为已展开；
4、再次从未展开的所有结点中找出距离最小的一个展开，即展开ACB（8）结点，……；
5、每次展开所有未展开的结点中距离最小的那个结点，直到展开的新结点中出现目标情况（结点含有5个字母）时，即得到了结果。
由上可见，A＊算法和等代价搜索法并没有象宽度优先搜索一样展开所有结点，只是根据某一原则（或某一估价函数值）每次展开距离A点最近的那个结点（或是估价函数计算出的最可能的那个结点），反复下去即可最终得到答案。
虽然中途有时也展开了一些并不是答案的结点，但这种展开并不是大规模的，不是全部展开，因而耗时要比宽度优先搜索小得多。
例2、题目基本同例1，现在把权定义成距离，现在要求A点到E点的最短路径，但并不要求每个城市都要走一遍。
[问题分析]
既然不要求每个点都要走一遍，只要距离最短即可，那么普通的宽度优先搜索已经没有什么意义了，实际上就是穷举。
那么等代价搜索能不能再用在这题上呢？
答案是肯定的，但到底搜索到什么时候才能得到答案呢？
这可是个很荆手的问题。
是不是搜索到一个结点是以E结束时就停止呢？
显然不对。
那么是不是要把所有以E为结束的结点全部搜索出来呢？
这简直就是宽度优先搜索了，显然不对。
实际上，应该是搜索到：
当我们确定将要展开的某个结点（即所有未展开的结点中距离最小的那个点）的最后一个字母是E时，这个结点就是我们所要求的答案！
因为比这个结点大的点再展开得到的解显然不可能比这个结点优！
那么，除了等代价搜索外，有没有其它办法了呢？
下面就介绍这种求最短路径问题的其它几种成熟算法。
四、宽度优先搜索+剪枝
搜索之所以低效，是因为在搜索过程中存在着大量的重复和不必要的搜索。
因此，提高搜索效率的关键在于减少无意义的搜索。
假如在搜索时已经搜出从起点A到点B的某一条路径的长度是X，那么我们就可以知道，从A到B的最短路径长度必定≤X，因此，其他从A到B的长度大于或等于X的路径可以一律剔除。
具体实现时，可以开一个数组h[1..n]，n是结点总数，h[i]表示从起点到结点i的最短路径长度。
算法流程如下：
1、初始化：
将起点start入队，h[start]:
=0，h[k]:
=maxlongint（1<=k<=n，且k≠start）。
2、repeat
取出队头结点赋给t；
whilet有相邻的结点没被扩展
begin
t扩展出新的结点newp；
如果h[t]+w[t,newp]则将newp入队，把h[newp]的值更新为h[t]+w[t,newp]；
end
until队列空；
以上算法实现的程序如下：
constmaxn=100;
maxint=maxlongintdiv4;
maxq=10000;
varh:
array[1..maxn]oflongint;
g:
array[1..maxn,1..maxn]oflongint;
n,i,j:
longint;
procedurebfs;
varhead,tail,i,t:
longint;
q:
array[1..maxq]oflongint;
begin
fori:
=1tondoh[i]:
=maxint;
h[1]:
=0;
q[1]:
=1;
head:
=0;tail:
=1;
repeat
head:
=head+1;
t:
=q[head];
fori:
=1tondo
if（g[t,i]<>maxint）and（h[t]+g[t,i]begin
tail:
=tail+1;
q[tail]:
=i;
h[i]:
=h[t]+g[t,i];
end;
untilhead=tail;
end;
begin
assign（input,'data.in'）;
reset（input）;
read（n）;
fori:
=1tondo
forj:
=1tondo
begin
read（g[i,j]）;
if（g[i,j]<=0）and（i<>j）theng[i,j]:
=maxint;
end;
bfs;
fori:
=2tondo
writeln（'From1To',i,'Weigh',h[i]）;
close（input）;
end.
五、迭代法
该算法的中心思想是：
任意两点i,j间的最短距离（记为Dij）会等于从i点出发到达j点的以任一点为中转点的所有可能的方案中，距离最短的一个。
即：
Dij=min{Dij,Dik+Dkj}，1<=k<=n。
这样，我们就找到了一个类似动态规划的表达式，只不过这里我们不把它当作动态规划去处理，而是做一个二维数组用以存放任意两点间的最短距离，利用上述公式不断地对数组中的数据进行处理，直到各数据不再变化为止，这时即可得到A到E的最短路径。
算法流程如下：
D[i]表示从起点到i的最短路的长度，g是邻接矩阵，s表示起点；
1、D[i]:
=g[s,i]（1<=i<=n）；
2、repeat
c:
=false;{用以判断某一步是否有某个Dij值被修改过}
forj:
=1tondo
fork:
=1tondo
ifD[j]>D[k]+g[k,j]then
beginD[j]:
=D[k]+g[k,j];c:
=true;end;
Untilnotc；
这种算法是产生这样一个过程：
不断地求一个数字最短距离矩阵中的数据的值，而当所有数据都已经不能再变化时，就已经达到了目标的平衡状态，这时最短距离矩阵中的值就是对应的两点间的最短距离。
这个算法实现的程序如下：
constmaxn=100;
maxint=maxlongintdiv4;
varD:
array[1..maxn]oflongint;
g:
array[1..maxn,1..maxn]oflongint;
n,i,j,k:
longint;
c:
boolean;
begin
assign（input,'data.in'）;
reset（input）;
read（n）;
fori:
=1tondo
forj:
=1tondo
begin
read（g[i,j]）;
if（g[i,j]<=0）and（i<>j）theng[i,j]:
=maxint;
end;
fori:
=1tondoD[i]:
=g[1,i];
repeat
c:
=false;
forj:
=1tondo
fork:
=1tondo{k是中转点}
ifD[j]>D[k]+g[k,j]then
begin
D[j]:
=D[k]+g[k,j];
c:
=true;
end;
untilnotc;
fori:
=2tondo
writeln（'From1To',i,'Weigh',D[i]）;
close（input）;
end.
六、动态规划
动态规划算法已经成为了许多难题的首选算法。
某些最短路径问题也可以用动态规划来解决
升级会员 