最小生成树-普里姆算法

奥普瓯江

原理：




备注：





代码：

#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;
}