[C++知识库]Kruskal算法，最小生成树，c/c++描述

??感谢bilibili懒猫老师和小甲鱼老师的讲解。
??图的最小生成树，是图的最小连通子图。前面我们讲了Prim算法，其依据的核心定理是：把图里顶点分成两个集合，连接这两个集合的边中，权值最小的边一定在最小生成树MST里，minimal
spanning tree。
??还有另外一个Kruskal算法，纪念伟大的Kruskal工程师。其核心思路是：首先把图里所有路径按权值由小到大排序，从小到大依次选取合适的边加入MST，直到MST里边数比顶点数小1.所谓合适，指待加入树的边，不能使树里出现环。或者说待加入的边的两个顶点，不能在树里存在连通路径。否则，必然出现环。
??该算法实现的几个关键点的处理：
??树MST的存储结构：采用边集数组存储。
??对原图里边排序：本程序采用了插入排序。
??如何判断待加入树的边的两个顶点在树里是否连通：这里运用了并查集的知识。并查集，频繁对集合进行合并和频繁查询元素属于哪个集合。一开始，每个顶点自成一个集合，其根节点的下标是其本身在顶点数组里的下标。最小生成树里顶点属于共同的一个集合，树里顶点的根节点下标是相同的。每往树里加入一条边，就把这条边的两个顶点所在的集合合并，直至加入完建立树需要的所有的边。并查集见本篇的前一两篇文章。
??函数kruskalMST：生成最小生成树，用kruskal算法。
??其引用了以下两个函数：
??函数orderEdge：对边按权值排序，并把边存储在另外一个中间数组里。
??函数unionSet：对加入树的边的两个顶点所属的集合进行合并，原则是小集合合并到大集合里。
main函数所在源文件代码：

#include<iostream>
#include<stdio.h>
using namespace std;
#define MAXVERTEX 15
#define INFINI 65555

struct GraphAdjaMatrix {
	char vertexes[MAXVERTEX];
	int edges[MAXVERTEX][MAXVERTEX];
	int numVertexes;
	int numEdges;
};

struct Edge {
	int indexA;
	int indexB;
	int weightAB;
};

struct GraphEdgeSetArray {
	int vertexNum;
	int edgeNum;
	char vertexes[MAXVERTEX];
	Edge edges[MAXVERTEX];
};

extern void createGraphAdjMatrix(GraphAdjaMatrix &graphAdjMatrix,
			int numVertexes,int numEdges,int edges[][6],char vertexes[]);
extern void dispalyGraphAdjMatrix(GraphAdjaMatrix &graphAdjMatrix);
extern void kruskalMST(GraphAdjaMatrix& graphAdjMatrix,
	GraphEdgeSetArray & graphMST);

int main() {
	GraphAdjaMatrix graphAdjMatrix ;
	int numVertexes = 6, numEdges = 9;
	int edges[][6] = {	{0,34,46,INFINI,INFINI,19},
						{34,0,INFINI,INFINI,12,INFINI},
						{46,INFINI,0,17,INFINI,25},
						{INFINI,INFINI,17,0,38,25},
						{INFINI,12,INFINI,38,0,26},
						{19,INFINI,25,25,26,0} };
	char vertexes[] = {'a','b','c','d','e','f'};

	createGraphAdjMatrix(graphAdjMatrix,numVertexes,numEdges,edges,vertexes);
	dispalyGraphAdjMatrix(graphAdjMatrix);
	cout << endl;

	GraphEdgeSetArray graphMST;
	kruskalMST(graphAdjMatrix,graphMST);

	cout << "its minimal spanning tree is as following :" << endl;
	for (int i = 0; i < graphMST.edgeNum; i++) {
		cout << '(' << graphMST.vertexes[graphMST.edges[i].indexA] << ',';
		cout << graphMST.vertexes[graphMST.edges[i].indexB] << ')';
		cout << graphMST.edges[i].weightAB;
		cout << "          ";
		cout << '(' <<graphMST.edges[i].indexA << ',';
		cout << graphMST.edges[i].indexB << ')';
		cout << graphMST.edges[i].weightAB << endl;;
	}

	return 0;
}

各函数所在源文件代码：

#include<iostream>
#include<stdio.h>
using namespace std;
#define MAXVERTEX 15
#define INFINI 65555

struct GraphAdjaMatrix {
	char vertexes[MAXVERTEX];
	int edges[MAXVERTEX][MAXVERTEX];
	int numVertexes;
	int numEdges;
};

struct Edge {
	int indexA;
	int indexB;
	int weightAB;
};

struct GraphEdgeSetArray {
	int vertexNum;
	int edgeNum;
	char vertexes[MAXVERTEX];
	Edge edges[MAXVERTEX];
};

void createGraphAdjMatrix(GraphAdjaMatrix &graphAdjMatrix,
	int numVertexes, int numEdges, int edges[][6], char vertexes[]) {
	graphAdjMatrix.numVertexes = numVertexes;
	graphAdjMatrix.numEdges = numEdges;
	
	for (int i = 0; i < numVertexes; i++)
		graphAdjMatrix.vertexes[i] = vertexes[i];

	for (int row = 0; row < numVertexes; row++)
		for (int column = 0; column < numVertexes; column++)
			graphAdjMatrix.edges[row][column] = edges[row][column];
}

void dispalyGraphAdjMatrix(GraphAdjaMatrix &graphAdjMatrix) {
	cout << "adjacensy matrix :" << endl;
	int row,column;
	printf("%3c",' ');
	for (row = 0; row < graphAdjMatrix.numVertexes; row++)
		printf("%3c",graphAdjMatrix.vertexes[row]);
	printf("\n");
	for (row = 0; row < graphAdjMatrix.numVertexes; row++) {
		printf("%-3c", graphAdjMatrix.vertexes[row]);
		for (column = 0; column < graphAdjMatrix.numVertexes; column++)
			if (graphAdjMatrix.edges[row][column] == INFINI)
				printf("%3s", "∞");
			else
				printf("%3d",graphAdjMatrix.edges[row][column]);
		cout << endl;
	}
}

void orderEdge(GraphAdjaMatrix& graphAdjMatrix,Edge edgesInOrder[]) {
	edgesInOrder[0].weightAB = edgesInOrder[1].weightAB = 0;
	int row, column,edgeCount = 0;
	Edge edgeTemp;
	for(row = 0 ; row < graphAdjMatrix.numVertexes ; row++)
		for(column = row + 1 ; column < graphAdjMatrix.numVertexes ; column++)
			if (graphAdjMatrix.edges[row][column] != INFINI) {
				if (edgesInOrder[0].weightAB == 0) {
					edgesInOrder[0].weightAB = graphAdjMatrix.edges[row][column];
					edgesInOrder[0].indexA = row;
					edgesInOrder[0].indexB = column;
				}
				else if (edgesInOrder[0].weightAB != 0 && edgesInOrder[1].weightAB == 0) {
					edgesInOrder[0].weightAB = graphAdjMatrix.edges[row][column];
					edgesInOrder[0].indexA = row;
					edgesInOrder[0].indexB = column;

					if (edgesInOrder[0].weightAB > edgesInOrder[1].weightAB) {
						edgeTemp = edgesInOrder[0];
						edgesInOrder[0] = edgesInOrder[1];
						edgesInOrder[1] = edgeTemp;
					}
				}
				else {
					int i;
					for (i = 0; i < edgeCount; i++)
						if (edgesInOrder[i].weightAB <= graphAdjMatrix.edges[row][column] &&
							edgesInOrder[i + 1].weightAB > graphAdjMatrix.edges[row][column] ||
								graphAdjMatrix.edges[row][column] < edgesInOrder[0].weightAB)
							break;
					if (i == edgeCount) {
						edgesInOrder[edgeCount].indexA = row;
						edgesInOrder[edgeCount].indexB = column;
						edgesInOrder[edgeCount].weightAB = graphAdjMatrix.edges[row][column];
  					}
					else if(i == 0){
						for (i = edgeCount; i >= 1; i--)
							edgesInOrder[i] = edgesInOrder[i -1];
						edgesInOrder[0].indexA = row;
						edgesInOrder[0].indexB = column;
						edgesInOrder[0].weightAB = graphAdjMatrix.edges[row][column];
					}
					else {
						for (int j = edgeCount; j >= i + 2; j--)
							edgesInOrder[j] = edgesInOrder[j - 1];
						edgesInOrder[i + 1].indexA = row;
						edgesInOrder[i + 1].indexB = column;
						edgesInOrder[i + 1].weightAB = graphAdjMatrix.edges[row][column];
					}
				}
				edgeCount++;
			}
}


void unionSet(int parent[],Edge edgeShort,int vertexNum) {
	int indexA = edgeShort.indexA, indexB = edgeShort.indexB;
	if (parent[indexA] == indexA)
		parent[indexA] = parent[indexB];
	else if (parent[indexB] == indexB)
		parent[indexB] = parent[indexA];
	else {
		int parentOfA = parent[indexA], parentOfB = parent[indexB];
		int numFamilyA = 0, numfamilyB = 0;
		int indexFamilyA[MAXVERTEX], indexFamilyB[MAXVERTEX];
		for (int i = 0; i < vertexNum; i++)
			if (parent[i] == parentOfA) {
				indexFamilyA[numFamilyA] = i;
				numFamilyA++;
			}
			else if (parent[i] == parentOfB) {
				indexFamilyB[numfamilyB] = i;
				numfamilyB++;
			}
	
		if (numFamilyA <= numfamilyB)
			for (int i = 0; i < numFamilyA; i++)
				parent[indexFamilyA[i]] = parentOfB;
		else
			for (int i = 0; i < numfamilyB; i++)
				parent[indexFamilyB[i]] = parentOfA;
	}
}


void kruskalMST(GraphAdjaMatrix& graphAdjMatrix,
	GraphEdgeSetArray& graphMST) {
	Edge edgesInOrder[MAXVERTEX];
	orderEdge(graphAdjMatrix,edgesInOrder);
	
	graphMST.edgeNum = graphAdjMatrix.numVertexes - 1;
	graphMST.vertexNum = graphAdjMatrix.numVertexes;
	for (int i = 0; i < graphMST.vertexNum; i++)
		graphMST.vertexes[i] = graphAdjMatrix.vertexes[i];

	int parent[MAXVERTEX];
	for (int i = 0; i < graphMST.vertexNum; i++)
		parent[i] = i;

	Edge edgeTemp;
	int numEdgeInMST = 0;
	for (int i = 0; i < graphAdjMatrix.numEdges; i++) {
		edgeTemp = edgesInOrder[i];
		if (parent[edgeTemp.indexA] != parent[edgeTemp.indexB]) {
			graphMST.edges[numEdgeInMST] = edgesInOrder[i];
			unionSet(parent,edgeTemp,graphMST.vertexNum);
			numEdgeInMST++;
		
			if (numEdgeInMST == graphMST.vertexNum - 1)
				break;
		}
	}
}

测试结果与对应的图如下：


同样的例子，跟之前prim算法的结果是一样的。谢谢阅读。