数据结构图之prime算法详解
大家好！今天我要和大家分享一下我对Prime算法的一些理解和实践经验。你可能会有疑问，Prime算法是什么？其实，Prime算法是用于寻找无向图中最小生成树的一种经典算法。不过，我之前写代码时也是个新手，费了不少劲才搞明白这个算法。
问题1：Prime算法是什么？
Prime算法是一种用于寻找无向图中最小生成树的算法。最小生成树（MST）是指在一个连通无向图中找到一棵生成树，使得所有边的权值之和最小。Prime算法的基本思想是从一个起始点开始，逐步添加边到生成树中，直到生成树包含了所有顶点。
问题2：为什么我写的Prime算法运行结果不正确？
作为一个新手，我刚开始写代码时也是一头雾水。我写了一个下午的Prime算法，但结果总是不对。后来在朋友的帮助下，我才理解了代码的逻辑和实现细节。其实，算法的关键在于理解其思想，然后再逐步实现伪代码，最后写出能跑的代码。
问题3：如何正确实现Prime算法？
首先，我们需要理解算法的基本思想。然后，我们可以按照以下步骤来实现算法：
- 初始化一些数组，比如lowcost和adjest，用于存放最小生成树的邻接边和权值。
- 从起始点开始，找到当前权值最小的边，将对应的顶点加入到生成树中。
- 更新相关数组，以便在下一次查找时使用。
下面是我根据上述步骤写出的Prime算法代码：
#include #define MAX_V 100typedef struct {
int v[MAX_V]; // 顶点表
int arc[MAX_V][MAX_V]; // 边表
int v1, a1; // 顶点数和边数
} Graph;
int getid(Graph g, int i) {
for (int j = 0; j < g.v1; j++) {
if (i == g.v[j]) return j;
}
return -1;
}
Graph createGraph() {
Graph g;
printf("请输入顶点数和边数: ");
scanf("%d %d", &g.v1, &g.a1);
for (int i = 0; i < g.v1; i++) {
printf("请输入顶点: ");
scanf("%d", &g.v[i]);
}
printf("请输入边的权值: ");
for (int i = 0; i < g.v1; i++) {
for (int j = 0; j < g.v1; j++) {
scanf("%d", &g.arc[i][j]);
g.arc[j][i] = g.arc[i][j];
}
}
return g;
}
void prime(Graph* g) {
int tree[MAX_V];
int adjest[MAX_V];
int lowcost[MAX_V];
for (int i = 0; i < g->v1; i++) {
lowcost[i] = g->arc[0][i];
adjest[i] = 0;
tree[i] = 0;
}
int cnt = 0;
for (int w = 1; w < g->v1; w++) {
int min = 32767;
int k = -1;
for (int i = 1; i < g->v1; i++) {
if (lowcost[i] != 0 && lowcost[i] < min) {
min = lowcost[i];
k = i;
}
}
tree[++cnt] = k;
lowcost[k] = 0;
for (int i = 1; i < g->v1; i++) {
if (g->arc[k][i] < lowcost[i]) {
lowcost[i] = g->arc[k][i];
adjest[i] = k;
}
}
}
printf("入树的顺序: ");
for (int i = 0; i < g->v1; i++) {
printf("%d ", tree[i]);
}
printf("n");
printf("边的前驱: ");
for (int i = 0; i < g->v1; i++) {
printf("%d ", adjest[i]);
}
}
int main() {
Graph g = createGraph();
prime(&g);
return 0;
}
通过理解和实践，我们可以发现Prime算法其实并不难，关键在于理解其思想和实现步骤。希望这篇文章能帮助大家更好地理解Prime算法，并在实际编程中应用它。如果你有任何问题或建议，欢迎在评论区留言哦！
本篇为文章是写的prime算法，本人见书上算法只有伪代码于是想着写出一个能跑的prime算法
本人写了一个下午的prime算法，但是运行的结果是不正确的 （本人是个小菜鸡） 经过朋友的帮助，运行结果正确。
我觉得算法主要先理解思想 在去试图打出分部的伪代码 最后打出能跑的代码
不多说上代码
# include # define m 31715# define maxs 100typedef struct {int v[maxs]; // 顶点表int arc[maxs][maxs];//边表int v1, a1, w; //顶点数 和边数 权数} tu;int getid(tu t, int i) {for (int j = 0; j < t.v1; j++) {if (i == t.v[j])return j;}return -1;}tu creat (tu t) {printf("请输入定点数和边数");//输入顶点数 边数scanf("%d", &(t.v1));//printf("进行到这了");scanf("%d", &(t.a1));for (int i = 0; i < t.v1; i++) { //初始化 顶点表printf("请输入顶点");scanf("%d", &t.v[i]);}printf("请输入边的权值");for (int i = 0; i < t.v1; i++) {for (int j = 0; j < t.v1; j++) {scanf("%d", &t.arc[i][j]);t.arc[j][i] = t.arc[i][j];}} for(int i=0;i<t.v1;i++) { for(int j=0;jv1]; //用于存放邻接节点int adjest[t->v1]; int lowcost [t->v1]; //用于存放到各边的权值//初始化for (int i = 0; i v1; i++) {lowcost[i] = t->arc[0][i]; // 先按以0为起点 到各边的权值adjest[i]=0;tree[i] = 0; //表示 各边均以 0 为起点}//寻找 lowcost中最小值//要遍历 int cnt=0;for (int w = 1; w v1; w++) {int min, k;min = 32767;//设置初始最小值for (int i = 1; i a1; i++) { //进行遍历 找到 lowcost中最小值 来确定 下一个进树的节点if (lowcost[i] 0) { // =0 表示已经进树min = lowcost[i] ;//赋值k = i; //记录i的值 用于后续进树操作和更新lowcost操作}}tree[++cnt] = k;lowcost[k] = 0;for (int i = 1; i v1; i++) { //为什么从1开始 ？ 因为 lowcost数组中第一个数已经在树中 lowcost【0】=0；一定不满足下边if语句if ( (lowcost[i] t->arc[k][i] )&& t->arc[k][i] >= 0) {lowcost[i] = t->arc[k][i]; // 当满足if语句时 说明lowcost需要更新 把二维数组中的k行i列数据进行赋值 //表示这条边的起点为 k//printf("here");adjest[i]=k;}}}printf("入树的顺序");for (int i = 0; i v1; i++) {printf("%d ", tree[i]);}printf("\n");printf("边的前驱"); for (int i = 0; i v1; i++) {printf("%d ", adjest[i]);}}int main() {tu t;t = creat(t);prime(&t);/*prime 算法 建立 lowcost 数组用于存放最小生成树的邻接边 如果两条边都指向同一个顶点 则 把最小的存入 lowcost设置最小值 min =312715 比min小 则会进行 赋值 用for循环 进行全部比较 最后保留的是 最小权的下标和权值 下标的 lowcost 为0 则表示进树 则 lowcost会更新 如果 新进入树的节点的二维数组 中 第i个值 比lotcost 中第i个值 小则赋值 tree[i]=k;k 是 进入树的节点的下标 输出tree*/return 0;} 
开发者涨薪指南 
48位大咖的思考法则、工作方式、逻辑体系
