最小生成树
\(n\) 个点用 \(n-1\) 条边连接成一个连通块,形成的图形只可能是树
一个有 \(n\) 个点的连通图,边一定是大于等于 \(n-1\) 条的。图的最小生成树,就是在这些边中选择 \(n-1\) 条出来,连接所有的 \(n\) 个点。这 \(n-1\) 条边的边权之和是所有方案中最小的。
Prim算法
适用于稠密图,时间复杂度 \(O(n^2)\)
核心思想:每次挑一条与当前集合相连的最短边。
// vis[i] 表示点i是否在当前生成树集合中
// dis[i] 表示点i到当前集合的最短边的长度
// g[i][j] 表示点i和点j的边权
// 返回值:最小生成树中所有边的总长度
int Prim() {
int mst = 0;
memset(dis, 0x7f, sizeof(dis));
memset(vis, 0, sizeof(vis));
dis[1] = 0; //选 1 当起点
for (int i = 1; i < n; i++) {
int k = -1, minn = INF;
// 寻找最短边
for (int j = 1; j <= n; j++) {
if (!vis[j] && dis[j] < minn) {
k = j;
minn = dis[j];
}
}
vis[k] = true;
mst += dis[k];
// 用新加入的点 k 更新到邻接点的最短边
for (int j = 1; j <= n; j++) {
if (!vis[j]) dis[j] = min(dis[j], g[k][j]);
}
}
return mst;
}
Kruskal算法
适用于稀疏图,时间复杂度 \(O(m\log m)\)
核心思想:按照边权升序排列,从小到大选边,如果不构成环,则加入mst,否则跳过。
const int N = 1e5 + 10;
const int M = 1e6 + 10;
//存边
struct Edge {
int from, to, w;
bool operator < (const Edge &A) const {
return w < A.w;
}
} edge[M];
int n, m; //n个点,m条边
int fa[N]; //并查集
//并查集初始化
void init() {
for (int i = 1; i <= n; i++) fa[i] = i;
}
//递归找根结点,路径压缩
int find1(int x) {
if (fa[x] != x) fa[x] = find1(fa[x]);
return fa[x];
}
//非递归找根结点,路径压缩
int find2(int x) {
int tmp = x, rt;
while (fa[x] != x) x = fa[x];
rt = x;
x = tmp;
while (fa[x] != x) {
tmp = fa[x];
fa[x] = rt;
x = tmp;
}
return rt;
}
void kruskal() {
int mst = 0, cnt = 0, k = 1, rx, ry;
while (cnt < n-1) { //找 n-1 条边
rx = find1(edge[k].from);
ry = find1(edge[k].to);
if (rx != ry) {
mst += edge[k].w;
fa[rx] = ry;
cnt++;
}
}
cout << mst << endl;
}
int main() {
cin >> n >> m; //输入点数、边数
int from, to, w;
init();
for (int i = 1; i <= m; i++) {
cin >> edge[i].from >> edge[i].to >> edge[i].w;
}
sort(edge+1, edge+1+m);
kruskal();
return 0;
}
标签:const,个点,int,最小,生成,edge,模板,dis
From: https://www.cnblogs.com/kuangbiaopilihu/p/17989860