1. 相关概念
1.1 生成树概念
所谓一个图的生成树是一个极小连通子图，它含有图中全部的n个顶点，但只有足以构成一棵树的n-1条边。
从上述定义可知，如果一个图有n个顶点和小于n-1条边，则是非连通图，如果它多余n-1条边，必定构成一个环。
注意：
（1）一个图可以有多棵不同的生成树；
（2）具有n-1条边并不一定是生成树。
1.2 最小生成树
给定一个连通网，在该往的所有生成树中，使得各边权值之和最小的那棵生成树称为该网的最小生成树（Minimum Spanning Tree, MST），也叫最小代价生成树。
注意：当网中有多个相同权值的边时，最小生成树可能不唯一。
1.3 MST性质
构造最小生成树的多数算法都利用了MST的性质。
MST性质：设N=（N，E）是一个连通网，U是顶点集V的一个非空子集。若边（u, v）是一条具有最小权值的边，其中u∈U，v属于V-U，则必存在一棵包含边（u，v）的最小生成树。
MST性质解释：在生成树的构造过程中，图中n个顶点分属两个集合：
U：已落在生成树上的顶点集；
V-U：尚未落在生成树上的顶点集 。
接下来则应在所有连通U中顶点和V-U中顶点的边中选取权值最小的边。
2. 普里姆（Prim）算法
算法思想：
设N=（V，E）是连通网，TE是N上最小生成树中边的集合；
初始令U={u0}(u0∈V)，TE={}；
在所有u∈U，v∈V-U的边（u, v)∈E中找一条代价最小的边（u0，v0）；
将（u0，v0）并入集合TE，同时v0并入U；
重复上述操作直至U=V为止，则T=(V, {TE})为N的最小生成树。Prim算法是以某顶点为起点，逐步找各顶点上最小权值的边来构造最小生成树的，算法时间复杂度为O(n^2)。
#include <iostream>
using namespace std;
/**************************************************************************************
*********************************** 图结构定义及操作 ***********************************
***************************************************************************************/
typedef char VertexType; // 顶点类型，自定义
typedef int WeightType; // 边上权值类型，自定义
#define MAXVEX (100) // 最大顶点数
#define INFINITY (65535) // 用65535表示∞，表示顶点之间没有边
typedef struct {
VertexType vexs[MAXVEX]; // 顶点数组
WeightType arcs[MAXVEX][MAXVEX]; // 邻接矩阵
int Nv, Ne; // 顶点数、边数
} MGraph;
/**
* @brief: 建立图的邻接矩阵结构
* @param G：指向图的指针
* @return: void
*/
void createMGraph(MGraph* G) {
cout << "输入顶点数和边数：";
cin >> G->Nv >> G->Ne;
// 初始化邻接矩阵
for (int i = 0; i < G->Nv; i++)
{
for (int j = 0; j < G->Nv; j++)
{
G->arcs[i][j] = (i == j) ? 0 : INFINITY; // 邻接矩阵主对角线初始化为0，其余初始化为INFINITY
}
}
cout << "输入顶点信息：";
for (int i = 0; i < G->Nv; i++)
{
cin >> G->vexs[i];
}
// 读入Ne条边信息，建立邻接矩阵
int i, j;
WeightType w;
for (int k = 0; k < G->Ne; k++)
{
cout << "输入边(Vi, Vj)的下标i、j及其权值w：";
cin >> i >> j >> w;
G->arcs[i][j] = w;
G->arcs[j][i] = G->arcs[i][j]; // 无向图的邻接矩阵为对称阵
}
}
/**************************************************************************************
********************************* 最小生成树之Prime算法 *********************************
***************************************************************************************/
void minSpanTreePrime(MGraph* G) {
int adjvex[MAXVEX];
WeightType lowcost[MAXVEX]; /* 保存相关顶点间边的权值
若lowcost[i]的值为0，表示下标为i的顶点已被纳入生成树中
*/
/* 初始化操作，从V0顶点开始构建最小生成树 */
adjvex[0] = 0; // 初始化第一个顶点的下标为0
lowcost[0] = 0; // 将lowcost[0]初始化为0，即将顶点V0纳入生成树
for (int i = 1; i < G->Nv; i++)
{
lowcost[i] = G->arcs[0][i]; // 将V0与其邻接点之间的边上权值存入lowcost数组
adjvex[i] = 0; // 均初始化为V0的下标
}
for (int i = 1; i < G->Nv; i++) // 这里循环从1开始，因为生成树有n-1条边
{
WeightType minVal = INFINITY; // 记录最小权值，初始化为INFINITY
int minIdx; // 记录最小权值顶点下标
for (int j = 0; j < G->Nv; j++)
{
if (lowcost[j] != 0 && lowcost[j] < minVal) {
minVal = lowcost[j];
minIdx = j;
}
} // 找到权值最小的顶点下标
cout << "(" << adjvex[minIdx] << ", " << minIdx << ")" << endl; /* 打印当前顶点中权值最小的边
也就是最小生成树中的一条边
*/
lowcost[minIdx] = 0; // 将当前顶点的权值置为0，表示它已被纳入生成树中
// 将下标为minIdx的顶点加入生成树后，更新lowcost数组
for (int k = 0; k < G->Nv; k++)
{
/*
lowcost[k] != 0：表示不考虑已加入生成树的顶点
G->arcs[minIdx][k]：表示顶点minIdx的邻接点Vk的权值
G->arcs[minIdx][k] < lowcost[k]：若邻接点的权值小于当前lowcost[k]的值，则需要更新lowcost[k]
*/
if (lowcost[k] != 0 && G->arcs[minIdx][k] < lowcost[k]) {
lowcost[k] = G->arcs[minIdx][k];
adjvex[k] = minIdx;
}
}
}
}
int main() {
MGraph* G = new MGraph;
createMGraph(G);
minSpanTreePrime(G);
delete G;
}
运行结果：
以《大话数据结构》图7-6-3为例。
3. 克鲁斯卡尔（Kruskal）算法
算法思想：
设连通网N=（V，E），令最小生成树初始状态为只有n个顶点而无边的非连通图T=（V，{}），每个顶点自成一个连通分量；
在E中选取代价最小的边，若该边依附的顶点落在T中不同的连通分量上（即：不能形成环），则将此边加入到T中，否则，舍去此边，选取下一条代价最小的边；
以此类推，直至T中所有顶点都在同一连通分量上为止。Kruskal算法以边为目标，直接去找最小权值的边来构建最小生成树的，算法时间复杂度为O(eloge)。
#include <iostream>
using namespace std;
/**************************************************************************************
*********************************** 图的边集数组表示 ***********************************
***************************************************************************************/
typedef int WeightType; // 边上权值类型，自定义
typedef char VertexType; // 顶点类型，自定义
#define MAXVEX (100) // 最大顶点数
#define MAXEDGE (100) // 最大边数
/* 边集数组的Edge结构定义 */
typedef struct {
int begin; // 存储边的起点下标
int end; // 存储边的终点下标
WeightType w; // 权值
} Edge;
typedef struct {
VertexType vexs[MAXVEX]; // 顶点数组
Edge edges[MAXEDGE]; // 边集数组
int Nv, Ne; // 顶点数，边数
} EGraph;
/**
* @brief: 创建图的边集数组表示
* @param G：指向图的指针
* @return： void
*/
void createEGraph(EGraph* G) {
cout << "输入顶点数和边数：";
cin >> G->Nv >> G->Ne;
cout << "输入顶点信息：";
for (int i = 0; i < G->Nv; i++)
{
cin >> G->vexs[i];
}
// 读入Ne条边信息，建立边集数组
int i, j;
WeightType w;
Edge e;
for (int k = 0; k < G->Ne; k++)
{
cout << "输入边(Vi, Vj)的下标i、j及其权值w：";
cin >> i >> j >> w;
e.begin = i;
e.end = j;
e.w = w;
G->edges[k] = e;
}
}
/**
* @brief: 对边集合数组进行排序(采用冒泡排序)
* @param G：指向图的指针
* @return： void
*/
void edgesSort(EGraph* G) {
for (int i = 1; i < G->Ne; i++)
{
for (int j = 0; j < G->Ne - i; j++)
{
if (G->edges[j].w > G->edges[j+1].w)
{
Edge e = G->edges[j];
G->edges[j] = G->edges[j + 1];
G->edges[j + 1] = e;
}
}
}
/*
// 打印排序后的结果
for (int i = 0; i < G->Ne; i++)
{
cout << G->edges[i].w << "\t";
}
cout << endl;
*/
}
/**************************************************************************************
******************************** 最小生成树之Kruskal算法 ********************************
***************************************************************************************/
int parent[MAXVEX] = { 0 }; // 辅助数组，用来判断边与边是否形成环路
/**
* @brief: 查找连线顶点的尾部下标
* @param parent: 用来判断是否形成回路的数组
* @param f: 顶点下标
* @return: int
*/
int Find(int* parent, int f) {
while (parent[f] > 0)
{
f = parent[f];
}
return f;
}
/**
* @brief: 最小生成树Kruskal算法
* @param G: 指向图的指针
* @return: void
*/
void minSpanTreeKruskal(EGraph* G) {
int n, m;
for (int i = 0; i < G->Ne; i++) // 循环每一条边
{
n = Find(parent, G->edges[i].begin);
m = Find(parent, G->edges[i].end);
if (n != m) // 假如n与m不等，说明此边没有与现有生成树形成环路
{
parent[n] = m; /* 将此边的结尾顶点放入下标为起点的parent中，
表示此顶点已经在生成树集合中
*/
cout << "(" << G->edges[i].begin << ", " << G->edges[i].end << ")\t"
<< G->edges[i].w << endl;
}
}
}
int main() {
EGraph* G = new EGraph;
createEGraph(G);
edgesSort(G);
minSpanTreeKruskal(G);
delete G;
}
运行结果：
以《大话数据结构》图7-6-7为例。
4. 两种算法比较
| 算法名 | Prime | Kruskal |
|---|---|---|
| 算法思想 | 选择点 | 选择边 |
| 时间复杂度 | O(n^2)（n为顶点数） | O(eloge)（e为边数） |
| 适应范围 | 稠密图 | 稀疏图 |
5. 参考书籍
大话数据结构-程杰
青岛大学数据结构-王卓
Kruskal算法
parent数组和Find函数的原理