图论中的常用经典算法

图论中的常用经典算法

第一节 最小生成树算法

一、生成树的概念

若图是连通的无向图或强连通的有向图，则从其中任一个顶点出发调用一次bfs或dfs后便可

以系统地访问图中所有顶点；若图是有根的有向图，则从根出发通过调用一次dfs或bfs亦可系统

地访问所有顶点。在这种情况下，图中所有顶点加上遍历过程中经过的边所构成的子图称为原图的

生成树。

对于不连通的无向图和不是强连通的有向图，若有根或者从根外的任意顶点出发，调用一次

二、求图的最小生成树算法

严格来说，如果图G=（V，E）是一个连通的无向图，则把它的全部顶点V和一部分边E’构成

一个子图G’，即G’=（V， E’），且边集 E’能将图中所有顶点连通又不形成回路，则称子图G’是

图G的一棵生成树。

对于加权连通图，生成树的权即为生成树中所有边上的权值总和，权值最小的生成树称为图的

最小生成树。

求图的最小生成树具有很高的实际应用价值，比如下面的这个例题。

例1、城市公交网

[问题描述]

有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权为在这两

以下e行，每行3个数i,j,w

ij

，表示在城市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算法求最小生成树的思想如下：

中图（E）中的4条粗线将5个顶点连通成了一棵最小生成树。Prim算法的正确性可以通过反证法

证明。

elist[i].fromv:=1；elist[i].endv:=i+1；elist[i].weight:=g[1,i+1]；

③ 求出最小生成树的n-1条边；

min:=maxint；m:=k；

For j:=k To n-1 Do {查找权值最小的一条边}

If elist[j].weight<min Then Begin min:=elist[j].weight；m:=j；End；

End；

End；

2、用Kruskal算法求最小生成树的思想如下：

Kruskal算法在实现过程中的关键和难点在于：如何判断欲加入的一条边是否与生成树中已保

留的边形成回路？我们可以将顶点划分到不同的集合中，每个集合中的顶点表示一个无回路的连通

分量，很明显算法开始时，把所有n个顶点划分到n个集合中，每个集合只有一个顶点，表明顶点

之间互不相通。当选取一条边时，若它的两个顶点分属于不同的集合，则表明此边连通了两个不同

的连通分量，因每个连通分量无回路，所以连通后得到的连通分量仍不会产生回路，因此这条边应

该保留，且把它们作为一个连通分量，即把它的两个顶点所在集合合并成一个集合。如果选取的一

elist中的下标；

③ 设一个数组S[1..n]，S[i]都是集合，初始时S[i]= [ i ]。

j:=1；{边集数组的下标}

For k:=1 To n Do Begin {取出第j条边，记下两个顶点分属的集合序号}

If elist[j].fromv in s[k] Then m1:=k；

If elist[j].endv in s[k] Then m2:=k；

s[m2]:=[ ]； {另一集合置空}

End；

j:=j+1； {取下条边，继续判断}

End；

④ 输出最小生成树的各边：elist[C[i]]

3、总结

指它们时间有数据线连接。由于计算机所处的位置不同，因此不同的两台计算机的连接费用往往是

当然，如果将任意两台计算机都用数据线连接，费用将是相当庞大的。为了节省费用，我们采

用数据的间接传输手段，即一台计算机可以间接的通过若干台计算机（作为中转）来实现与另一台

计算机的连接。

现在由你负责连接这些计算机，你的任务是使任意两台计算机都连通（不管是直接的或间接

的）。

[输入格式]

输入文件wire.in，第一行为整数n（2<=n<=100），表示计算机的数目。此后的 n行，每

行n个整数。第x+1行y列的整数表示直接连接第x台计算机和第y台计算机的费用。

[输出格式]

输出文件wire.out，一个整数，表示最小的连接费用。

[样例输出]

[问题分析]

本题是典型的求图的最小生成树问题，我们可以利用Prim算法或者Kruskal算法求出，下面的

程序在数据结构上对Kruskal算法做了一点修改，具体细节请看程序及注解。

[参考程序]

Program wire(Input, Output)；

var g : Array [1..100, 1..100] Of Integer；{邻接矩阵}

l : Array [0..100] Of Integer； {l[i]存放顶点i到当前已建成的生成树中

Assign(Input, 'wire.in')；

Reset(Input)；

Assign(Output, 'wire.out')；

Rewrite(Output)；

Readln(n)；

Fillchar(u, sizeof(u), 1)； {初始化为True，表示所有顶点均未加入}

k := 0；

For j := 1 To n Do {找一个未加入到生成树中的顶点，记为k，

要求k到当前生成树中所有顶点的代价最小}

If u[j] And (l[j] < l[k]) Then k := j；

u[k] := False； {顶点k加入生成树}

For j := 1 To n Do {找到生成树中的顶点j，要求g[k,j]最小}

If u[j] And (g[k，j] < l[j]) Then l[j] := g[k，j]；

End；

total := 0；