最小生成树算法：普利姆、克鲁斯卡尔（附详细代码）

【注：】本文代码在c++环境下运行

普利姆算法和克鲁斯卡尔算法，都可以用于最小生成树的寻找。

初学两种算法，很容易混淆，经常会把普利姆的算法过程记到了克鲁斯卡尔的头上。这是因为这两个算法都是以人名命名，难以记忆。所以，我建议，根据两算法的特点，把克鲁斯卡尔算法记作 “加边算法” 。把普利姆算法记作 “加点算法”。

我们今天的算法分析，就以下面这个无向带权图为例子：

其邻接矩阵我们可以画出，如下图：

加边算法克鲁斯卡尔

就是每次选择权值最小的边加入到最小生成树集合中。当然，要满足一个前提，这条边加入进来之后，不能产生回路。

要解决的核心问题就是：1.排序；2.判断一条边的加入，会不会构成环。

核心代码：（详细代码见帖子最后）

//克鲁斯卡尔算法
void kruskal(EData **edges, PGraph G) {
	int k = 0;			//对应结果集的指针 
	EData res[MAX];		//存最小生成树结果的边
	sort(edges, G);		//对边的权值排序
	//遍历每一条边
	for(int i = 0;i < G->edgnum;i++){		
		//把每一条边的两个结点编号拿出来
		int p_start = get_index((*edges + i)->start);
		int p_end = get_index((*edges + i)->end);
		//p_start和 p_end 如果不属于同一个集合才能加入。否则加入他们就会产生回路。 
		if(G->vexs[p_start] != G->vexs[p_end]){
			res[k++] = *(*edges + i);
			//要把所有连通分量编号为 p_end的节点给置为p_start。这一步是至关重要的一步！！ 
			for(int j = 0;j < G->vexnum;j++){
				if(G->vexs[j] == G->vexs[p_end]){
					G->vexs[j] = G->vexs[p_start];
				}
			}
		}
	}
	cout << "克鲁斯卡尔算法生成的最小生成树的各边为：" << endl;
	for(int i = 0;i < k;i++){
		cout << res[i].start << ", " << res[i].end << "权值为：" << res[i].weight << endl;
	}
}

---

加点算法普利姆：

设定一个U集合，起始阶段把源点加入U集合内部，

每次把离 U集合 最近的那个结点加入U集合内，然后更新U集合到U集合外其他各点的距离，更新的过程我们称为 松弛。

再说大白话一点，每次把权值最小的外部结点加入U集合内。等所有结点都加入进U集合了，算法终止，最小生成树也成了。

核心代码：（完整代码见帖子最后）

//普利姆算法
int* prim(PGraph G, int *sum) {
	int* res = (int*)malloc(sizeof(EData) * G->vexnum);int k = 1;*sum = 0;	//res数组装每次选择加入最小生成树的结点序号 
	*res = 0;		//第一个节点作为初始节点 
	for(int i = 0;i < G->vexnum;i++){	//初始化dis数组 和 src数组 
		G->dis[i] = G->matrix[0][i];
		G->src[i] = 0;						
	}
	for(int i = 0;i < G->vexnum;i++){
		int min = MAX_INT, min_index = 0;
		//每次找出dis数组中的最小值，作为下一个节点
		for(int j = 0;j < G->vexnum;j++){
			if(G->dis[j] != 0 && G->dis[j] < min){
				min = G->dis[j];
				min_index = j;
			}
		} 
		//结果更新
		*sum = *sum + G->dis[min_index];
		G->dis[min_index] = 0;			//min_index结点就进入U集合了 
		*(res + k) = min_index;
		k++;
		//dis数组更新。根据这个最小值节点，松弛附近的权值
		for(int j = 0;j < G->vexnum;j++){
			//考虑到负权值的情况 
			if(G->matrix[min_index][j] < G->dis[j] && G->dis[j] != 0){
				G->dis[j] = G->matrix[min_index][j];
				G->src[j] = min_index;		//要更改路径 
			}
		} 
	}
	return res;
}

---

下面是完整可运行代码，包含所有数据结构及方法：

克鲁斯卡尔的：

#include<iostream>
#include<cstdlib>
using namespace std;

#define MAX_INT 999	 //边的最大权值，视为正无穷 
#define MAX 100		//数组最大长度 
/*数据结构*
// 邻接矩阵
*/
typedef struct _graph
{
    char vexs[MAX];       // 顶点集合
    int vexnum;           // 顶点数
    int edgnum;           // 边数
    int matrix[MAX][MAX]; // 邻接矩阵
}Graph, *PGraph;

// 边的结构体
typedef struct _EdgeData
{
    char start; // 边的起点
    char end;   // 边的终点
    int weight; // 边的权重
}EData;

/*
**/

//初始化邻接矩阵 
void init(PGraph G)
{
	//所有顶点 
	G->vexs[0] = 'A';G->vexs[1] = 'B';G->vexs[2] = 'C';G->vexs[3] = 'D';G->vexs[4] = 'E';
	G->edgnum = 7;
	G->vexnum = 5;
	//填充邻接矩阵
	G->matrix[0][1] = 9;G->matrix[0][2] = 8;G->matrix[0][3] = MAX_INT;G->matrix[0][4] = MAX_INT;
	G->matrix[1][2] = 2;G->matrix[1][3] = MAX_INT;G->matrix[1][4] = 6;
	G->matrix[2][3] = 4;G->matrix[2][4] = 5;
	G->matrix[3][4] = 3;
	//根据对称性质
	for(int i = 1;i < G->vexnum;i++){
		for(int j = 0;j < i;j++){
			G->matrix[i][j] = G->matrix[j][i];
		}	
	} 
}

void show(PGraph G)
{
	for(int i = 0;i < G->vexnum;i++){
		for(int j = 0;j < G->vexnum;j++){
			if(G->matrix[i][j] == MAX_INT)
				cout << "#" << " ";				//无穷大用#表示 
			else
				cout << G->matrix[i][j] << " ";
		}	
		cout << endl;
	} 
}

//得到该图的边集合。因为函数内部要改指针edges的值。所以要用二级指针 
void getEdges(EData **edges, PGraph G)
{
	*edges = (EData *)malloc(G->edgnum * sizeof(EData));
	int incre = 0;
	for(int i = 1;i < G->vexnum;i++){
		for(int j = 0;j < i;j++){
			if(G->matrix[i][j] != MAX_INT){
				//找到起点和终点 
				char start = G->vexs[i];
				char end = G->vexs[j];
				(*edges + incre)->start = start;
				(*edges + incre)->end = end;
				(*edges + incre)->weight = G->matrix[i][j];
				//地址往后增 
				incre++;
			}
		}	
	} 
} 

//打印所有的边 
void showEdges(EData *edges, PGraph G){
	for(int i = 0;i < G->edgnum;i++){
		cout << (edges + i)->start << ", " << (edges + i)->end << ", " << (edges + i)->weight << endl;
	}
}

//对Edge数组进行排序。采用简单选择排序算法 
void sort(EData **edge, PGraph G){
	for(int i = 0;i < G->edgnum;i++){
		int min = (*edge + i)->weight;
		int min_index = i;
		for(int j = i + 1;j < G->edgnum;j++){
			int val = (*edge + j)->weight;
			if(val < min){
				min = val;
				min_index = j;
			}
		}
		//和最小的节点交换 
		EData temp;
		temp.end = (*edge + i)->end;temp.start = (*edge + i)->start;temp.weight = (*edge + i)->weight;
		(*edge + i)->end = (*edge + min_index)->end;(*edge + i)->start = (*edge + min_index)->start;(*edge + i)->weight = (*edge + min_index)->weight;
		(*edge + min_index)->end = temp.end;(*edge + min_index)->start = temp.start;(*edge + min_index)->weight = temp.weight;
	}
}

//通过节点序号得到 其vexs的 下标 
int get_index(char vex){
	return vex - 65;
}

//克鲁斯卡尔算法
void kruskal(EData **edges, PGraph G) {
	int k = 0;			//对应结果集的指针 
	EData res[MAX];		//存最小生成树结果的边
	sort(edges, G);
	for(int i = 0;i < G->edgnum;i++){
		int p_start = get_index((*edges + i)->start);
		int p_end = get_index((*edges + i)->end);
		//p_start和 p_end 如果不属于同一个集合才能加入。否则加入他们就会产生回路。 
		if(G->vexs[p_start] != G->vexs[p_end]){
			res[k++] = *(*edges + i);
			//要把所有连通分量编号为 p_end的节点给置为p_start。这一步是至关重要的一步！！ 
			for(int j = 0;j < G->vexnum;j++){
				if(G->vexs[j] == G->vexs[p_end]){
					G->vexs[j] = G->vexs[p_start];
				}
			}
		}
	}
	cout << "克鲁斯卡尔算法生成的最小生成树的各边为：" << endl;
	for(int i = 0;i < k;i++){
		cout << res[i].start << ", " << res[i].end << "权值为：" << res[i].weight << endl;
	}
}

int main()
{
	Graph G;
	init(&G);
	//show(&G);
	EData *edges;
	getEdges(&edges, &G);
	cout << "排序前:" << endl;
	showEdges(edges, &G);
	sort(&edges, &G);
	cout << "排序后:" << endl;
	showEdges(edges, &G);
	cout << "----" << endl;
	kruskal(&edges, &G);
	free(edges);
	return 0;
}

运行效果：

---

普利姆的：

#include<iostream>
#include<cstdlib>
using namespace std;

#define MAX_INT 999	 //边的最大权值，视为正无穷 
#define MAX 100		//数组最大长度 
/*数据结构*
// 邻接矩阵
*/
typedef struct _graph
{
    char vexs[MAX];       // 顶点集合
    int vexnum;           // 顶点数
    int edgnum;           // 边数
    int matrix[MAX][MAX]; // 邻接矩阵
    int dis[MAX];		  //标记U集合到集合外各点的最小权值
	int src[MAX];	  	  //记录路径 
}Graph, *PGraph;

// 边的结构体
typedef struct _EdgeData
{
    char start; // 边的起点
    char end;   // 边的终点
    int weight; // 边的权重
}EData;

/*
**/

//初始化邻接矩阵 
void init(PGraph G)
{
	//所有顶点 
	G->vexs[0] = 'A';G->vexs[1] = 'B';G->vexs[2] = 'C';G->vexs[3] = 'D';G->vexs[4] = 'E';
	G->edgnum = 7;
	G->vexnum = 5;
	//填充邻接矩阵
	G->matrix[0][1] = 9;G->matrix[0][2] = 8;G->matrix[0][3] = MAX_INT;G->matrix[0][4] = MAX_INT;
	G->matrix[1][2] = 2;G->matrix[1][3] = MAX_INT;G->matrix[1][4] = 6;
	G->matrix[2][3] = 4;G->matrix[2][4] = 5;
	G->matrix[3][4] = 3;
	//根据对称性质
	for(int i = 1;i < G->vexnum;i++){
		for(int j = 0;j < i;j++){
			G->matrix[i][j] = G->matrix[j][i];
		}	
	} 
}

void show(PGraph G)
{
	cout << "图的邻接矩阵为:" << endl;
	for(int i = 0;i < G->vexnum;i++){
		for(int j = 0;j < G->vexnum;j++){
			if(G->matrix[i][j] == MAX_INT)
				cout << "#" << " ";				//无穷大用#表示 
			else
				cout << G->matrix[i][j] << " ";
		}	
		cout << endl;
	} 
}
//普利姆算法
int* prim(PGraph G, int *sum) {
	int* res = (int*)malloc(sizeof(EData) * G->vexnum);int k = 1;*sum = 0;	//res数组装每次选择加入最小生成树的结点序号 
	*res = 0;		//第一个节点作为初始节点 
	for(int i = 0;i < G->vexnum;i++){	//初始化dis数组 和 src数组 
		G->dis[i] = G->matrix[0][i];
		G->src[i] = 0;						
	}
	for(int i = 0;i < G->vexnum;i++){
		int min = MAX_INT, min_index = 0;
		//每次找出dis数组中的最小值，作为下一个节点
		for(int j = 0;j < G->vexnum;j++){
			if(G->dis[j] != 0 && G->dis[j] < min){
				min = G->dis[j];
				min_index = j;
			}
		} 
		//结果更新
		*sum = *sum + G->dis[min_index];
		G->dis[min_index] = 0;			//min_index结点就进入U集合了 
		*(res + k) = min_index;
		k++;
		//dis数组更新。根据这个最小值节点，松弛附近的权值
		for(int j = 0;j < G->vexnum;j++){
			//考虑到负权值的情况 
			if(G->matrix[min_index][j] < G->dis[j] && G->dis[j] != 0){
				G->dis[j] = G->matrix[min_index][j];
				G->src[j] = min_index;		//要更改路径 
			}
		} 
	}
	return res;
}

//打印最小生成树构建方案 
void showPath(int *res, PGraph G, int sum)
{
	for(int i = 0;i < G->vexnum;i++){
		if(i == 0){
			cout << "1.以" << G->vexs[*(res + i)] << "为初始结点" << endl; 
		}else{
			int node_index = *(res + i);
			int src_index = G->src[node_index]; 
			cout << i + 1 << ".连接结点" << G->vexs[node_index] << "与结点" << G->vexs[src_index] << endl;
		}
	} 
	cout << "生成的最小生成树代价和为：" << sum << endl;
}

int main()
{
	Graph G;
	init(&G);
	show(&G);
	int sum = 0;	//记录最小生成树的总和 
	int* res = prim(&G, &sum);
	showPath(res, &G, sum);
	free(res);
	return 0;
}

运行效果：