最小生成树-克鲁斯卡尔算法

奥普瓯江

原理：



备注：



代码：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX 9
#define INTF 65535

typedef struct Nice                 //边集链表
{
    int degree;
    int start;
    int end;
    struct Nice *next;
}Nice;

void Dack(Nice **F, int array[MAX][MAX]);
int judge(int array[MAX][MAX]);
void Print(Nice *F);
void List(Nice **F);
int Kiss(int play[MAX], int f);

int Kiss(int play[MAX], int f)              //判断是否存在环
{
    //这个while循环是判断的关键他的原理是用while对图进行检索，play[f]数组中储存着下一个顶点的位置，组成边的首要条件是一个前驱（play[f]）和一个后继（play[f]中储存的数据）

    while(play[f] > 0)
    {
        f = play[f];                        //如果play[f]有数据则把其中的数据传给f这样就能形成循环检索
    }
    return f;
}

void List(Nice **F)                         //克鲁斯卡尔算法正文
{
    int play[MAX], m, n;
    Nice *temp;


    for(int i = 0; i < MAX; i++)            //先把play[MAX]数组初始化
    {
        play[i] = 0;
    }

    while(*F != NULL)                       //按照边集合的多少进行循环
    {
        temp = *F;                          //这里用一个临时指针temp是因为最后输出完毕后需要对已用的指针进行释放不然就会造成内存浪费

        m =Kiss(play, temp->start);         //这里个循环主要是靠这个两个函数的返回值
        n =Kiss(play, temp->end);           //当两个返回值都相同的时候就代表play[]中存在环

        if(n != m)                          //两个返回值相等及不执行本判断
        {
            play[m] = n;                    //当两个返回值不相同把该后继n数据传入数组中以作记录，数组的位置为前驱
            printf("%d %d %d\n", temp->start, temp->end, temp->degree);
        }
        *F = (*F)->next;
        free(temp);
    }

}

int judge(int array[MAX][MAX])              //判断array数组中是否以被全部筛选完毕如果全部筛选完毕及返回0，这个需要配合while循环使用
{
    for(int i = 0; i < MAX; i++ )
    {
        for(int j = i; j < MAX; j++)
        {
            if(array[i][j] != 0 && array[i][j] < INTF)
            {
                return 1;
            }
        }
    }
    return 0;
}

void Dack(Nice **F, int array[MAX][MAX])            //数组后插法生成边集数组
{
    Nice *temp, *tail;

    while(judge(array))                         //判断array数组中的数据是否都已遍历完毕如果数组中的数据只剩下0和INTF则边集数组生成完毕
    {
        temp = (Nice *)malloc(sizeof(Nice));
        temp->next = NULL;

        for(int i = 0; i < MAX; i++)            //把数组中的每个度进行筛选
        {
            for(int j = i; j < MAX; j++)        //这里注意j的初始数据是i赋予的这样就可以阶梯循环了，减少这个for循环的次数，因为无向图的数组储存是有特点的，每一行依次递增减少一个，标注为0。
            {
                if(array[i][j] != 0 && array[i][j] < INTF)      //如果没有度储存在当前下标下就掠过执行，这样可以减少if判断节省资源
                {
                    if(*F == NULL && temp == NULL)              //当array中的度第一次被传输到temp中时temp是空的所以无从比较，故而直接传输数据不进行比较
                    {
                        temp->start = i;
                        temp->end = j;
                        temp->degree = array[i][j];
                    }
                    else
                    {
                        if(temp->degree > array[i][j])          //当for循环在再次被执行传输temp数据时temp以存有数据及可进行比较，array数组中最小的那个度传给链表靠前的位置一次进行插入
                        {
                            temp->start = i;
                            temp->end = j;
                            temp->degree = array[i][j];
                        }
                    }
                }
            }
        }
        array[temp->start][temp->end] = 0;                 //已被筛选完毕的度在其中填入0标记已被执行完毕

        if(*F == NULL)                                     //尾插法
        {
            *F = temp;
        }
        else
        {
            tail->next = temp;
        }
        tail = temp;
    }

}

void Print(Nice *F)             //打印链表
{
    Nice *temp = F;
    while(temp != NULL)
    {
        printf("%d %d %d\n", temp->start, temp->end, temp->degree);
        temp = temp->next;
    }
}

int main()
{
    Nice *F = NULL;

    int array[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}
        };

        Dack(&F, array);
//      Print(F);
        List(&F);



    return 0;
}

输出结果：