本篇为文章是写的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;
}
