最小生成树-普里姆算法
本帖最后由 奥普瓯江 于 2022-11-24 00:23 编辑原理：
备注：
代码：
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX 9
#define INTF 65535
void KISS(int list);
void KISS(int list)
{
int temp, k, j , dack = 0;
int low;
low = 0; //low数组下标为0的数组初始化，也代表了本次最小生成树的检索是从0这个节点开始的
for(int i = 1; i < MAX; i++) //初始化low数组治理需要主要注意的是low数组下标0的数组已在前面对其进行了赋值，就是把list数组中的第一行传给low数组，其中不包括一个值
{
low = list;
}
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 != 0 && low < temp) //判断当前low中的数值是否是本数组中最小的与temp进行比较
{
temp = low;
k = j;
}
j++;
}
dack += low; //进行累计叠加已统计一共有多少权值
printf("%2d %4d\n",low, k); //打印当前最小的权值，及节点
low = 0; //打印过的节点被赋予0这里证明他已经被执行过了，这我把两个数组合并成了一个数组接用该数组进行表述
for(int j = 1; j < MAX; j++) //执行数组low数组初始化赋值也就是第一个for循环所拥有的功能。
{
if(low != 0 && list < low)//如果标注已经被执行过了（low = 0）及不执行该判断，这里最有意思的是list这里的k将转换成列也就是下一个节点对low进行赋值
{
low = list; //初始化low数组，将下一个节点(k)所包含的数组赋值给low，从新进行开始的for循环（不是这个for）对新一组low数组进行判断
}
}
}
printf("最短路径合计:%2d\n", dack); //打印最短路径权的和值
}
int main()
{
int list = {
{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;
}
页:
[1]