感谢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算法的结果是一样的。谢谢阅读。
