克鲁斯卡尔算法(Kruskal)
-
思路
① $将所有边按权重从小到大排序$ O(mlogn)
② $枚举每条边a,b、权值c$ O(m)
$if (a,b)不连通$
$将这条边加入到集合中$
该算法运用了排序和并查集相结合,使用结构体存储边的值。
res
存储的是最小生成树当中所有树边的权重之和。cnt
存储的是当前共加了多少条边
-
步骤
-
对输入的所有的边进行从排序从小到大排序
- 初始化并查集
- 遍历所有的边,查找当前边的两个节点所在的集合
- 如果不在同一个集合,就将节点 $a$ 加入到节点 $b$ 的集合中,并将 $res$ 值加上当前边的权值,将 $cnt$ 加1
-
最后,如果 $cnt$ 的值小于 $n-1$,说明该图无法构成最小生成树,返回false。否则返回 $res$ 的值
-
例题
给定一个 $n$ 个点 $m$ 条边的无向图,图中可能存在重边和自环,边权可能为负数。
求最小生成树的树边权重之和,如果最小生成树不存在则输出 impossible
。
给定一张边带权的无向图 $G=(V,E)$,其中 $V$ 表示图中点的集合,$E$ 表示图中边的集合,$n=|V|$,$m=|E|$。
由 $V$ 中的全部 $n$ 个顶点和 $E$ 中 $n−1$ 条边构成的无向连通子图被称为 $G$ 的一棵生成树,其中边的权值之和最小的生成树被称为无向图 $G$ 的最小生成树。
-
输入格式
第一行包含两个整数 $n$ 和 $m$。
接下来 $m$ 行,每行包含三个整数 $u,v,w$ 表示点 $u$ 和点 $v$ 之间存在一条权值为 $w$ 的边。
-
输出格式
共一行,若存在最小生成树,则输出一个整数,表示最小生成树的树边权重之和,如果最小生成树不存在则输出 impossible
。
-
数据范围
$1≤n≤105$,
$1≤m≤2∗105$,
图中涉及边的边权的绝对值均不超过 $1000$。
-
输入样例:
4 5
1 2 1
1 3 2
1 4 3
2 3 2
3 4 4
-
输出样例:
6
-
代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1e5+10, M = 2e5+10, INF = 0x3f3f3f3f;
struct Edge{
int a,b,c;
bool operator<(const Edge &e) const
{
return c < e.c;
}
}edge[M];
int p[N], n, m;
int find(int x)
{
if(p[x] != x) return p[x] = find(p[x]);
return p[x];
}
int Kruskal()
{
sort(edge, edge+m);
for(int i = 1; i <= n; i++) p[i] = i;
int res = 0, cnt = 0;
for(int i = 0; i < m; i++)
{
int a = edge[i].a, b = edge[i].b, c = edge[i].c;
int pa = find(a), pb = find(b);
if(pa != pb)
{
p[pa] = pb;
res += c;
cnt++;
}
}
if(cnt < n-1) return INF;
else return res;
}
int main()
{
cin >> n >> m;
for(int i = 0; i < m; i++)
{
int a,b,c;
cin >> a >> b >> c;
edge[i] = {a,b,c};
}
int t = Kruskal();
if(t == INF) puts("impossible");
else cout << t << endl;
return 0;
}