最小生成树之普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法

2023年8月1日发(作者：)

最⼩⽣成树之普⾥姆（Prim）算法和克鲁斯卡尔（Kruskal）算法最⼩⽣成树列⼦引⼊如图假设v0到v8表⽰9个村庄，现在需要在这9个村庄假设通信⽹络。村庄之间的数字代表村庄之间的直线距离，求⽤最⼩成本完成这9个村庄的通信⽹络建设。分析这幅图是⼀个带权值的图，即⽹结构。所谓最⼩成本，就是n个顶点，⽤n-1条边把⼀个连通图连接起来，并且使权值的和最⼩。最⼩⽣成树如果⽆向连通图是⼀个⽹图，那么它的所有⽣成树中必有⼀颗是边的权值总和最⼩的⽣成树，即最⼩⽣成树。找到连通图的最⼩⽣成树，有两种经典的算法：普⾥姆(Prim)算法和克鲁斯卡尔(Kruskal)算法⼀、普⾥姆(Prim)算法普利姆算法步骤从图中某⼀个顶点出发(这⾥选V0)，寻找它相连的所有结点，⽐较这些结点的权值⼤⼩，然后连接权值最⼩的那个结点。（这⾥是V1）然后将寻找这两个结点相连的所有结点，找到权值最⼩的连接。（这⾥是V5）.重复上⼀步，知道所有结点都连接上。实现代码#include #include #define MAXEDGE 20#define MAXVEX 20#define INIFINTY 65535typedef struct {

int arc[MAXVEX][MAXVEX]; int numVertexes, numEdges;

}MGraph;/** * 构建图 */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];}/** * Prime算法⽣成最⼩⽣成树 */void MiniSpanTree_Prim(MGraph G){

int min,i,j,k;

int adjvex[MAXVEX]; // 保存相关顶点的下标 int lowcost[MAXVEX]; // 保存相关顶点间边的权值

lowcost[0] = 0; // 初始化第⼀个权值为0，即v0加⼊⽣成树 adjvex[0] = 0; // 初始化第⼀个顶点下标为0

for (i = 1; i < texes; i++) { // 循环除下标为0外的全部顶点 lowcost[i] = [0][i]; // 将v0顶点与之右边的权值存⼊数组 adjvex[i] = 0; // 初始化都为v0的下标 }

for (i = 1; i < texes; i++) {

min = INIFINTY; //初始化最⼩权值 j = 1; k = 0;

while (j < texes) { // 循环全部顶点 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 < texes; j++) { // 循环所有顶点 if (lowcost[j]!= 0 && [k][j] < lowcost[j]) { // 如果下标为k顶点各边权值⼩于当前这些顶点未被加⼊⽣成树权值 lowcost[j] = [k][j]; // 将较⼩的权值存⼊lowcost相应的位置 adjvex[j] = k; // 将下标为k的顶点存⼊adjvex 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 #include #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 < texes - 1; i++) { for (j = i+1; j < texes; j++) { if ([i][j] < INIFINTY) { edges[k].begin = i; edges[k].end = j; edges[k].weight = [i][j]; k++; } } } sort(edges, &G);

for (i = 0; i < texes; i++) { parent[i] = 0; }

printf("打印最⼩⽣成树:n"); for (i = 0; i < es; 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)算法对于稠密图，边数⾮常多的情况更好⼀些。

2023年8月1日发(作者：)

最⼩⽣成树之普⾥姆（Prim）算法和克鲁斯卡尔（Kruskal）算法最⼩⽣成树列⼦引⼊如图假设v0到v8表⽰9个村庄，现在需要在这9个村庄假设通信⽹络。村庄之间的数字代表村庄之间的直线距离，求⽤最⼩成本完成这9个村庄的通信⽹络建设。分析这幅图是⼀个带权值的图，即⽹结构。所谓最⼩成本，就是n个顶点，⽤n-1条边把⼀个连通图连接起来，并且使权值的和最⼩。最⼩⽣成树如果⽆向连通图是⼀个⽹图，那么它的所有⽣成树中必有⼀颗是边的权值总和最⼩的⽣成树，即最⼩⽣成树。找到连通图的最⼩⽣成树，有两种经典的算法：普⾥姆(Prim)算法和克鲁斯卡尔(Kruskal)算法⼀、普⾥姆(Prim)算法普利姆算法步骤从图中某⼀个顶点出发(这⾥选V0)，寻找它相连的所有结点，⽐较这些结点的权值⼤⼩，然后连接权值最⼩的那个结点。（这⾥是V1）然后将寻找这两个结点相连的所有结点，找到权值最⼩的连接。（这⾥是V5）.重复上⼀步，知道所有结点都连接上。实现代码#include #include #define MAXEDGE 20#define MAXVEX 20#define INIFINTY 65535typedef struct {

int arc[MAXVEX][MAXVEX]; int numVertexes, numEdges;

}MGraph;/** * 构建图 */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];}/** * Prime算法⽣成最⼩⽣成树 */void MiniSpanTree_Prim(MGraph G){

int min,i,j,k;

int adjvex[MAXVEX]; // 保存相关顶点的下标 int lowcost[MAXVEX]; // 保存相关顶点间边的权值

lowcost[0] = 0; // 初始化第⼀个权值为0，即v0加⼊⽣成树 adjvex[0] = 0; // 初始化第⼀个顶点下标为0

for (i = 1; i < texes; i++) { // 循环除下标为0外的全部顶点 lowcost[i] = [0][i]; // 将v0顶点与之右边的权值存⼊数组 adjvex[i] = 0; // 初始化都为v0的下标 }

for (i = 1; i < texes; i++) {

min = INIFINTY; //初始化最⼩权值 j = 1; k = 0;

while (j < texes) { // 循环全部顶点 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 < texes; j++) { // 循环所有顶点 if (lowcost[j]!= 0 && [k][j] < lowcost[j]) { // 如果下标为k顶点各边权值⼩于当前这些顶点未被加⼊⽣成树权值 lowcost[j] = [k][j]; // 将较⼩的权值存⼊lowcost相应的位置 adjvex[j] = k; // 将下标为k的顶点存⼊adjvex 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 #include #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 < texes - 1; i++) { for (j = i+1; j < texes; j++) { if ([i][j] < INIFINTY) { edges[k].begin = i; edges[k].end = j; edges[k].weight = [i][j]; k++; } } } sort(edges, &G);

for (i = 0; i < texes; i++) { parent[i] = 0; }

printf("打印最⼩⽣成树:n"); for (i = 0; i < es; 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)算法对于稠密图，边数⾮常多的情况更好⼀些。