一般最小生成树算法分成两种算法:
一个是克鲁斯卡尔算法:这个算法的思想是利用贪心的思想,对每条边的权值先排个序,然后每次选取当前最小的边,判断一下这条边的点是否已经被选过了,也就是已经在树内了,一般是用并查集判断两个点是否已经联通了;
另一个算法是普里姆算法:这个算法长的贼像迪杰斯塔拉算法,首先选取一个点进入集合内,然后找这个点连接的点里面权值最小的点,然后每次在选取与集合内任意一点连接的点的边的权值最小的那个(这个操作可以在松弛那里修改一下,这也是和迪杰斯塔拉算法最大的不同,你每次选取一个点后,把这个点能达到的点的那条边的权值修改一下,而不是像迪杰斯塔拉算法那样,松弛单点权值);
克鲁斯卡尔代码:
#include<iostream> #include<algorithm> #define maxn 5005 using namespace std; struct Node { int x; int y; int w; }node[maxn]; int cmp(Node x,Node y) { return x.w<y.w; } int fa[maxn]; int findfa(int x) { if(fa[x]==x) return x; else return findfa(fa[x]); } int join(int u,int v) { int t1,t2; t1=findfa(u); t2=findfa(v); if(t1!=t2) { fa[t2]=t1; return 1; } else return 0; } int main() { int i,j; int sum; int ans; int n,m; sum=0;ans=0; cin>>n>>m; for(i=1;i<=m;i++) cin>>node[i].x>>node[i].y>>node[i].w; sort(node+1,node+1+m,cmp); for(i=1;i<=n;i++) fa[i]=i; for(i=1;i<=m;i++) { if(join(node[i].x,node[i].y)) { sum++; ans+=node[i].w; } if(sum==n-1) break; } cout<<ans<<endl; return 0; } 普里姆算法: #include<iostream> #include<algorithm> #include<cstring> #include<cstdio> #define inf 0x3f3f3f using namespace std; int Map[1005][1005]; int dist[1005]; int visit[1005]; int n,m; int prime(int x) { int temp; int lowcast; int sum=0; memset(visit,0,sizeof(visit)); for(int i=1;i<=n;i++) dist[i]=Map[x][i]; visit[x]=1; for(int i=1;i<=n-1;i++) { lowcast=inf; for(int j=1;j<=n;j++) if(!visit[j]&&dist[j]<lowcast) { lowcast=dist[j]; temp=j; } visit[temp]=1; sum+=lowcast; for(int j=1;j<=n;j++) { if(!visit[j]&&dist[j]>Map[temp][j]) dist[j]=Map[temp][j]; } } return sum; } int main() { int y,x,w,z; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(i==j) Map[i][j]=0; else Map[i][j]=inf; } } memset(dist,inf,sizeof(dist)); for(int i=1;i<=m;i++) { scanf("%d%d%d",&x,&y,&w); Map[x][y]=w; Map[y][x]=w; } z=prime(1); printf("%d\n",z); return 0; }