目录
一、概述
恩，最小生成树问题顾名思义，概括来说就是路修的最短。
接下来引入几个一看就明白的定义：
最小生成树相关概念：
带权图：边赋以权值的图称为网或带权图，带权图的生成树也是带权的，生成树T各边的权值总和称为该树的权。
最小生成树（MST）：权值最小的生成树。
最小生成树的性质：假设G＝(V,E)是一个连通网，U是顶点V的一个非空子集。若(u,v)是一条具有最小权值的边，其中u∈U，v∈V－U，则必存在一棵包含边(u,v)的最小生成树。
完成构造网的最小生成树必须解决下面两个问题：
（1）尽可能选取权值小的边，但不能构成回路；
（2）选取n－1条恰当的边以连通n个顶点；
prim算法适合稠密图（暂时不敢看，主要是从一个顶点出发，然后依次找最短路径的顶点，然后更新一波顶点，最后直到形成最小生成树），kruskal算法适合简单图。
关于这两个算法原理的展示这里有两个生动形象的视频可供理解，ps（真tm良心！）
二、kruskal算法
kruskal远离更为简单粗暴，但是需要借助并查集这一知识。克鲁斯卡尔算法的基本思想是以边为主导地位，始终选择当前可用的最小边权的边（可以直接快排或者algorithm的sort这个贼方便）。每次选择边权最小的边链接两个端点是kruskal的规则，并实时判断两个点之间有没有间接联通(就是看有没有形成环，形成环就肯定不是最小生成树)。
难点就是对并查集的理解，这是关键，推荐看b站一个博主正月打灯笼的并查集三讲，最原始形态的和优化的，不懂就多看看。
这是链接，请过客收下：https://www.bilibili.com/video/av38498175?from=search&seid=7867423306707863524
洛谷 3366
题目描述
如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出 orzorz
输入输出格式
输入格式：
第一行包含两个整数N、MN、M，表示该图共有 NN 个结点和 MM 条无向边。（N≤5000,M≤200000N≤5000,M≤200000）
接下来 MM 行每行包含三个整数 Xi、Yi、ZiXi、Yi、Zi，表示有一条长度为 ZiZi 的无向边连接结点Xi、YiXi、Yi
输出格式：
输出包含一个数，即最小生成树的各边的长度之和；如果该图不连通则输出 orzorz
输入输出样例
输入样例#1：
4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3
输出样例#1：
7
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,tot=0,k=0;//n端点总数，m边数，tot记录最终答案，k已经连接了多少边
int fat[200010];//记录集体老大
struct node
{
int from,to,dis;//结构体储存边
}edge[200010];
bool cmp(const node &a,const node &b)//sort排序（当然你也可以快排）
{
return a.dis<b.dis;
}
int father(int x)//找集体老大，并查集的一部分
{
if(fat[x]!=x)
return father(fat[x]);
else return x;
}
void unionn(int x,int y)//加入团体，并查集的一部分
{
fat[father(y)]=father(x);
}
int main()
{
scanf("%d%d",&n,&m);//输入点数，边数
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&edge[i].from,&edge[i].to,&edge[i].dis);//输入边的信息
}
for(int i=1;i<=n;i++) fat[i]=i;//自己最开始就是自己的老大 （初始化）
sort(edge+1,edge+1+m,cmp);//按权值排序（kruskal的体现）
for(int i=1;i<=m;i++)//从小到大遍历
{
if(k==n-1) break;//n个点需要n-1条边连接
if(father(edge[i].from)!=father(edge[i].to))//假如不在一个团体
{
unionn(edge[i].from,edge[i].to);//加入
tot+=edge[i].dis;//记录边权
k++;//已连接边数+1
}
}
printf("%d",tot);
return 0;
}
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/114886.html原文链接：https://javaforall.net
