当前位置：首页 > news >正文

C语言-数据结构无向图普里姆Prim算法（邻接矩阵存储）

news 来源：原创 2024/9/20 18:38:11

Prim算法使用了贪心的思想，在算法中使用了两个数组，这两个数组会非常巧妙的操作整个算法的灵魂过程

lowcost的功能：

1.帮助算法寻找到当前距离已完成的最小生成树集合的最小的边长（找到新边）

2.在整个过程中记录新结点加入的时候，更新整个已完成的生成树中所有结点集合到剩余各个结点的最小值（更新当前已加入最小生成树结点集合状态下距离其他结点最短边值）

adjvex的功能：

1.存储每个新节点加入已完成最小生成树结点时，通过它找到当前新加入生成树结点集合中的前驱结点是谁，从而输出对应的边

2.更新前驱结点，帮助在下一次寻找到新结点保存对应的前驱结点（例如A->B这条边中A结点叫前驱）

整个算法的过程时非常巧妙的，lowcost数组类似于水母的触手一开始就只有一条触手，通过触手找到当前最短的边，并把它捕获到已经完成的生成树结点中，理解为生成新的一条触手，触手数量+1，整个代码中大for循环中包含两个小循环，大for循环进行节点数-1轮，每一次从图中找到一个新结点，也就是找到最小生成树的一条边，里面第一个while循环找到当前距离水面触手最短的结点，也就是即将加入的最小生成树的边，找到后并把边对应的结点设置为0标记已经找到的边，下面的小循环for是为了更新当新的触手（新的边）加入的时候，整个水母触手（已完成的最小生成树）距离剩下的各结点之间最短的边长进行更新。并存入下一个即将加入水母触手伙伴的前驱结点，以便绘制打印出对应的边。

我们将创建下面的无向权值图：

最小生成树示意图：

邻接矩阵的绘制还是手动赋值上三角，并通过矩阵对称性生成整个邻接矩阵，其中最小生成树中需要用到权值，对应原本有边的地方之前我是用1表示，现在改成边对应的权值，之前的0表示没有边，现在改成99表示为无穷，其实应该换成更大的值以确保树的边权值都小于这个最大值，但为了方便对齐显示看邻接矩阵，就使用了比本图中各边长较大的99来表示最大值。

Prim算法代码：

/* 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.numNodes; i++)	/* 循环除下标为0外的全部顶点 */{lowcost[i] = G.arc[0][i];	/* 将v0顶点与之有边的权值存入数组 */adjvex[i] = 0;					/* 初始化都为v0的下标 */}printf("\n最小生成树的边按顺序生成：\n");for (i = 1; i < G.numNodes; i++){min = GRAPH_INFINITY;	/* 初始化最小权值为∞， *//* 通常设置为不可能的大数字如32767、65535等 */j = 0; k = 0;while (j < G.numNodes)	/* 循环全部顶点 */{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 = 0; j < G.numNodes; j++)	/* 循环所有顶点 */{if (lowcost[j] != 0 && G.arc[k][j] < lowcost[j]){/* 如果下标为k顶点各边权值小于此前这些顶点未被加入生成树权值 */lowcost[j] = G.arc[k][j];/* 将较小的权值存入lowcost相应位置 */adjvex[j] = k;				/* 将下标为k的顶点存入adjvex */}}}
}

完整代码（包含邻接矩阵的创建，Prim算法）

#include "stdio.h"    
#include "stdlib.h"   
#include "math.h"  
#include "time.h"// 禁用特定的警告
#pragma warning(disable:4996)// 定义一些常量和数据类型
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXVEX 8 /* 最大顶点数，用户定义 */
#define GRAPH_INFINITY 99 /* 用0表示∞，表示不存在边 *//* 定义状态、顶点和边的类型 */
typedef int Status;  /* Status是函数的返回类型，如OK表示成功 */
typedef char VertexType; /* 顶点的类型，用字符表示 */
typedef int EdgeType; /* 边上的权值类型，用整数表示 */
typedef int Boolean; /* 布尔类型 *//* 访问标记数组 */
Boolean visited[MAXVEX];/* 图的邻接矩阵结构体 */
typedef struct
{VertexType vexs[MAXVEX]; /* 顶点表 */EdgeType arc[MAXVEX][MAXVEX]; /* 邻接矩阵，表示边的权值 */int numNodes, numEdges; /* 图中当前的顶点数和边数 */
} MGraph;/* 创建一个无向网图的邻接矩阵表示 */
void CreateMGraph(MGraph* G)
{int i, j, k, w;// 初始化图的顶点数和边数G->numNodes = 8;G->numEdges = 12;// 定义顶点标签char Array[] = "ABCDEFGHI";// 初始化邻接矩阵和顶点表for (i = 0; i < G->numNodes; i++) {for (j = 0; j < G->numNodes; j++) {G->arc[i][j] = GRAPH_INFINITY; /* 初始化邻接矩阵为∞ */}G->vexs[i] = Array[i]; /* 初始化顶点表 */}G->arc[0][0] = GRAPH_INFINITY;G->arc[0][1] = 10;G->arc[0][2] = GRAPH_INFINITY;G->arc[0][3] = GRAPH_INFINITY;G->arc[0][4] = GRAPH_INFINITY;G->arc[0][5] = 11;G->arc[0][6] = GRAPH_INFINITY;G->arc[0][7] = GRAPH_INFINITY;G->arc[1][0] = GRAPH_INFINITY;G->arc[1][1] = GRAPH_INFINITY;G->arc[1][2] = 23;G->arc[1][3] = GRAPH_INFINITY;G->arc[1][4] = GRAPH_INFINITY;G->arc[1][5] = GRAPH_INFINITY;G->arc[1][6] = 12;G->arc[1][7] = GRAPH_INFINITY;G->arc[2][0] = GRAPH_INFINITY;G->arc[2][1] = GRAPH_INFINITY;G->arc[2][2] = GRAPH_INFINITY;G->arc[2][3] = 21;G->arc[2][4] = GRAPH_INFINITY;G->arc[2][5] = GRAPH_INFINITY;G->arc[2][6] = GRAPH_INFINITY;G->arc[2][7] = GRAPH_INFINITY;G->arc[3][0] = GRAPH_INFINITY;G->arc[3][1] = GRAPH_INFINITY;G->arc[3][2] = GRAPH_INFINITY;G->arc[3][3] = GRAPH_INFINITY;G->arc[3][4] = GRAPH_INFINITY;G->arc[3][5] = GRAPH_INFINITY;G->arc[3][6] = GRAPH_INFINITY;G->arc[3][7] = 11;G->arc[4][0] = GRAPH_INFINITY;G->arc[4][1] = GRAPH_INFINITY;G->arc[4][2] = GRAPH_INFINITY;G->arc[4][3] = GRAPH_INFINITY;G->arc[4][4] = GRAPH_INFINITY;G->arc[4][5] = 47;G->arc[4][6] = GRAPH_INFINITY;G->arc[4][7] = 80;G->arc[5][0] = GRAPH_INFINITY;G->arc[5][1] = GRAPH_INFINITY;G->arc[5][2] = GRAPH_INFINITY;G->arc[5][3] = GRAPH_INFINITY;G->arc[5][4] = GRAPH_INFINITY;G->arc[5][5] = GRAPH_INFINITY;G->arc[5][6] = 6;G->arc[5][7] = GRAPH_INFINITY;G->arc[6][0] = GRAPH_INFINITY;G->arc[6][1] = GRAPH_INFINITY;G->arc[6][2] = GRAPH_INFINITY;G->arc[6][3] = GRAPH_INFINITY;G->arc[6][4] = GRAPH_INFINITY;G->arc[6][5] = GRAPH_INFINITY;G->arc[6][6] = GRAPH_INFINITY;G->arc[6][7] = 8;G->arc[7][0] = GRAPH_INFINITY;G->arc[7][1] = GRAPH_INFINITY;G->arc[7][2] = GRAPH_INFINITY;G->arc[7][3] = GRAPH_INFINITY;G->arc[7][4] = GRAPH_INFINITY;G->arc[7][5] = GRAPH_INFINITY;G->arc[7][6] = GRAPH_INFINITY;G->arc[7][7] = GRAPH_INFINITY;// 由于是无向图，邻接矩阵是对称的，需要将其对称for (int i = 0; i < G->numNodes; i++) {for (int j = 0; j < G->numNodes; j++) {G->arc[j][i] = G->arc[i][j];}}// 打印邻接矩阵printf("邻接矩阵为：\n");printf("     ");for (int i = 0; i < G->numNodes; i++) {printf("%2d ", i); /* 打印列索引 */}printf("\n     ");for (int i = 0; i < G->numNodes; i++) {printf("%2c ", G->vexs[i]); /* 打印顶点标签 */}printf("\n");for (int i = 0; i < G->numNodes; i++) {printf("%2d", i); /* 打印行索引 */printf("%2c ", G->vexs[i]); /* 打印顶点标签 */for (int j = 0; j < G->numNodes; j++) {if (G->arc[i][j] != 99) {printf("\033[31m%02d \033[0m", G->arc[i][j]); /* 打印邻接矩阵中的权值 */}else {printf("%02d ", G->arc[i][j]); /* 打印邻接矩阵中的权值 */}}printf("\n");}
}/* 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.numNodes; i++)	/* 循环除下标为0外的全部顶点 */{lowcost[i] = G.arc[0][i];	/* 将v0顶点与之有边的权值存入数组 */adjvex[i] = 0;					/* 初始化都为v0的下标 */}printf("\n最小生成树的边按顺序生成：\n");for (i = 1; i < G.numNodes; i++){min = GRAPH_INFINITY;	/* 初始化最小权值为∞， *//* 通常设置为不可能的大数字如32767、65535等 */j = 0; k = 0;while (j < G.numNodes)	/* 循环全部顶点 */{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 = 0; j < G.numNodes; 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);//Prim算法MiniSpanTree_Prim(G);return 0;
}

最小生成树示意图：

运行结果，边是按下标输出的，下标所对应的字母按ABCDEFGH顺序来表示：