最小生成树
最小生成树问题对应的基本是无向图。O(n^2)
含有两个基本常用算法O(mlogn)
1.Prim算法:
朴素版Prim算法(稀疏图)
堆优化版的Prim算法(稠密图)
2.Kruskal算法:O(mlogm)
一般稠密图使用朴素版的Prim算法,稀疏图用Kruskal算法
算法基本思路
朴素Prim算法同Dijkstra算法很相似,学过408的都知道这两个算法如果用在全是正值的路径中求出的最短路径是一样的,利用的都是贪心原理。
dist[i]<-(+无穷)
for(int i=0;i<n;i++)
t<-找到集合外距离最近的点
用t更新其他点到集合(此处Dijk是起点,这就是两者区别)的距离
st[t]=true;
C++ 代码
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=510,INF=0x3f3f3f3f;
int n,m;
int g[N][N];
int dist[N];
bool st[N];
int prim()
{
memset(dist,0x3f,sizeof dist);
int res=0;//存的是最小生成树里面所有边的长度之和
for(int i=0;i<n;i++)//每次找当前集合y中距离最小的点
{
int t=-1;
for(int j=1;j<=n;j++)
if(!st[j]&&(t==-1||dist[t]>dist[j]))
t=j;
if(i&&dist[t]==INF) return INF;
if(i) res+=dist[t];
//用t更新一下该点到其他点的距离,表示该点到集合的距离
for(int j=1;j<=n;j++) dist[j]=min(dist[j],g[t][j]);
st[t]=true;
}
return res;
}
int main()
{
scanf("%d%d",&n,&m);
memset(g,0x3f,sizeof g);
while(m--)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
g[a][b]=g[b][a]=min(g[a][b],c);//因为G为无向边的图所以存两次,有重复的路径存储最小的那条即可
}
int t=prim();
if(t==INF) puts("impossible");
else printf("%d\n",t);
return 0;
}