C语言程序克鲁斯卡尔算法

只看该作者 · 2024-2-18 20:19

#define _CRT_SECURE_NO_WARNINGS

#include<stdio.h>



typedef struct Edge

{

        int v1, v2;

        int wight;

}Edge;



int main()

{

        int n, m;//结点数和边数

        int i, j, k = 0;

        int count = 0;

        Edge edge[100];//边集

        int vest[30];//判断是否成环的编号数组

        scanf("%d %d", &n, &m);

        for (i = 0; i < m; i++)

        {

                scanf("%d %d %d", &edge[i].v1, &edge[i].v2, &edge[i].wight);

                if(edge[i].v1 > edge[i].v2)

                {

                        int t = edge[i].v1;

                        edge[i].v1 = edge[i].v2;

                        edge[i].v2 = t;

                }

        }

        for (i = 1; i <= n; i++)//初始化编号数组

                vest[i] = i;

        for (i = 0; i < m - 1; i++)//排序

        {

                for (j = 0; j < m - i - 1; j++)

                {

                        if (edge[j].wight > edge[j + 1].wight)

                        {

                                Edge t = edge[j];

                                edge[j] = edge[j + 1];

                                edge[j + 1] = t;

                        }

                }

        }

        for (i = 0; i < m && count < n - 1; i++)

        {

                if (vest[edge[i].v1] != vest[edge[i].v2])//说明不构成环,打印

                {

                        printf("%d %d %d\n", edge[i].v1, edge[i].v2, edge[i].wight);

                        count++;

                        int flag1 = vest[edge[i].v1];

                        int flag2 = vest[edge[i].v2];

                        for (j = 1; j <= n; j++)

                        {

                                if (vest[j] == flag2)//把全部编号为flag2的结点改为flag1

                                        vest[j] = flag1;

                        }

                }

        }

        return 0;

}