Kruskal:
随便贴一个题吧：
//时间复杂度：时间复杂度为O（eloge）(e为网中边的数目) int v[N]; int findi(int x) { return x!=v[x]?v[x]=findi(v[x]):v[x]; } int main() { int n,m; while(~scanf("%d %d",&n,&m)&&n) { memset(v,0,sizeof v); int sum=1; for(int i=1;i<=n;i++) { v[i]=i; } while(m--) { int a,b; scanf("%d %d",&a,&b); int aa=findi(a); int bb=findi(b); if(aa!=bb) { v[bb]=aa; sum++; } } printf("%d\n",n-sum); } return 0; }
Prim：
//这里记顶点数v，边数e //邻接矩阵:O(v2) 邻接表:O(elog2v) void prim() { for(int i=1;i<=n;i++) { low[i]=m[1][i]; } vis[1]=1; for(int i=2;i<=n;i++) { int min=inf; int k=1; for(int j=1;j<=n;j++) { if(!vis[j]&&min>low[j]) { min=low[j]; k=j; } } if(min==inf) break; vis[k]=1; ans+=min; for(int j=1;j<=n;j++) { if(!vis[j]&&low[j]>m[k][j]) { low[j]=m[k][j]; } } } }
