最小生成树-普里姆算法

奥普瓯江 · 发表于 2022-11-15 01:41:24

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

本帖最后由奥普瓯江于 2022-11-24 00:23 编辑

原理：

备注：

代码：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX 9
#define INTF 65535
void KISS(int list[MAX][MAX]);
void KISS(int list[MAX][MAX])
{
int temp, k, j , dack = 0;
int low[MAX];
low[0] = 0; //low数组下标为0的数组初始化，也代表了本次最小生成树的检索是从0这个节点开始的
for(int i = 1; i < MAX; i++) //初始化low数组治理需要主要注意的是low数组下标0的数组已在前面对其进行了赋值，就是把list数组中的第一行传给low数组，其中不包括一个值
{
low[i] = list[0][i];
}
for(int i = 1; i < MAX; i++) //真正开始进行最小生成树的筛选，这是一个循环其循环的次数为MAX遍
{
temp = INTF; //将temp临时变量赋予int最大值INTF
j = 1; //将j赋予1这里是因为low第一个数值已经赋予了0不需要在进行计算
k = 0;
while(j < MAX) //把list数组中赋予到low数值中的最小值筛选出来
{
if(low[j] != 0 && low[j] < temp) //判断当前low[j]中的数值是否是本数组中最小的与temp进行比较
{
temp = low[j];
k = j;
}
j++;
}
dack += low[k]; //进行累计叠加已统计一共有多少权值
printf("%2d %4d\n",low[k], k); //打印当前最小的权值，及节点
low[k] = 0; //打印过的节点被赋予0这里证明他已经被执行过了，这我把两个数组合并成了一个数组接用该数组进行表述
for(int j = 1; j < MAX; j++) //执行数组low数组初始化赋值也就是第一个for循环所拥有的功能。
{
if(low[j] != 0 && list[k][j] < low[j]) //如果标注已经被执行过了（low[j] = 0）及不执行该判断，这里最有意思的是list[k][j]这里的k将转换成列也就是下一个节点对low进行赋值
{
low[j] = list[k][j]; //初始化low数组，将下一个节点(k)所包含的数组赋值给low，从新进行开始的for循环（不是这个for）对新一组low数组进行判断
}
}
}
printf("最短路径合计:%2d\n", dack); //打印最短路径权的和值
}
int main()
{
int list[MAX][MAX] = {
{0, 10, INTF, INTF, INTF, 11,INTF, INTF, INTF},
{10, 0, 18, INTF, INTF, INTF, 16, INTF, 12},
{INTF, 18, 0, 22, INTF, INTF, INTF, INTF, 8},
{INTF, INTF, 22, 0, 20, INTF, INTF, 16, 21},
{INTF, INTF, INTF, 20, 0, 26, INTF,7, INTF},
{11, INTF, INTF, INTF, 26, 0, 17, INTF,INTF},
{INTF, 16, INTF, INTF, INTF, 17, 0, 19, INTF},
{INTF, INTF, INTF, 16, 7, INTF, 19, 0, INTF},
{INTF, 12, 8, 21, INTF, INTF, INTF, INTF, 0}
};
KISS(list);
return 0;
}

复制代码

账号		自动登录	找回密码
密码			立即注册

[学习笔记] 最小生成树-普里姆算法

马上注册，结交更多好友，享用更多功能^_^

浏览过的版块