首先是prim算法，也是我最开始接触的最小生成树算法，类似dij选点
#include<bits/stdc++.h>
using namespace std;
int dis[100001],ans=0;
bool vis[10001];
vector<int >g[10001],w[1000001];
int main()
{
int n,m;
cin >> n >> m;
for(int i = 1;i<=m;i++)
{
int x,y,z;
cin >> x >> y >> z;
g[x].push_back(y);
w[x].push_back(z);
g[y].push_back(x);
w[y].push_back(z);
}
memset(dis,0x3f,sizeof(dis));
dis[1]=0;
for(int k = 1;k<=n;k++)
{
int u,minn=1e9;
for(int i = 1;i<=n;i++)
{
if(dis[i]<minn && !vis[i])
{
minn=dis[i];
u=i;
}
}
vis[u]=1;
ans+=dis[u];
for(int i = 0;i<g[u].size();i++)
{
int v=g[u][i];
dis[v]=min(dis[v],w[u][i]);
}
}
for(int i = 1;i<=n;i++)
{
if(!vis[i])
{
cout << "orz";
return 0;
}
}
cout << ans;
return 0;
}
prim算法擅长稠密图，但不适合解决稀疏图
接下来是kruskal算法，该算法是将边按权从小到大排序，接着枚举边，若边为树边（即两端不在一个连通块里），可以用并查集维护
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=300100;
int n,k,ans,f[N],num,sum=0,dis[N];
inline int read(){register int x=0,f=1;register char ch=getchar();while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
struct Node
{
int u,v,w;
}a[N];
int find(int x)
{
return f[x] == x ? f[x] : f[x] = find(f[x]);
}
void bin(int x,int y)
{
f[find(y)]=f[find(x)];
}
void init()
{
for(int i = 1;i<=30010;i++) f[i]=i;
}
bool cmp(Node x,Node y)
{
return x.w<y.w;
}
signed main()
{
init();
cin >> n >> k;
for(int i = 1;i<=k;i++)
{
a[i].u=read(),a[i].v=read(),a[i].w=read();
}
sort(a+1,a+1+k,cmp);
for(int i = 1;i<=k;i++)
{
if(ans==n-1) break;
if(find(a[i].u)==find(a[i].v)) continue;
else
{
bin(a[i].u,a[i].v);
ans++;
sum+=a[i].w;
}
}
if(ans!=n-1)
{
// cout<<ans<<endl;
puts("orz");
}
else
cout<<sum<<endl;
return 0;
}
与prim相反,kruskal算法擅长解决稀疏图而不是稠密图
另外，kruskal还有kruskal重构树 ，即在建立kruskal生成树过程中通过建立新节点连接两个端点，不难发现，原图中两个点之间的所有简单路径上最大边权的最小值 = 最小生成树上两个点之间的简单路径上的最大值 = Kruskal 重构树上两点之间的 LCA 的权值。