假设要在n个城市之间建立通信联络网，则联通n个城市需要n-1条线路。这时需要考虑如何建设才能最省钱呢？用连通网来表示n个城市及n个城市间可能设置的通信线路，其中网的顶点表示城市，边表示城市间的线路，边的权值表示建造这条线路的花费。对于n个顶点的连通网可以建立许多不同的生成树，每棵生成树都可以是一个通信网，选择一棵总耗费最小的生成树，就是最小代价生成树（最小生成树minimum cost spanning tree）。一棵生成树的代价就是树上各边的代价之和。
下面介绍构造最小生成树的算法。
一、普里姆（Prim）算法
1、算法思想
image.png
上图为原始的连通网，从中选取合适的路径构造最小生成树。
初始时：属于最小生成树的顶点集合U = { }
不属于最小生成树的集合V = {v1、v2、v3、v4、v5、v6}
设置两个数据结构：
lowcost[i]：表示以i为终点的边的最小权值，lowcost[i] = 0表示以i为终点的边的最小权值为0，也就说i点加入了最小生成树。
mst[i]：表示对应lowcost[i]那条边的起点，（mst[i]，i）表示的就是最小生成树的一条边，当mst[i] = 0表示起点i加入了最小生成树。
第一步：选择顶点v1作为起始点
这时：属于最小生成树的顶点集合U = {v1}
不属于最小生成树的集合V = {v2、v3、v4、v5、v6}
以顶点v1作为起点的边有（1，2），（1，3），（1，4），也就是终端点为2，4，5，
把权值赋到lowcost中，lowcost[2]=6，lowcost[3]=1，lowcost[4]=5，lowcost[5]=，lowcost[6]=，（*代表无限大，即无通路）
mst赋默认值：mst[2]=1，mst[3]=1，mst[4]=1，mst[5]=1，mst[6]=1
image.png
第二步：以顶点v1为起始点找到一条权值最小的边，这条边的要求是一个顶点在集合U，一个顶点在集合V，这条边就是顶点v1到顶点v3的一条边
这时：属于最小生成树的顶点集合U = {v1、v3}
不属于最小生成树的集合V = {v2、v4、v5、v6}
（1，3）这条边的权值最小，加入集合，更新lowcost，mst数据
lowcost[2]=5，lowcost[3]=0（已加入集合，赋值为0），lowcost[4]=5，lowcost[5]=6，lowcost[6]=4
mst[2]=3，mst[3]=0（已加入集合，赋值为0），mst[4]=1，mst[5]=3，mst[6]=3
image.png
第三步：重复上面步骤
这时：属于最小生成树的顶点集合U = {v1、v3、v6}
不属于最小生成树的集合V = {v2、v4、v5}
image.png
这时：属于最小生成树的顶点集合U = {v1、v3、v6、v4、v2}
不属于最小生成树的集合V = {v5}
为什么会选择顶点v3-v5这个边？
经过上步，还有顶点v2、顶点v5没有连上，U中与顶点v2相连的为顶点v1（权值为6），顶点v3（权值为5），U中与顶点v5相连的为顶点v3、顶点v6,（权值均为6），选取权值最小的边，所以把顶点v3与顶点v2相连，并把顶点v2加入到U中
image.png
最后：属于最小生成树的顶点集合U = {v1、v3、v6、v4、v2、v5}
不属于最小生成树的集合V = { }
2、算法
int prim(int graph[][MAX], int n) {
int lowcost[MAX];
int mst[MAX];
int i, j, min, minid, sum = 0;
for (i = 2; i <= n; i++) { //lowcost赋值为起点为v1的边的权值
lowcost[i] = graph[1][i];
mst[i] = 1;
}
mst[1] = 0; //顶点v1加入集合
for (i = 2; i <= n; i++) {
min = MAXCOST;
minid = 0;
for (j = 2; j <= n; j++) {
//找到未被访问的，且权值最小的顶点
if (lowcost[j] < min && lowcost[j] != 0) {
min = lowcost[j];
minid = j;
}
}
sum += min;
lowcost[minid] = 0; //加入集合
for (j = 2; j <= n; j++) {
//更新lowcost，mst
if (graph[minid][j] < lowcost[j]) {
lowcost[j] = graph[minid][j];
mst[j] = minid;
}
}
}
return sum;
}
算法复杂度为O（n2），与网中的边数无关，适用于求边稠密的网的最小生成树。
二、克鲁斯卡尔（Kruskal）算法
1、算法思想
（1）一个有n个顶点的连通网络N = (V, {E})，最初先构造一个只有n个顶点，没有边的非连通图T = {V, {ф}}，图中每个顶点自成一格连通分量。
（2）在Ｅ中选择一条具有最小权植的边，若该边的两个顶点落在T中不同的连通分量上，则将此边加入到Ｔ中；否则将此边舍去，重新选择一条权植最小的边。
（3）以此类推，直到T中所有顶点在同一连通分量上为止。
image.png
上图为原始的连通网，从中选取合适的路径构造最小生成树。
第一步：只有6个顶点而没有边的非连通图，每个顶点都是一个连通分量，一共有6个（红色圆圈）
image.png
第二步：选择一条权值最小的边（v1，v3），这条边连接了两个连通分量，因此连通分量变成了5个
image.png
第三步：在剩下的边中，再选择一条权值最小的边（v4， v6），这条边连接了两个连通分量，也没有构成回路，所以是符合要求的，这时连通分量变成了4个
image.png
第四步：在剩下的边中，再选择一条权值最小的边（v2， v5），这条边连接了两个连通分量，也没有构成回路，所以是符合要求的，这时连通分量变成了3个
image.png
第五步：在剩下的边中，再选择一条权值最小的边（v3， v6），这条边连接了两个连通分量，也没有构成回路，所以是符合要求的，这时连通分量变成了2个
image.png
最后一步：在剩下的边中，再选择一条权值最小的边（v2， v3），这条边连接了两个连通分量，也没有构成回路，所以是符合要求的，得到最终的最小生成树。（剩下的边中，权值最小边有：（v2， v3），（v3， v4）和（v1， v4），选择（v2， v3）是因为只有这条边不会构成回路。）
image.png
算法复杂度为O（eloge）（e为网中边的数目），适合求边稀疏的网的最小生成树
网友评论