《经典图论算法.doc》由会员分享，可在线阅读，更多相关《经典图论算法.doc（23页珍藏版）》请在金锄头文库上搜索。
1、图论中的常用经典算法第一节 最小生成树算法一、生成树的概念若图是连通的无向图或强连通的有向图，则从其中任一个顶点出发调用一次bfs或dfs后便可以系统地访问图中所有顶点；若图是有根的有向图，则从根出发通过调用一次dfs或bfs亦可系统地访问所有顶点。在这种情况下，图中所有顶点加上遍历过程中经过的边所构成的子图称为原图的生成树。对于不连通的无向图和不是强连通的有向图，若有根或者从根外的任意顶点出发，调用一次bfs或dfs后不能系统地访问所有顶点，而只能得到以出发点为根的连通分支（或强连通分支）的生成树。要访问其它顶点则还需要从没有访问过的顶点中找一个顶点作为起始点，再次调用bfs或dfs，这样得
2、到的是生成森林。由此可以看出，一个图的生成树是不唯一的，不同的搜索方法可以得到不同的生成树，即使是同一种搜索方法，出发点不同亦可导致不同的生成树。如下图：但不管如何，我们都可以证明：具有n个顶点的带权连通图，其对应的生成树有n-1条边。二、求图的最小生成树算法严格来说，如果图G=（V，E）是一个连通的无向图，则把它的全部顶点V和一部分边E构成一个子图G，即G=（V， E），且边集E能将图中所有顶点连通又不形成回路，则称子图G是图G的一棵生成树。对于加权连通图，生成树的权即为生成树中所有边上的权值总和，权值最小的生成树称为图的最小生成树。求图的最小生成树具有很高的实际应用价值，比如下面的这个例题
3、。例1、城市公交网问题描述有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权为在这两个城市之间修建高速公路的造价，研究后发现，这个地图有一个特点，即任一对城市都是连通的。现在的问题是，要修建若干高速公路把所有城市联系起来，问如何设计可使得工程的总造价最少。输入 n（城市数，1=n=100） e（边数） 以下e行，每行3个数i,j,wij，表示在城市i,j之间修建高速公路的造价。输出 n-1行，每行为两个城市的序号，表明这两个城市间建一条高速公路。举例下面的图（A）表示一个5个城市的地图，图（B）、（C）是对图（A）分别进行深度优先遍历和广度优先遍历得到的一棵生成树，其权
4、和分别为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），其中XS，not (YS)；将顶点Y加入集合S，边（X，Y）加入集合TE；得到最小生成
5、树T =（S，TE）上图是按照Prim算法，给出了例题中的图（A）最小生成树的生成过程（从顶点1开始）。其中图（E）中的4条粗线将5个顶点连通成了一棵最小生成树。Prim算法的正确性可以通过反证法证明。因为操作是沿着边进行的，所以数据结构采用边集数组表示法，下面给出Prim算法构造图的最小生成树的具体算法框架。 从文件中读入图的邻接矩阵g； 边集数组elist初始化；For i:=1 To n-1 Do Begin elisti.fromv:=1；elisti.endv:=i+1；elisti.weight:=g1,i+1； End； 求出最小生成树的n-1条边； For k:=1 To n-
6、1 Do Begin min:=maxint；m:=k； For j:=k To n-1 Do 查找权值最小的一条边 If elistj.weightmin Then Begin min:=elistj.weight；m:=j；End； If mk Then Begin t:=elistk；elistk:=elistm；elistm:=t；End；把权值最小的边调到第k个单元 j:=elistk.endv； j为新加入的顶点 For i:=k+1 To n-1 Do 修改未加入的边集 Begin s:=elisti.endv； w:=gj,s； If welisti.weight Then B
7、egin elisti.weight:=w；elisti.fromv:=j；End； End； End； 输出；2、用Kruskal算法求最小生成树的思想如下： 设最小生成树为T=（V，TE），设置边的集合TE的初始状态为空集。将图G中的边按权值从小到大排好序，然后从小的开始依次选取，若选取的边使生成树T不形成回路，则把它并入TE中，保留作为T的一条边；若选取的边使生成树形成回路，则将其舍弃；如此进行下去，直到TE中包含n-1条边为止。最后的T即为最小生成树。如何证明呢？下图是按照Kruskal算法给出了例题中图（A）最小生成树的生成过程：Kruskal算法在实现过程中的关键和难点在于：如何判
8、断欲加入的一条边是否与生成树中已保留的边形成回路？我们可以将顶点划分到不同的集合中，每个集合中的顶点表示一个无回路的连通分量，很明显算法开始时，把所有n个顶点划分到n个集合中，每个集合只有一个顶点，表明顶点之间互不相通。当选取一条边时，若它的两个顶点分属于不同的集合，则表明此边连通了两个不同的连通分量，因每个连通分量无回路，所以连通后得到的连通分量仍不会产生回路，因此这条边应该保留，且把它们作为一个连通分量，即把它的两个顶点所在集合合并成一个集合。如果选取的一条边的两个顶点属于同一个集合，则此边应该舍弃，因为同一个集合中的顶点是连通无回路的，若再加入一条边则必然产生回路。下面给出利用Krusk
9、al算法构造图的最小生成树的具体算法框架。 将图的存储结构转换成边集数组表示的形式elist，并按照权值从小到大排好序； 设数组C1.n-1用来存储最小生成树的所有边，Ci是第i次选取的可行边在排好序的elist中的下标； 设一个数组S1.n，Si都是集合，初始时Si= i 。i:=1；获取的第i条最小生成树的边j:=1；边集数组的下标While i=n-1 Do Begin For k:=1 To n Do Begin 取出第j条边，记下两个顶点分属的集合序号 If elistj.fromv in sk Then m1:=k； If elistj.endv in sk Then m2:=k；
10、 End； If m1m2 Then Begin 找到的elist第j条边满足条件，作为第i条边保留 Ci:=j； i:=i+1； sm1:=sm1+sm2；合并两个集合 sm2:= ； 另一集合置空 End； j:=j+1； 取下条边，继续判断 End； 输出最小生成树的各边：elistCi3、总结以上两个算法的时间复杂度均为O（n*n）。参考程序见Prim.pas和Kruskal.pas。请大家用以上两种算法完成例1。三、应用举例例2、最优布线问题（wire.pas，wire.exe）问题描述学校有n台计算机，为了方便数据传输，现要将它们用数据线连接起来。两台计算机被连接是指它们时间有数据
11、线连接。由于计算机所处的位置不同，因此不同的两台计算机的连接费用往往是不同的。 当然，如果将任意两台计算机都用数据线连接，费用将是相当庞大的。为了节省费用，我们采用数据的间接传输手段，即一台计算机可以间接的通过若干台计算机（作为中转）来实现与另一台计算机的连接。现在由你负责连接这些计算机，你的任务是使任意两台计算机都连通（不管是直接的或间接的）。输入格式 输入文件wire.in，第一行为整数n（2=n=100），表示计算机的数目。此后的n行，每行n个整数。第x+1行y列的整数表示直接连接第x台计算机和第y台计算机的费用。输出格式 输出文件wire.out，一个整数，表示最小的连接费用。样例输入
12、30 1 21 0 12 1 0样例输出2（注：表示连接1和2，2和3，费用为2）问题分析本题是典型的求图的最小生成树问题，我们可以利用Prim算法或者Kruskal算法求出，下面的程序在数据结构上对Kruskal算法做了一点修改，具体细节请看程序及注解。参考程序Program wire(Input, Output)；var g : Array 1.100, 1.100 Of Integer；邻接矩阵l : Array 0.100 Of Integer； li存放顶点i到当前已建成的生成树中任意一顶点j的权值gi,j的最小值u : Array 0.100 Of Boolean； ui=True
13、，表示顶点i还未加入到生成树中；ui=False，表示顶点I已加入到生成树中 n, i, j, k, total : Integer；Begin Assign(Input, wire.in)；Reset(Input)；Assign(Output, wire.out)；Rewrite(Output)； Readln(n)； For i := 1 To n Do Begin For j := 1 To n Do Read(gi，j)； Readln；End； Fillchar(l, sizeof(l), $7F)； 初始化为maxintl1 := 0； 开始时生成树中只有第1个顶点 Fillchar(u, sizeof(u), 1)； 初始化为True，表示所有顶点均未加入 For i := 1 To n Do Begin k := 0； For j := 1 To n Do 找一个未加入到生成树中的顶点，记为k，要求k到当前生成树中所有顶点的代价最小 If uj And (lj lk) Then k := j； uk := False； 顶点k加入生成树 For j := 1 To n Do 找到生成树中的顶点j，要求gk,j最小 If uj And (gk，j lj) T
