本篇为文章是写的prime算法，本人见书上算法只有伪代码于是想着写出一个能跑的prime算法
本人写了一个下午的prime算法，但是运行的结果是不正确的 （本人是个小菜鸡） 经过朋友的帮助，运行结果正确。
我觉得算法主要先理解思想 在去试图打出分部的伪代码 最后打出能跑的代码
不多说上代码
# include <stdio.h> # define m 31715 # define maxs 100 typedef 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;j<t.v1;j++) { printf("%d ",t.arc[i][j]); } printf("\n"); } return t; } void prime(tu *t) { int tree[t->v1]; //用于存放邻接节点 int adjest[t->v1]; int lowcost [t->v1]; //用于存放到各边的权值 //初始化 for (int i = 0; i < t->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 < t->v1; w++) { int min, k;min = 32767;//设置初始最小值 for (int i = 1; i < t->a1; i++) { //进行遍历 找到 lowcost中最小值 来确定 下一个进树的节点 if (lowcost[i] < min && lowcost[i] > 0) { // =0 表示已经进树 min = lowcost[i] ; //赋值 k = i; //记录i的值 用于后续进树操作和更新lowcost操作 } } tree[++cnt] = k; lowcost[k] = 0; for (int i = 1; i < t->v1; i++) { //为什么从1开始 ？ 因为 lowcost数组中第一个数已经在树中 lowcost【0】=0；一定不满足下边if语句 if ( (lowcost[i]<0 || 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 < t->v1; i++) { printf("%d ", tree[i]); } printf("\n"); printf("边的前驱"); for (int i = 0; i < t->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; }
