作者： STzen
链接： https://www.Jian Shu.com/p/683 ffd E4 f3a 3
来源：简单书
引入最小生成树列
假设如图所示，v0到v8表示9个村，现在有必要假设这9个村的通信网络。 村间数字表示村间的直线距离，要求以最低成本完成这9个村的通信网络建设。
此图为带权值的图，即网结构。
最小成本是指将n个顶点用n-1条边连接成一个连通图，并按权值的和最小。
如果最小生成树3358www.Sina.com/为无向连通图，则在所有生成树中，一定存在具有最小边缘权重总和的生成树或最小生成树
要找到连通图的最小生成树，请访问网图
一.棱镜(Prim )算法
yydbb算法的步骤从图中的某个顶点出发，在这里选择V0。 找到它所连接的普里姆(Prim)算法和自觉的裙子(Kruskal)算法，比较这些节点的所有结点，连接权值大小的节点。 (这里是V1 ) )。
然后，找到连接了此权值最小的两个结点，并找到所有结点的连接。 (这里是V5。
重复前面的步骤，知道所有节点都已连接。
代码# include stdio.h # include stdlib.h # definemaxedge 20 # definemaxvex 20 # defineinifinty 65535 typedef struct { intarc [ Marc ] }MGraph； /** *生成图*/voidcreatemgraph(mgraph*g ) { int i，j； G-numVertexes=9； //9个顶点G-numEdges=15； //15边for(I=0； i G-numVertexes； I () /初始化映射for ) j=0； j G-numVertexes； j () if ) I==j ) G-arc[i][j]=0； elseg-arc [ I ] [ j ]=g-arc [ j ] [ I ]=inifinty； } } G-arc[0][1]=10； G-arc[0][5]=11； G-arc[1][2]=18； G-arc[1][8]=12； G-arc[1][6]=16； G-arc[2][3]=22； G-arc[2][8]=8； G-arc[3][4]=20； G-arc[3][7]=16； G-arc[3][6]=24； G-arc[3][8]=21； G-arc[4][5]=26； G-arc[4][7]=7； G-arc[5][6]=17； G-arc[6][7]=19； //邻接矩阵的对称性for(I=0； i G-numVertexes； I ) for ) j=0； j G-numVertexes； j ) G-arc[j][i]=G-arc[i][j]； }/** * Prime算法最小生成树*/voidminispantree _ prim (mgraphg ) { int min，I，j，k； int adjvex[MAXVEX]； //关联顶点的下标int lowcost[MAXVEX]； //保存相关顶点之间的边的权重lowcost[0]=0； //初始化的第一个权值为0，即v0被添加到生成树adjvex[0]=0将第一个顶点的下标初始化为0f or (I=1； i G.numVertexes； I ) ) /循环下标除0之外的所有顶点lowcost[i]=G.arc[0][i]； //v0将顶点及其右侧的权重储存在数组adjvex[i]=0中； //初始化均为v0下标(for ) I=1； I
lt; G.numVertexes; i++) { min = INIFINTY; //初始化最小权值 j = 1; k = 0; while (j < G.numVertexes) { // 循环全部顶点 if (lowcost[j] != 0 && lowcost[j] < min) { min = lowcost[j]; // 让当前权值变为最小值 k = j; // 将当前最小值的下标存入k } j++; } printf("(%d, %d)n", adjvex[k], k); // 打印当前顶点中权值最小的边 lowcost[k] = 0; // 将当前顶点的权值设置为0，表示此顶点已经完成任务 for (j = 1; j < G.numVertexes; j++) { // 循环所有顶点 if (lowcost[j]!= 0 && G.arc[k][j] < lowcost[j]) { // 如果下标为k顶点各边权值小于当前这些顶点未被加入生成树权值 lowcost[j] = G.arc[k][j]; // 将较小的权值存入lowcost相应的位置 adjvex[j] = k; // 将下标为k的顶点存入adjvex } } }}int main(int argc, const char * argv[]) { MGraph G; CreateMGraph(&G); MiniSpanTree_Prim(G); return 0;} 代码解释 创建了两个数组adjvex和lowcost。adjvex[0] = 0意思就是从V0开始，lowcost[0] =
0表示V0已经被纳入到最小生成树中。之后凡是lowcost数组中的值被设置为0就是表示此下标的顶点被纳入最小生成树。普里姆算法的时间复杂度为O(n^2)，因为是两层循环嵌套。 代码运行结果
二、自觉的裙子(Kruskal)算法
普里姆算法是从某一顶点为起点，逐步找各个顶点最小权值的边来构成最小生成树。那我们也可以直接从边出发，寻找权值最小的边来构建最小生成树。不过在构建的过程中要考虑是否会形成环的情况
边集数组存储图
在直接用边来构建最小生成树的时候，需要用到边集数组结构，代码为：
typedef struct { // 边集数组 int begin; int end; int weight;}Edge; 代码实现 #include <stdio.h>#include <stdlib.h>#define MAXEDGE 20#define MAXVEX 20#define INIFINTY 65535typedef struct { int arc[MAXVEX][MAXVEX]; int numVertexes, numEdges; }MGraph;typedef struct { // 边集数组 int begin; int end; int weight;}Edge;/** * 构建图 */void CreateMGraph(MGraph * G){ int i, j; G->numVertexes = 9; // 9个顶点 G->numEdges = 15; // 15条边 for (i = 0; i < G->numVertexes; i++) { // 初始化图 for (j = 0; j < G->numVertexes; j++) { if (i == j) G->arc[i][j] = 0; else G->arc[i][j] = G->arc[j][i] = INIFINTY; } } G->arc[0][1] = 10; G->arc[0][5] = 11; G->arc[1][2] = 18; G->arc[1][8] = 12; G->arc[1][6] = 16; G->arc[2][3] = 22; G->arc[2][8] = 8; G->arc[3][4] = 20; G->arc[3][7] = 16; G->arc[3][6] = 24; G->arc[3][8] = 21; G->arc[4][5] = 26; G->arc[4][7] = 7; G->arc[5][6] = 17; G->arc[6][7] = 19; // 利用邻接矩阵的对称性 for (i = 0; i < G->numVertexes; i++) for (j = 0; j < G->numVertexes; j++) G->arc[j][i] = G->arc[i][j];}/** * 交换权值、头、尾 */void Swapn(Edge * edges, int i, int j){ int temp; temp = edges[i].begin; edges[i].begin = edges[j].begin; edges[j].begin = temp; temp = edges[i].end; edges[i].end = edges[j].end; edges[j].end = temp; temp = edges[i].weight; edges[i].weight = edges[j].weight; edges[j].weight = temp;}/** * 对权值进行排序 */void sort(Edge edges[], MGraph *G){ int i,j; for (i = 0; i < G->numEdges; i++) { for (j = i+1; j < G->numEdges; j++) { if (edges[i].weight > edges[j].weight) Swapn(edges, i, j); } } printf("权值排序之后为：n"); for (i = 0; i < G->numEdges; i++) { printf("(%d, %d) %dn", edges[i].begin, edges[i].end, edges[i].weight); }}/** * 查找连线顶点的尾部下标 */int Find(int * parent, int f){ while (parent[f] > 0) f = parent[f]; return f;}void MiniSpanTree_Kruskal(MGraph G){ int i,j,n,m; int k = 0; Edge edges[MAXEDGE]; // 定义边集数组 int parent[MAXVEX]; // 定义一维数组来判断边与边是否形成回路 //构建边集数组并排序 for (i = 0; i < G.numVertexes - 1; i++) { for (j = i+1; j < G.numVertexes; j++) { if (G.arc[i][j] < INIFINTY) { edges[k].begin = i; edges[k].end = j; edges[k].weight = G.arc[i][j]; k++; } } } sort(edges, &G); for (i = 0; i < G.numVertexes; i++) { parent[i] = 0; } printf("打印最小生成树:n"); for (i = 0; i < G.numEdges; i++) { n = Find(parent, edges[i].begin); m = Find(parent, edges[i].end); if (n != m) { parent[n] = m; printf("(%d, %d) %dn",edges[i].begin, edges[i].end , edges[i].weight); } }}int main(int argc, const char * argv[]) { MGraph G; CreateMGraph(&G); MiniSpanTree_Kruskal(G); return 0;} 代码解释 先构建边集数组，并排序，所以前面有对权值进行排序的方法sort。自觉的裙子(Kruskal)算法的时间复杂度为O(eloge)。 运行结果
对比普里姆(Prim)算法和自觉的裙子(Kruskal)算法 自觉的裙子(Kruskal)算法主要针对边来展开，边数较少时效率非常高，所以对于稀疏图有很大的优势；普里姆(Prim)算法对于稠密图，边数非常多的情况更好一些。