今天，我们来介绍最小代价生成树这一算法。最小生成树的算法有三个，一个是prime算法，一个是kruskal算法，另一个是Boruvka算法。这三个算法都是解决最小代价生成树这一问题的，在这里我们只说prime算法和kruskal算法，那么这两个算法有什么不同呢？图我们知道，有稠密图和稀疏图（引入下定义：数据结构中对于稀疏图的定义为：有很少条边或弧（边的条数|E|远小于|V|²）的图称为稀疏图（sparse graph），反之边的条数|E|接近|V|²，称为稠密图（dense graph）。）。由于这两个算法的贪心策略不同，在面对稠密图时，prime的算法的时间复杂度为O（V^2）[v为顶点的个数]，kruskal算法的时间复杂度为O（E * logE）[E为边的条数]，而稠密图的E是大于V的，所以kruskal算法时间复杂度反而大于prime算法；在面对稀疏图时kruskal算法是优于prime算法的。
大致讲完两个算法的具体适用于什么类型的图，那现在我们正式来说说生是最下代价生成树吧。
这是一张无向网，每一条边的数字代表连接两个点之间的代价值，现在，我们需要找到（顶点个数 - 1）条边能够使得每两个点都有连通路径，且这些边的代价值中和最小。下面这幅图就是其中一个最小代价生成树（红色连接起来的）：
那么prime算法是怎么实现的呢？其实prime算法的步骤很简单：
第一步：我们先找到一个顶点（任意一个顶点都行，加入说我们找到了v3）；
第二步也是最重要、整个程序核心的一步：我们把v3放入顶点集合U0中，然后找一条权值最小的边<u,v>，其中u属于U0，v属于U-U0（U全该图的顶点集合），然后我们把v这个点加入到U0中，重复这个操作，直到我们的U0集合等于U集合为止，辣么这个时候，我们找到了|U|-1条边，也就是我们的最小生成树已经找到了。
通过上面的解释，我们也验证了prime算法的时间复杂度是和顶点个数有关的，下面，我贴出prime算法的代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44int minimum(minside &closedge, int vexnum) {
int i = 0, j, k, min;
while (!closedge[i].lowcost)
i += 1;
min = closedge[i].lowcost;
k = i;
for (j = i + 1; j < vexnum; j ++) {
if (closedge[j].lowcost > 0) {
if (min > closedge[j].lowcost) {
min = closedge[j].lowcost;
k = j;
}
}
}
return k;
}
void MiniSpanTree_PRIM(MGraph G, VertexType u) {
int i, j, k, min;
minside closedge;
k = LocateVex(G, u);
//初始化minside数组
for (j = 0; j < G.vexnum; j ++) {
if (j != k) {
strcpy(closedge[j].adjvex, u);
closedge[j].lowcost = G.arcs[k][j].adj;
}
}
//自身到自身的最小代价为0
closedge[k].lowcost = 0;
cout << "最小代价生成树的各边为：" << endl;
for (i = 1; i < G.vexnum; i ++) {
//去寻找一个最小代价的路径，并找到与之联系的顶点
k = minimum(closedge, G.vexnum);
cout << "(" << closedge[k].adjvex << "," << G.vexs[k] << ")" << " ";
closedge[k].lowcost = 0;
for (j = 0; j < G.vexnum; j ++) {
if (G.arcs[k][j].adj < closedge[j].lowcost) {
strcpy(closedge[j].adjvex, G.vexs[k]);
closedge[j].lowcost = G.arcs[k][j].adj;
}
}
}
}
这是相关图的数据结构代码1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
typedef char VertexType[MAX_NAME];
typedef char InfoType;
enum GraphKind{DG, DN, UDG, UDN};
int IncInfo;
typedef struct {
//图节点（如果是图，则代表边是否存在，如果是网，则是权值信息）
int adj;
InfoType *info;
}ArcCell, AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
struct MGraph {
//顶点集向量
VertexType vexs[MAX_VERTEX_NUM];
//边集
AdjMatrix arcs;
//顶点的个数以及边的条数
int vexnum, arcnum;
//图的类型
GraphKind kind;
};
typedef struct node {
VertexType adjvex;
int lowcost;
} minside[MAX_VERTEX_NUM];
接着，我们再说说kruskal算法是什么个步骤：
同样，还是以上面的最先的那个图为例，kruskal算法的贪心策略是从边，也就是边所具有的权值，我们将图中的黑色的连线忽略，然后呢，我们把这些边的权值拿出来，进行选取，每一次选择权值最小的边，然后找到两个顶点，这样，我们就构建了一个两个节点的树，接着不断进行这个步骤，但是，要小心，我们最终的目的是找到最小代价生成树，因此我们在判断边是否被选取时，考虑的条件不单单是权值大小的问题，还要考虑这个边进来之后，会不会构成圈，如果会是当前的树存在圈，那么这条边我们是不能选取的，应该舍弃这条边。因此，kruskal算法实际是判断当前边是否能够被选取的问题，也就是判断某边加入是否会构成圈的问题，因为边的权值排序是很轻松的。下面我放出kruskal算法的代码，是基于邻接矩阵的图结构的。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
typedef struct
{
elemtype v1;
elemtype v2;
int cost;
} EdgeType;
EdgeType edges[MAXEDGE];
typedef int elemtype;
typedef struct
{
elemtype v1;
elemtype v2;
int cost;
} EdgeType;
void Kruskal(EdgeType edges[], int n)
/*用Kruskal 方法构造有n 个顶点的图edges 的最小生成树*/
{
int father[MAXEDGE];
int i, j, vf1, vf2;
for (i = 0; i < n; i++)
father[i] = -1;
i = 0;
j = 0;
while (i < MAXEDGE && j < n - 1)
{
vf1 = Find(father, edges[i].v1);
vf2 = Find(father, edges[i].v2);
if (vf1 != vf2)
{
father[vf2] = vf1;
j++;
printf("%3d %3d\n", edges[i].v1, edges[i].v2);
}
i++;
}
}
int Find(int father[], int v)
/*寻找顶点v 所在树的根结点*/
{
int t;
t = v;
while (father[t] >= 0)
t = father[t];
return (t);
}