引言
在实际生活中的许多问题都是通过转化为图这类数据结构来求解的，这就涉及了许多图的算法研究。
例如：在n个城市之间铺设光缆，以保证这个n个城市中的任意两个城市之间都可以通信。由于铺设光缆的价格高，且各个城市之间的距离不同，这就使得在各个城市之间铺设光缆的价格不同。那么如何选择铺设线路的方案，才能使费用最低呢？
这个案例就是图的应用 - 最小生成树问题
重要概念
首先，需要明确几个重要概念：
- 连通图：在无向图中，若任意两个顶点都有路径相通，则称该无向图为连通图
- 强连通图：在有向图中，若任意两个顶点都有路径相通，则称该有向图为强连通图
- 连通网：在连通图中，若图的边具有一定的意义，每一条边都对应着一个数，称为权重，称这种连通图为连通网
- 生成树：一个连通图的生成树是指一个连通子图，它含有图中全部n个顶点，但只有足以构成一棵树的n-1条边。
- 最小生成树：在连图网的所有生成树中，所有边的权值和最小的生成树，称为最小生成树
一棵有n个顶点的生成树有且仅有n-1条边，如果生成树中再添加一条边，则必定成环
Prim算法
普里姆算法（Prim算法）是加权连通图里生成最小生成树的一种算法。
算法流程
对于一个加权连通图，其顶点集合V，边集合E
- 从顶点集合中任选一个顶点作为初始顶点，并将该顶点标为已处理
- 已处理的所有顶点可以看成是一个集合U，计算所有与集合U中相邻接的顶点的距离。选择距离最短的顶点，将其标记为已处理，并记录最短距离的边
- 不断计算已处理的顶点集合U和未处理的顶点的距离，每次选出距离最短的顶点标记为已处理，同时记录最短距离的边，直到所有顶点都出来完
- 最终，所有记录的最短距离的边构成的树，即最小生成树
算法图解
例如，上面这个图，用Prim算法构建最小生成树的过程如下：
- 声明2个数组，adjvex数组存储顶点，lowcost数组存储边的权重
- 选择顶点A作为初始出发点，与A相邻接的顶点有B和C，距A的距离分别为6和3。选择距离最短的边（A，C），将C标记为已处理，存储到adjvex数组， 将边（A，C）存入lowcost数组
- 接着处理与C相邻接的顶点A、B、F、E，由于A顶点已经被处理，只需要处理B、F、E中权重最小的顶点即可
- 重复操作，直到所有顶点被处理完，最小生成树生成过程结束
- 结果：A -> C -> B -> D、 B-> F -> E
代码实现
void prim(GNode G, int v) {
int adjvex[MAXVEX];
int lowcost[MAXVEX];
/* 从顶点V出发 */
adjvex[v] = 0;
lowcost[v] = 0;
int i;
for (i = 0; i < G.Nv; i++) {
lowcost[i] = G.arc[v][i];
adjvex[i] = v;
}
int min, sum = 0;
int j, k;
for (i = 1; i < G.Nv; i++) {
min = MAX_INT;
j = 1;
k = 0;
/* 找出最小值 */
while (j < G.Nv) {
if (lowcost[j] != 0 && lowcost[j] < min) {
min = lowcost[j];
k = j;
}
j++;
}
printf("(%c -> %c) = %d\n", G.vers[adjvex[k]], G.vers[k], G.arc[adjvex[k]][k]);
sum += G.arc[adjvex[k]][k];
lowcost[k] = 0;
for (j = 0; j < G.Nv; j++) {
if (lowcost[j] != 0 && G.arc[k][j] < lowcost[j]) {
lowcost[j] = G.arc[k][j];
adjvex[j] = k;
}
}
}
printf("sum = %d\n", sum);
}
性能分析
Prim算法使用邻接矩阵来保存图的话，时间复杂度是O($N^2$)
使用二叉堆优化Prim算法的时间复杂度为O((V + E) log(V)) = O(E log(V))
Kruskal算法
克鲁斯卡算法（Kruskal算法）是一种贪心算法，通过对边表按照权重大小进行排序，每次从边表中取出权重最小且两个顶点都不在同一个集合的边加入生成树中。
如果顶点在同一集合中，说明已经通过其他边相连，仍然加入此顶点，那么就会形成环
算法流程
- 将图中的所有边按权重从小到大排序
- 将图中的n个顶点看成独立的n棵树组成的森林
- 按权重从小到大选择边，所选边连接的两个顶点Vi、Ui。Vi、Ui应属于不同的两棵树，则成为最小生成树的一条边，并将这两棵树合并作为一棵树
- 重复操作3，直到所有的顶点都在一棵树内或者有n-1条边为止
算法图解
- 首先将所有的边按照权重排序，结果为：(B，D)、(B，F)、(A，C)、(B，C)、(A，B)、(D，F)、(E，F)、(C，E)
- 权重最小的边为（B， D），且顶点B、D不在一棵树上，将顶点B、D合并到一棵子树
- 权重最小的边为（B， F），且顶点B、F不在一棵树上，将顶点B、F合并到一棵子树
- 权重最小的边为（A，C），且顶点A、C不在一棵树上，将顶点A、C合并到一棵子树
- 权重最小的边为（B，C），且顶点B、C不在一棵树上，将顶点B、C合并到一棵子树
- 权重最小的边为（A，B），且顶点A、B在一棵树上，则顶点A、B连接的边不能选择
- 重复上面的操作，直到所有顶点都在同一棵树上
- 结果：B->D、A->C、B->F、B->C、E->F
代码实现
/* 边表结构 */
typedef struct {
int begin;
int end;
int weight;
}Edge;
void swapn(Edge edges[], int i, int j) {
int temp = edges[i].begin;
edges[i].begin = edges[j].begin;
edges[j].begin = temp;
temp = edges[i].end;
edges[i].end = edges[j].end;
edges[j].end = temp;
temp = edges[i].weight;
edges[i].weight = edges[j].weight;
edges[j].weight = temp;
}
void sort(Edge edges[], GNode G) {
int i, j;
for (i = 0; i < G.Ne; i++) {
for (j = i + 1; j < G.Ne; j++) {
if (edges[i].weight > edges[j].weight) {
swapn(edges, i, j);
}
}
}
printf("边表排序后为：\n");
for (i = 0; i < G.Ne; i++) {
printf("(%d, %d) = %d\n", edges[i].begin, edges[i].end, edges[i].weight);
}
}
int find(int *parent, int f) {
while (parent[f] > 0) {
f = parent[f];
}
return f;
}
void kruskal(GNode G) {
/* 邻接矩阵转为边表 */
Edge edges[MAXVEX];
int i, j, k = 0;
for (i = 0; i < G.Nv; i++) {
for (j = i + 1; j < G.Nv; j++) {
if (G.arc[i][j] < MAX_INT) {
edges[k].begin = i;
edges[k].end = j;
edges[k].weight = G.arc[i][j];
k++;
}
}
}
/* 边表按权重大小排序 */
sort(edges, G);
/* 初始化 parent数组 */
int parent[MAXVEX] = {0};
printf("最小生成树为：\n");
/* 循环边表数组 */
int m, n, sum = 0;
for (i = 0; i < G.Ne; i++) {
/* 获取begin和end在parent数组中的信息
* 如果n = m, 则说明这条边加入最小生成树会产生闭环
*/
n = find(parent, edges[i].begin);
m = find(parent, edges[i].end);
if (n != m) {
/* 将边的结尾顶点放入下标为起点的parent数组, 表示已经加入生成树集合中 */
parent[n] = m;
printf("(%c -> %c) = %d\n", G.vers[edges[i].begin], G.vers[edges[i].end], edges[i].weight);
sum += edges[i].weight;
}
}
printf("sum = %d\n", sum);
}
性能分析
Kruskal算法为了提高每次贪心选择时查找最短边的效率，可以先将图G中的边按代价从小到达排序，则这个操作的时间复杂度为O(elge)，其中e为无向连通网中边的个数。对于两个顶点是否属于同一个连通分量，可以用并查集的操作将其时间性能提高到O(n)，所以Kruskal算法的时间性能是O(elge)。
总结
图的最小生成树算法种类还有很多，除了上面提到的Prim算法和Kruskal算法，这2个最为经典的算法之外，还有例如：Boruvka算法、 基于权矩阵的最小生成树算法等。