最小生成树 Prim和Kruskal

• 感觉挺简单的,Prim和Dijkstra差不多,Kruskal搞个并查集就行了,直接上代码吧,核心思路都是找最小的边.

• Prim

  int n,m;
  int g[N][N];
  int u,v;
  int dis[N];
  bool st[N];
  
  int prim(){
  	me(dis,INF,sizeof(dis));
  
  	int res=0;
  	for(int i=0;i<n;++i){
  		int t=-1;
  		for(int j=1;j<=n;++j){
  			if(!st[j] && (t==-1 || dis[t]>dis[j])) t=j;
  		}
  		if(i && dis[t]==INF) return INF;
  		if(i) res+=dis[t];
  
  		for(int j=1;j<=n;++j){
  			dis[j]=min(dis[j],g[t][j]);
  		}
  
  		st[t]=true;
  	}
  	return res;
  }
  
  int main() {
      scanf("%d %d",&n,&m);
  
      me(g,INF,sizeof(g));
  
      for(int i=1;i<=m;++i){
      	int a,b,c;
      	scanf("%d %d %d",&a,&b,&c);
      	g[a][b]=g[b][a]=min(g[a][b],c);
      }
  
      int t=prim();
  
      if(t==INF) puts("impossible");
      else printf("%d\n",t);
  
      return 0;
  }
  

• Kruskal

  struct misaka{
  	int a,b;
  	int val;
  }e[N];
  
  int n,m;
  int p[N];
  
  bool cmp(misaka n,misaka m){
  	return n.val<m.val;
  }
  
  int find(int x){
  	if(p[x]!=x) p[x]=find(p[x]);
  
  	return p[x];
  }
  
  int main() {
       scanf("%d %d",&n,&m);
  
       for(int i=0;i<m;++i){
       	int a,b,val;
       	scanf("%d %d %d",&a,&b,&val);
       	e[i]={a,b,val};
       }	
  
       sort(e,e+m,cmp);
  
       for(int i=1;i<=n;++i)   p[i]=i;
  
       int res=0;
       int cnt=0;
  
       for(int i=0;i<m;++i){
       	int a=e[i].a;
       	int b=e[i].b;
       	int val=e[i].val;
  
       	a=find(a);
       	b=find(b);
  
       	if(a!=b){
       		p[a]=b;
       		res+=val;
       		cnt++;
       	}
       }
  
       if(cnt<n-1) puts("impossible");
       else printf("%d\n",res);
  
      return 0;
  }
  

最小生成树 Prim和Kruskal

原文：https://www.cnblogs.com/lr599909928/p/13372190.html