数据结构实验之图论六:村村通公路 【克鲁斯卡尔算法】

2023-03-09 17:06:15 浏览数 (1)

分析:MST,用最好理解的克鲁斯卡尔算法,其中 fin 是寻找这个点的父节点并进行路径压缩,merge 是把这两个点合并在一起,表示现在已经是相连接的了,克鲁斯卡尔算法要求需要先对边权来排序,所以首先用个结构体来存 起点 - 终点 - 权值,然后按权值从大到小排序,依次选取最小边权。

代码语言:javascript复制
#include <iostream>
#include <bits/stdc  .h>
using namespace std;
struct node
{
    int b,e;
    int w;
}s[3005];
bool cmp(struct node a, struct node b)
{
    return a.w < b.w;
}
bool vis[1005];
int c[10005];
int fin(int x)
{
    int r = x;
    while(r != c[r]){
        r = c[r];
    }
    int i = x, j;
    while(c[i] != r)
    {
        j = c[i];
        c[i] = r;
        i = j;
    }
    return r;
}
int merge(int x, int y)
{
    if(fin(x) != fin(y))
    {
        c[fin(x)] = fin(y);
        return 1;
    }
    return 0;
}
int main()
{
    int n,m,ans = 0,cnt = 0;
    while(~scanf("%d%d",&n,&m)){
            for(int i = 0; i < m; i   )
            {
                scanf("%d%d%d",&s[i].b,&s[i].e,&s[i].w);
            }
            for(int i = 0; i <= n; i   )c[i] = i;
            sort(s,s m,cmp);
            ans = 0;
            cnt = 0;
            for(int i = 0; i < m; i   )
            {
                if(merge(s[i].b,s[i].e) == 1)
                {
                    ans  = s[i].w;
                    cnt   ;
                }
                if(cnt == n - 1) break;
            }
            if(cnt == n - 1)
            {
                printf("%dn",ans);
            }
            else printf("-1n");
    }
    return 0;
}

0 人点赞