最小生成树:构造连通网的最小代价生成树。（带权值的图为网结构，任意两顶点都是连通的图为连通图）
找连通网的最小生成树，经典有两种算法:普利姆算法（Prim）和克鲁斯卡尔算法（Kruskal）。
prim算法
假设N=（P,{E}）(P是顶点集合，E是边集合)是连通网，TE是N上最小生成树中边的集合。算法从U={u0}（u0属于V），TE={ }开始。重复执行下述操作：
在所有u属于U，v属于V-U的边（u，v）属于E中找一条代价最下的边（u0，v0）并入集合TE，同时v0并入U，直至U=V为止。此时TE中必有n-1条边，则T=（V,{TE}）为N的最
小生成树。即，以某顶点为起点，逐位找各顶点上最小权值的边来构建最小生成树的。
代码：
#include "stdio.h" #include "stdlib.h" #include "io.h" #include "math.h" #include "time.h" #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define MAXEDGE 20 #define MAXVEX 20 #define INFINITY 65535 typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */ typedef struct { int arc[MAXVEX][MAXVEX]; int numVertexes,numEdges; }MGraph; void CreateMGraph(MGraph *G)/* 构件图 */ { int i,j; /* printf("请输入边数和顶点数:"); */ G->numEdges=15; G->numVertexes=9; 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] = INFINITY; } } 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][8]=8; G->arc[2][3]=22; G->arc[3][8]=21; G->arc[3][6]=24; G->arc[3][7]=16; G->arc[3][4]=20; G->arc[4][7]=7; G->arc[4][5]=26; G->arc[5][6]=17; G->arc[6][7]=19; for(i = 0; i < G->numVertexes; i++) { for(j = i; j < G->numVertexes; j++) { G->arc[j][i] =G->arc[i][j]; } } } /* Prim算法生成最小生成树 */ void MiniSpanTree_Prim(MGraph G) { int min,i,j,k; int adjvex[MAXVEX]; /* 保存相关顶点下标 */ int lowcost[MAXVEX]; /* 保存相关顶点间边的权值 */ lowcost[0] = 0;/* 初始化第一个权值为0，即v0加入生成树 */ /* lowcost的值为0，在这里就是此下标的顶点已经加入生成树 */ adjvex[0] = 0; /* 初始化第一个顶点下标为0 */ for(i = 1; i < G.numVertexes; i++) /* 循环除下标为0外的全部顶点 */ { lowcost[i] = G.arc[0][i]; /* 将v0顶点与之有边的权值存入数组 */ adjvex[i] = 0; /* 初始化都为v0的下标 */ } for(i = 1; i < G.numVertexes; i++) { min = INFINITY; /* 初始化最小权值为∞， */ /* 通常设置为不可能的大数字如32767、65535等 */ j = 1;k = 0; while(j < G.numVertexes) /* 循环全部顶点 */ { if(lowcost[j]!=0 && lowcost[j] < min)/* 如果权值不为0且权值小于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(void) { MGraph G; CreateMGraph(&G); MiniSpanTree_Prim(G); return 0; }
结果：
Kruskal算法
假设N=（V，{E}）是连通网，则令最小生成树的初始状态为只有n个顶点而无边的非连通图T={V,{}}，图中每个顶点各自成一个连通分量（无向图的极大连通子图）。
在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。一次类推，直至T中所有顶点都在同
一个连通分量上为止。即，以边为目标去构建，因为权值在边上，直接找权值最小的边来构建生成树。
代码：
#include "stdio.h" #include "stdlib.h" #include "io.h" #include "math.h" #include "time.h" #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */ #define MAXEDGE 20 #define MAXVEX 20 #define INFINITY 65535 typedef struct { int arc[MAXVEX][MAXVEX]; int numVertexes,numEdges; }MGraph; typedef struct { int begin; int end; int weight; }Edge; /* 对边集数组Edge结构的定义 */ /* 构件图 */ void CreateMGraph(MGraph *G) { int i,j; /* printf("请输入边数和顶点数:"); */ G->numEdges=15; G->numVertexes=9; 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] = INFINITY; } } 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][8]=8; G->arc[2][3]=22; G->arc[3][8]=21; G->arc[3][6]=24; G->arc[3][7]=16; G->arc[3][4]=20; G->arc[4][7]=7; G->arc[4][5]=26; G->arc[5][6]=17; G->arc[6][7]=19; for(i = 0; i < G->numVertexes; i++) { for(j = i; 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,j); } } } printf("权排序之后的为:\n"); for (i = 0; i < G->numEdges; i++) { printf("(%d,%d) %d\n",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,n,m; int k = 0; int parent[MAXVEX];/* 定义一数组用来判断边与边是否形成环路 */ Edge edges[MAXEDGE];/* 定义边集数组,edge的结构为begin,end,weight,均为整型 */ /* 用来构建边集数组并排序********************* */ for ( i = 0; i < G.numVertexes-1; i++) { for (j = i + 1; j < G.numVertexes; j++) { if (G.arc[i][j]<INFINITY) { 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; /* 初始化数组值为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) /* 假如n与m不等，说明此边没有与现有的生成树形成环路 */ { parent[n] = m; /* 将此边的结尾顶点放入下标为起点的parent中。 */ /* 表示此顶点已经在生成树集合中 */ printf("(%d,edges[i].weight); } } } int main(void) { MGraph G; CreateMGraph(&G); MiniSpanTree_Kruskal(G); return 0; }
结果：
两种算法的比较：
1，时间复杂度：Prim算法为O（n^2），Kruskal算法为O(eloge)（e为边数）；
2，Kruskal算法只要是针对边来展开，边数少时效率会非常高，所以对于稀疏图有很大优势；而Prim算法主要针对顶点展开，边数非常多的稠密图的情况会好一些。
原文链接：https://www.f2er.com/datastructure/382722.html