你的位置:首页 > 信息动态 > 新闻中心
信息动态
联系我们

kruskal算法找最小生成树

2021-10-25 15:14:56
  1. 最小生成树的概念

对于一个顶点集为V,边集为E的无向图来说,生成树成树为:
由 V 中的全部 n 个顶点和 E 中 n−1 条边构成的无向连通子图被称为 G 的一棵生成树,其中边的权值之和最小的生成树被称为无向图 G 的最小生成树。

大白话:就是找n-1条边恰好连接n个节点,这个东西就是生成树,n-1条边的权重最小值,就是最小生成树的代价。

  1. Kuskal算法
  1. 将边按照权重由小到大排序
  2. 遍历每一条边,如果这个这个边连接的两个顶点不连通,将这条边加入答案。

思想就是贪心算法。时间复杂度取决于排序的时间,快排 0 ( m l o g m ) 0(mlogm) 0(mlogm)
其中 m = ∣ E ∣ m=|E| m=E

  1. 代码
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2e5+5;

struct Edge{
    int a, b, w;
    bool operator < (const Edge &O) const {
        return w < O.w;
    } 
}edges[MAXN];

int par[MAXN];

int find(int a) {
    if (par[a] == a) return a;
    return par[a] = find(par[a]);
}

int main() {
    int m, n;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> edges[i].a >> edges[i].b >> edges[i].w;
    }
    sort(edges, edges + m);
    for (int i = 1; i <= n; i++) {
        par[i] = i;
    }
    
    int cnt = 0,  spent = 0;
    for (int i = 0; i < m; i++) {
        int a = find(edges[i].a);
        int b = find(edges[i].b);
        if (a != b) {
            par[a] = b;
            spent += edges[i].w;
            cnt ++;
        }
    }
    if (cnt != n - 1) printf("impossible\n");
    else printf("%d\n", spent);
}

4.注意点

  1. 代码使用了并查集来判断两个顶点是否连通,并查集的par初始化一定要注意。
  2. 可以不适用临界表保存边,直接写一个重载的结构体就行了。
    对于typedef struct和struct的区别看这里。
  3. cnt保存了最小生成树边集的数目,如果需要输出可以使用数组保存边。
  1. 例题
  1. leecode 1584 模板题目