C语言程序 克鲁斯卡尔算法求最小生成树

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

版权声明：本文内容来源于网络搜集无法获知原创作者，仅供个人学习用途，若侵犯到您的权益请联系我们及时删除。邮箱：1370723259@qq.com