基本概念

一个连通图的生成树是一个极小连通子图，其含有图中的全部顶点，和构成一颗树的（n-1）条边。

所以生成树的要求是：

  1. 连通图的连通子图

  2. n个顶点

  3. n-1个边

==图的所有生成树中具有边上的权值之和最小的树称为图的最小生成树==

所以构造最小生成树的准则：

  1. 必须只使用该图中的边来构造最小生成树
  2. 必须使用且仅只使用（n-1）条边来连接图中的n个顶点
  3. 不能使用产生回路的边

城市之间的交通工程造价最优问题，就是典型的最小生成树应用。

求图的最小生成树的两个算法：

  • 普利姆（Prim）算法

    • 朴素版Prim算法——适用于稠密图 $O(n^2)$——适合用邻接矩阵实现，用链式向前星很麻烦
    • 堆优化版Prim算法 ——一般不常用$O(mlogn)$

  • 克鲁斯卡尔（Kruskal）算法——使用与稀疏图 $O(mlogm)$

普利姆算法重点是选点；克鲁斯卡尔算法重点是选边。

普利姆（Prim）算法

假设G=(V,E)是一个具有n个顶点的带权连通图，T=(U,TE)是G的最小生成树，其中U是T的顶点集，TE是T的边集，则由G构造从起始点v出发的最小生成树T的步骤如下：

  1. 初始化U={v}，以v到其他顶点的所有边为候选边。
  2. 重复一下两步骤（n-1）次，使得其他（n-1）个顶点被加入到U中。
    1. 从候选边中挑选权值最小的的边加入TE，设该边在V-U中的顶点是k，讲k加入U中；
    2. 考察当前V-U中的所有顶点j，修改候选边，若(k, j)的权值小于原来和顶点j关联的候选边，则用(k ,j)取代后者作为侯选边。

Prim是一种增量算法，一步步地选择最小边，并在U集合中添加相应的顶点。

注意，不一定是链式的。要计算非生成树的结点倒生成树结点中的最小距离（有边就都要遍历维护最小值）。书中的例子是特例。

普通邻接表实现

这里是利用类似于dfs套bfs的感觉。通过遍历每一个节点的链表，链表上的点就可能是将要走的点。寻找没有走过，且边权最小的点为下一个个节点。

核心代码

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
bool st[MaxV];					// 判断点是否被遍历过

void Prim(AdjGraph* G) {		// 遍历图
	int MIN = INF;
	ArcNode *p, *min;			// p为当前结点，min为边权最小的结点
	int father;					// 下一个结点的父结点
	for (int i = 0; i < G->n; ++i) {	// 遍历图每一个结点
		if (st[i]) {					// 只要在生成树（遍历过且需要）的结点
			p = G->adjlist[i].firstarc;	
			while (p != NULL) {			// 遍历这些结点的下一个结点，并维护最小值
				if (!st[p->adjvex]) {
					if (p->weight < MIN) {
						min = (ArcNode*)malloc(sizeof(ArcNode));
						MIN = p->weight;
						min = p;
						father = i;
					}
				}
				p = p->nextarc;
			}
		}
	}
	if (st[min->adjvex] || min ->adjvex > G->n) return;	// 生成结束的条件
	cout << " -(" << father << ")-> " << min->adjvex;
	st[min->adjvex] = true;
	Prim(G);
}

完整代码

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include <iostream>
#define MaxV 1000
#define INF INT_MAX

using namespace std;

typedef string infoType; 	// 存储信息的类型

typedef struct ANode {		// 边节点 
	int adjvex;				// 该边的邻接点编号
	struct ANode* nextarc;	// 指向下一条边的指针
	int weight;				// 该边的权重 
} ArcNode;					// 边节点的类型 

typedef struct {			// 头节点 
	infoType info;			// 顶点的其他信息 
	ArcNode* firstarc;		// 指向第一个边的指针 
} VNode; 					// 邻接表头节点类型 

typedef struct {
	VNode adjlist[MaxV];	// 邻接表头结点数组
	int n, e;				// 图中的顶点数n, 边数e 
} AdjGraph;					// 完整的图邻接表类型 

// 图的创建
void CreateAdj(AdjGraph*& G,int A[MaxV][MaxV], int n, int e) {
	ArcNode *p;
	G = (AdjGraph*)malloc(sizeof(AdjGraph));
	for (int i = 0; i < n; ++i)
		G->adjlist[i].firstarc = NULL;
	for (int i = 0; i < n; ++i) {
		for (int j = n-1; j >= 0; --j) {
			if (A[i][j] != 0 && A[i][j] != INF) {	// 存在一条边 
				// 申请内存 
				p = (ArcNode*)malloc(sizeof(ArcNode));
				// 存储信息 
				p->adjvex = j;
				p->weight = A[i][j];
				// 头插法插入节点 
				p->nextarc = G->adjlist[i].firstarc;
				G->adjlist[i].firstarc = p;
			}
		}
	}
	G->n = n;
	G->e = e; 
} 

// 图的遍历输出
void DispAdj(AdjGraph* G) {
	ArcNode* p;
	for (int i = 0; i < G->n; ++i) {
		p = G->adjlist[i].firstarc;
		cout << i << " :";
		// 遍历链表 
		while (p != NULL) {
			cout << p->adjvex << "[" << p->weight << "]->";
			p = p->nextarc; 
		} 
		cout << endl;
	}
} 

// 销毁图
void DestroyAdj(AdjGraph*& G) {
	ArcNode* pre, *p;
	for (int i = 0; i < G->n; ++i) {
		pre = G->adjlist[i].firstarc;
		if (pre != NULL) {
			p = pre->nextarc;
			while (p != NULL) {
				free(pre);
				pre = p;
				p=p->nextarc;
			}
			free(pre);
		}
	}
	free(G);
} 

bool st[MaxV];					// 判断点是否被遍历过

void Prim(AdjGraph* G) {
	int MIN = INF;
	ArcNode *p, *min;
	int m;
	for (int i = 0; i < G->n; ++i) {
		if (st[i]) {
			p = G->adjlist[i].firstarc;	
			while (p != NULL) {
				if (!st[p->adjvex]) {
					if (p->weight < MIN) {
						min = (ArcNode*)malloc(sizeof(ArcNode));
						MIN = p->weight;
						min = p;
						m = i;
					}
				}
				p = p->nextarc;
			}
		}
	}
	if (st[min->adjvex] || min ->adjvex > G->n) return;
	cout << " -(" << m << ")-> " << min->adjvex;
	st[min->adjvex] = true;
	Prim(G);
}

int main () {
	// 《数据结构教程》中的图 
	int A[][MaxV] = {
		{0,28,INF,INF,INF,10,INF},
		{28,0,16,INF,INF,INF,14},
		{INF,16,0,12,INF,INF,INF},
		{INF,INF,12,0,22,INF,18},
		{INF,INF,INF,22,0,25,24},
		{10,INF,INF,INF,25,0,INF},
		{INF,14,INF,18,24,INF,0}
	};
	AdjGraph* G;
	CreateAdj(G, A, 7, 9);
	DispAdj(G);
	st[0] = true; // 以 0 为起点
	cout << 0;
	Prim(G);
	DestroyAdj(G);
}

邻接矩阵实现

存储结构

1
2
3
4
int n;      		// n表示图中的结点数
int g[N][N];        // 邻接矩阵，存储所有边
int dist[N];        // 存储其他点到当前最小生成树的距离
bool st[N];    		// 存储每个点是否已经在生成树中(即生成树集合)

模板

1
2
3
4
5
6
7
void Prim() {
    memset(dist, INF, sizeof(dist));
    for (int i = 0; i < n; ++i) {
        遍历找集合外，距离集合内的点最近的点(用t记录编号)
        st[t] = true;// 添加倒集合中
    }
}

核心代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 如果图不连通，则返回INF, 否则返回最小生成树的树边权重之和
void prim(int v) {
    memset(dist, INF, sizeof(dist));
    
    // 先选择起点，并初始化
    for (int j = 0; j < n; ++j) dist[j] = min(dist[j], g[v][j]);
    cout << v << "->";
    st[v] = true;
    
    for (int i = 1; i < n; ++i) {
        int t = -1;
        for (int j = 0; j < n; ++j)
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        cout << t << "->";
        st[t] = true;

        for (int j = 0; j < n; ++j) dist[j] = min(dist[j], g[t][j]);
    }
}

完整代码

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
#include <bits/stdc++.h>
#define N 1000
#define INF 0x3f3f3f3f

using namespace std;

int n = 7;      		// n表示点数     
int g[][N]={ 			// 邻接矩阵，存储所有边，和书中的图一样
	{INF,28,INF,INF,INF,10,INF},
	{28,INF,16,INF,INF,INF,14},
	{INF,16,INF,12,INF,INF,INF},
	{INF,INF,12,INF,22,INF,18},
	{INF,INF,INF,22,INF,25,24},
	{10,INF,INF,INF,25,INF,INF},
	{INF,14,INF,18,24,INF,INF}
};
int dist[N];        // 存储其他点到当前最小生成树的距离
bool st[N];    		// 存储每个点是否已经在生成树中(即生成树集合)

// 如果图不连通，则返回INF, 否则返回最小生成树的树边权重之和
void prim(int v) {
    memset(dist, INF, sizeof(dist));
    
    // 先选择起点，并初始化
    for (int j = 0; j < n; ++j) dist[j] = min(dist[j], g[v][j]);
    cout << v << "->";
    st[v] = true;
    
    for (int i = 1; i < n; ++i) {
        int t = -1;
        for (int j = 0; j < n; ++j)
            if (!st[j] && (t == -1 || dist[t] > dist[j]))
                t = j;

        cout << t << "->";
        st[t] = true;

        for (int j = 0; j < n; ++j) dist[j] = min(dist[j], g[t][j]);
    }
}

int main() {
	n = 7;
	prim(0);
}

邻接矩阵实现——教材

核心代码

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
void Prim(MatGraph g, int v) {
	int lowcost[MAXV];						// U集合
	int min;								// 当前的最小值 
	int closest[MAXV];						// 对于非集合的点(点的编号就是下标)到集合中最近的点
	int k; 									// k 是最近的点（下一个点） 
	// 初始化 
	for (int i = 0; i < g.n; ++i) {
		lowcost[i] = g.edges[v][i];			// 距离都是图中v点到下一个点的边权 
		closest[i] = v;						// 最近的点都是自己 
	}
	for (int i = 1; i < g.n; ++i) {        	// 找出n-1个顶点，其实就是while (g.n-- > 1)的感觉，i除了表示找了几个点以外没有用 
		min = INF;							// 每次都先将 min 置为最大 
		// 在(V-U)中找出离 U 最近的顶点 k , 即寻找下一个结点 
		for (int j = 0; j < g.n; ++j) 
			// lowcost == 0表示点为自己或边权已被使用（已经是集合中的点了）。如果边权比最小的小就改变 k 
			if (lowcost[j] != 0 && lowcost[j] < min) {
				min = lowcost[j];
				k = j;			 			// k 记录最近顶点的编号
			}
		cout << " -(" << closest[k] << ")-" << min << "> " << k;	// 格式为 ： -(从xx点)-边权-> 到达的点 
		lowcost[k] = 0;         			//标记k已经加入U
		//修改数组lowcost和closest,这里的代码思想和上面初始化一样，初始化是v点到下一个点，这里就是k点到下一个点 
		for (int j = 0; j < g.n; ++j)
			if (g.edges[k][j] != 0 && g.edges[k][j] < lowcost[j]) {
				lowcost[j] = g.edges[k][j];	// 将lowcost数组更新为k点到下一个点的边权
				closest[j] = k;				// 默认最近点为自己 
			}
	}
}

完整代码

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <bits/stdc++.h>

using namespace std;

//图的两种存储结构
#define INF 0x3f3f3f3f			//定义INF
#define	MAXV 1000				//最大顶点个数
typedef char InfoType;

typedef struct
{	int no;						//顶点编号
	InfoType info;				//顶点其他信息
} VertexType;					//顶点类型
typedef struct
{	int edges[MAXV][MAXV];		//邻接矩阵数组
	int n,e;					//顶点数，边数
	VertexType vexs[MAXV];		//存放顶点信息
} MatGraph;						//完整的图邻接矩阵类型

void CreateMat(MatGraph &g,int A[MAXV][MAXV],int n,int e) { //创建图的邻接矩阵
	g.n=n; g.e=e;
	for (int i = 0; i < g.n; ++i)
		for (int j = 0; j < g.n; ++j)
			g.edges[i][j] = A[i][j];
}

void DispMat(MatGraph g) {
	for (int i = 0; i < g.n; ++i) {
		for (int j = 0; j < g.n; ++j)
			if (g.edges[i][j]!=INF)
				cout << g.edges[i][j] << " ";
			else
				cout << "INF ";
		cout << endl;
	}
}

void Prim(MatGraph g, int v) {
	int lowcost[MAXV];						// U集合
	int min;								// 当前的最小值 
	int closest[MAXV];						// 对于非集合的点(点的编号就是下标)到集合中最近的点
	int k; 									// k 是最近的点（下一个点） 
	// 初始化 
	for (int i = 0; i < g.n; ++i) {
		lowcost[i] = g.edges[v][i];			// 距离都是图中v点到下一个点的边权 
		closest[i] = v;						// 最近的点都是自己 
	}
	for (int i = 1; i < g.n; ++i) {        	// 找出n-1个顶点，其实就是while (g.n-- > 1)的感觉，i除了表示找了几个点意外没有用 
		min = INF;							// 每次都先将 min 置为最大 
		// 在(V-U)中找出离 U 最近的顶点 k , 即寻找下一个结点 
		for (int j = 0; j < g.n; ++j) 
			// lowcost == 0表示点为自己或边权已被使用（已经是集合中的点了）。如果边权比最小的小就改变 k 
			if (lowcost[j] != 0 && lowcost[j] < min) {
				min = lowcost[j];
				k = j;			 			// k 记录最近顶点的编号
			}
		cout << " -(" << closest[k] << ")-" << min << "> " << k;	// 格式为 ： -(从xx点)-边权-> 到达的点 
		lowcost[k] = 0;         			//标记k已经加入U
		//修改数组lowcost和closest,这里的代码思想和上面初始化一样，初始化是v点到下一个点，这里就是k点到下一个点 
		for (int j = 0; j < g.n; ++j)
			if (g.edges[k][j] != 0 && g.edges[k][j] < lowcost[j]) {
				lowcost[j] = g.edges[k][j];	// 将lowcost数组更新为k点到下一个点的边权
				closest[j] = k;				// 默认最近点为自己 
			}
	}
}

int main()
{
	MatGraph g;
	int A[MAXV][MAXV]={
		{0,28,INF,INF,INF,10,INF},
		{28,0,16,INF,INF,INF,14},
		{INF,16,0,12,INF,INF,INF},
		{INF,INF,12,0,22,INF,18},
		{INF,INF,INF,22,0,25,24},
		{10,INF,INF,INF,25,0,INF},
		{INF,14,INF,18,24,INF,0}};
	CreateMat(g, A, 7, 9);
	DispMat(g);
	cout << "0";
	Prim(g,0);
}

克鲁斯卡尔（Kruskal）算法

克鲁斯卡尔算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法。

假设 G = (V, E) 是一个具有 n 个顶点的带权联通无向图， T = (U, TE) 是 G 的最小生成树，则钩爪最小生成树的步骤如下：

  1. 置 U 的初始值为 V （即包含有 G 中的全部顶点），TE 的初始为空集（即图中的每一个顶点都构成一个分量）。
  2. 将图 G 中的边按权值从小到大的顺序依次选取，若选取的边未使生成树 T 形成回路，则加入 TE ，否则舍弃，直到 TE 中包含 n-1 边为止。

邻接矩阵实现——教材

核心代码

  1. 定义一个表示边的结构体。这样方便统计边的前后结点。而且注意：Kruskal算法关注边。
  2. 定义一个排序函数（或者在构造结构体时，顺便实现排序方式，这样就可以使用sort()）
  3. 定义Kruskal函数。函数首先根据参数 g 创建边的集合，即 E。创建好集合后，排序。这样操作之后，E数组就是排好序的边了。现在只需要挨个从小到达遍历这些边是否符合条件就行。
  4. 定义一个辅助函数。这个函数的下标 i 记录结点 i 的种类。初始时赋值为 i 即所有结点的种类都是单独的。当两个或多个结点的种类为同一个时，则这些点被连接起来了，也就是在同一颗最小生成树上了。
  5. 判断符合条件——是否构成回路。如果两个端点在一个集合中，即已经渲染为同类了，就是一个回路，如果不是同类，就使用该边。并且需要将两个端点所在的子生成树的所有结点都改成同一个，表示渲染成同一类。
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
50
51
52
53
54
55
56
57
// Kruskal算法需要的结构体 
typedef struct {
	int u;						// 边的起始顶点
	int v;						// 边的终止顶点
	int w;						// 边的权值 
} Edge;

void BubbleSort(Edge E[],int n) { 	//对E[0..n-1]按递增有序进行直接插入排序
	Edge temp;
	for (int i = 0; i < n - 1; ++i) 
		for (int j = i; j < n; ++j) 
			if (E[i].w > E[j].w) {
				temp = E[i];
				E[i] = E[j];
				E[j] = temp;
			}
}

void Kruskal(MatGraph g) {
	int u1, v1, sn1, sn2;
	int vset[MAXV];
	Edge E[MaxSize];							    // 存放所有边
	int k=0;										// E数组的下标从0开始计
	// 初始化 E 数组
	for (int i = 0; i < g.n; ++i)
		for (int j = 0; j <= i; ++j) {
			if (g.edges[i][j] != 0 && g.edges[i][j] != INF) {
				E[k].u = i;
				E[k].v = j; 
				E[k].w = g.edges[i][j];
				k++;
			}
		}
	// 对 E 数组按权值大小排序 
	BubbleSort(E, g.e);
	//初始化辅助数组（点的集合） 
	for (int i = 0; i < g.n; ++i) vset[i] = i;
	k = 1;                 			// k表示当前构造生成树的第几条边,初值为1,因为最小生成树的边有且仅有n-1条 
	int j = 0;						// E中边的下标,记录当前可使用的权值最小的边
    // 找到 n - 1 条边
	while (k < g.n) {
		// 取一条边的头尾顶点
		u1 = E[j].u;
		v1 = E[j].v;
		// 分别得到两个顶点所属的集合编号
		sn1 = vset[u1];
		sn2 = vset[v1]; 						
		if (sn1 != sn2) {    	  	// 若两顶点属于不同的集合,则该边是最小生成树的一条边
			cout << "  (" << u1 << "," << v1 << "):" << E[j].w << endl;
			k++;                    			// 生成边数增1
			for (int i = 0; i < g.n; ++i)     	// 两个集合统一编号
				if (vset[i] == sn2)  			// 集合编号为 sn2 的所有结点都改为 sn1
				    vset[i] = sn1;
		}
		j++;   									// 扫描下一条边
	}
}

完整代码

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <bits/stdc++.h>
#define MAXV 100
#define MaxSize 100
#define INF 0x3f3f3f3f 

using namespace std;

typedef char InfoType;

typedef struct {
	int no;						//顶点编号
	InfoType info;				//顶点其他信息
} VertexType;					//顶点类型
typedef struct {
	int edges[MAXV][MAXV];		//邻接矩阵数组
	int n,e;					//顶点数，边数
	VertexType vexs[MAXV];		//存放顶点信息
} MatGraph;						//完整的图邻接矩阵类型

void CreateMat(MatGraph &g,int A[MAXV][MAXV],int n,int e) { //创建图的邻接矩阵
	g.n=n; g.e=e;
	for (int i = 0; i < g.n; ++i)
		for (int j = 0; j < g.n; ++j)
			g.edges[i][j] = A[i][j];
}

void DispMat(MatGraph g) {
	for (int i = 0; i < g.n; ++i) {
		for (int j = 0; j < g.n; ++j)
			if (g.edges[i][j]!=INF)
				cout << g.edges[i][j] << " ";
			else
				cout << "INF ";
		cout << endl;
	}
}

// Kruskal算法需要的结构体 
typedef struct {
	int u;						// 边的起始顶点
	int v;						// 边的终止顶点
	int w;						// 边的权值 
} Edge;

void BubbleSort(Edge E[],int n) { 	//对E[0..n-1]按递增有序进行直接插入排序
	Edge temp;
	for (int i = 0; i < n - 1; ++i) 
		for (int j = i; j < n; ++j) 
			if (E[i].w > E[j].w) {
				temp = E[i];
				E[i] = E[j];
				E[j] = temp;
			}
}

void Kruskal(MatGraph g) {
	int u1, v1, sn1, sn2;
	int vset[MAXV];
	Edge E[MaxSize];							    // 存放所有边
	int k=0;										// E数组的下标从0开始计
	// 初始化 E 数组
	for (int i = 0; i < g.n; ++i)
		for (int j = 0; j <= i; ++j) {
			if (g.edges[i][j] != 0 && g.edges[i][j] != INF) {
				E[k].u = i;
				E[k].v = j; 
				E[k].w = g.edges[i][j];
				k++;
			}
		}
	// 对 E 数组按权值大小排序 
	BubbleSort(E, g.e);
	//初始化辅助数组（点的集合） 
	for (int i = 0; i < g.n; ++i) vset[i] = i;
	k = 1;                 			// k 表示当前构造生成树的第几条边,初值为1
	int j = 0;						// E 中边的下标,记录当前可使用的权值最小的边
    // 找到 n - 1 条边
	while (k < g.n) {
		// 取一条边的头尾顶点
		u1 = E[j].u;
		v1 = E[j].v;
		// 分别得到两个顶点所属的集合编号
		sn1 = vset[u1];
		sn2 = vset[v1]; 						
		if (sn1 != sn2) {    	  	// 若两顶点属于不同的集合,则该边是最小生成树的一条边
			cout << "  (" << u1 << "," << v1 << "):" << E[j].w << endl;
			k++;                    			// 生成边数增1
			for (int i = 0; i < g.n; ++i)     	// 两个集合统一编号
				if (vset[i] == sn2)  			// 集合编号为sn2的改为sn1
				    vset[i] = sn1;
		}
		j++;   									// 扫描下一条边
	}
}

int main () {
	MatGraph g;
	int A[MAXV][MAXV]={
		{0,28,INF,INF,INF,10,INF},
		{28,0,16,INF,INF,INF,14},
		{INF,16,0,12,INF,INF,INF},
		{INF,INF,12,0,22,INF,18},
		{INF,INF,INF,22,0,25,24},
		{10,INF,INF,INF,25,0,INF},
		{INF,14,INF,18,24,INF,0}};
	CreateMat(g, A, 7, 9);
	DispMat(g);
	Kruskal(g);
}

改进克鲁斯卡尔算法

改进克鲁斯卡尔算法需要 并查集 和 堆排序 的基础，如果不会可以点击链接学习。

完整代码如下：

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
#include <iostream>
#include <malloc.h>
#define MaxSize 100
#define MAXV 100
#define INF 0x3f3f3f3f
using namespace std;
typedef char InfoType;

int sum = 0;					// 最终结果 

typedef struct {
	int no;						//顶点编号
	InfoType info;				//顶点其他信息
} VertexType;					//顶点类型
typedef struct {
	int edges[MAXV][MAXV];		//邻接矩阵数组
	int n, e;					//顶点数，边数
	VertexType vexs[MAXV];		//存放顶点信息
} MatGraph;						//完整的图邻接矩阵类型
void CreateMat(MatGraph &g, int A[MAXV][MAXV], int n, int e) { //创建图的邻接矩阵
	g.n = n; g.e = e;
	for (int i = 0; i < g.n; ++i)
		for (int j = 0; j < g.n; ++j)
			g.edges[i][j] = A[i][j];
}

// 并查集相关代码 
typedef struct {
	int u;			//边的起始顶点
    int v;			//边的终止顶点
    int w;			//边的权值
} Edge;
typedef struct {
	int rank;						//结点对应秩
	int parent;						//结点对应双亲下标
} UFSTree;							//并查集树结点类型
void Init(UFSTree S[], int n) {		//初始化并查集树 
	for (int i = 0; i < n; ++i) {	//顶点编号从0到n-1
		S[i].rank=0;				//秩初始化为0
		S[i].parent=i;				//双亲初始化指向自已
	}
}
int Find(UFSTree S[], int x)	{			//在x所在子树中查找集合编号
	if (x != S[x].parent)					//双亲不是自已
		S[x].parent = Find(S, S[x].parent);	//路径压缩
	return S[x].parent;
}
void Union(UFSTree S[], int x, int y) {		//将x和y所在的子树合并
	int rx = Find(S,x);
	int ry = Find(S,y);
	if (S[rx].rank > S[ry].rank)
		S[ry].parent=rx;
	else { 
		S[rx].parent = ry;
		if (S[rx].rank == S[ry].rank)
			S[ry].rank++;
	}
}

// 堆排序相关代码 
void sift(Edge E[], int low, int high) {//筛选算法
	int i = low, j = 2*i;     			//E[j]是E[i]的左孩子
	Edge temp = E[i];
	while (j <= high) {
		if (j<high && E[j].w<E[j+1].w)	//若右孩子较大,把j指向右孩子
			j++;    					//f变为2i+1
		if (temp.w < E[j].w) {
			E[i] = E[j];              	//将E[j]调整到双亲结点位置上
			i = j;                    	//修改i和j值,以便继续向下筛选
			j = 2*i;
		}
		else break;                 	//筛选结束
	}
	E[i] = temp;                      	//被筛选结点的值放入最终位置
}
void HeapSort(Edge E[], int n) {
	Edge temp;
	for (int i = n/2; i >= 1; --i)  	//循环建立初始堆
		sift(E, i, n); 
	for (int i = n; i >= 2; --i) {  	//进行n-1次循环,完成推排序
		temp = E[1];        			//将第一个元素同当前区间内R[1]对换
		E[1] = E[i];
		E[i] = temp;
		sift(E, 1, i-1);     			//筛选R[1]结点,得到i-1个结点的堆
	}
}

// 改进Kruskal算法实现代码 
void Kruskal(MatGraph g) {
	int i, j, k, u1, v1, sn1, sn2;
	UFSTree S[MaxSize];
	Edge E[MaxSize];
	k = 1;					// e数组的下标从1开始计
	for (i = 0; i < g.n; ++i)
		for (j = 0; j <= i; ++j)
			if (g.edges[i][j] != 0 && g.edges[i][j] != INF) {
				E[k].u = i; E[k].v = j; E[k].w = g.edges[i][j];
				k++;
			}
	HeapSort(E, g.e);		// 采用堆排序对 E 数组按权值递增排序
	Init(S, g.n);			// 初始化并查集树t
	k=1;               		// k表示当前构造生成树的第几条边,初值为1
	j=1;               		// E中边的下标,初值为1
	while (k < g.n) {      	// 生成的边数小于n时循环
		// 取一条边的头尾顶点分别编号为u1和v2
		u1 = E[j].u;
		v1 = E[j].v;			
		// 利用并查集分别得到两个顶点所属的集合编号
		sn1 = Find(S,u1);
		sn2 = Find(S,v1); 
		if (sn1!=sn2) {    	// 两顶点属于不同的集合,该边是最小生成树的一条边
			sum += E[j].w; 	// 更新答案 
			k++;			// 生成边数增1
			Union(S,u1,v1);	// 利用并查集将u1和v1两个顶点合并
		}
		j++;   				// 继续扫描下一条边
	}
}

int main() {
	MatGraph g;
	int A[MAXV][MAXV] = {
		{  0,  3,INF,INF,INF,  4,INF,INF,INF},
		{  3,  0,  8,INF,INF,INF,  6,INF,  5},
		{INF,  8,  0, 12,INF,INF,INF,INF,  2},
		{INF,INF, 12,  0, 10,INF, 14,  6, 11},
		{INF,INF,INF, 10,  0, 18,INF,  1,INF},
		{  4,INF,INF,INF, 18,  0,  7,INF,INF},
		{INF,  6,INF, 14,INF,INF,  0,  9,INF},
		{INF,INF,INF,  6,  1,INF,  9,  0,INF},
		{INF,  5,  2, 11,INF,INF,INF,INF,  0}};
	CreateMat(g, A, 9, 15);
	Kruskal(g);
	cout << sum; 
}

如果使用更快的排序，例如堆排序，快速排序使得排序的时间复杂度提升为 $O(mlog_2 m)$，当然选择排序方式应当选择更快速，且更稳定的算法，所有这里选择使用堆排序。并且Kruskal算法是加边操作，很容易造成：多个边提前并在一个集合中，并且产生多个这个集合，在原本的Kruskal算法中合并集合占用的时间复杂度很高，但是思考这一性质，可以想出利用并查集来优化，使用并查集合并集合的时间复杂度为，所以while循环整体的时间复杂度变为。对于连通无向图来说,，所以最终算法时间复杂度为。

适用于竞赛的简化版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
int n, m;       // n是点数，m是边数
int p[N];       // 并查集的父节点数组

struct Edge {   // 存储边
    int a, b, w;

    bool operator< (const Edge &W)const
    {
        return w < W.w;
    }
} edges[M];

int find(int x) {   // 并查集核心操作
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int kruskal() {
    sort(edges, edges + m);

    for (int i = 1; i <= n; i ++ ) p[i] = i;    // 初始化并查集

    int res = 0, cnt = 0;
    for (int i = 0; i < m; i ++ ) {
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;

        a = find(a), b = find(b);
        if (a != b) {   // 如果两个连通块不连通，则将这两个连通块合并
            p[a] = b;
            res += w;
            cnt ++ ;
        }
    }

    if (cnt < n - 1) return INF;
    return res;
}