最小生成树————普利姆和克鲁斯卡尔

最小生成树定义：

一个无向图，任意两个顶点都是联通的，并且是一个树，这棵树就叫生成树。如果边上有权值，使边的权值和最小的生成树叫做最小生成树。

求解最小生成树有两个算法，克鲁斯卡尔（Kruskal）算法和普利姆（Prim）算法。

注意：一个完整的最小生成树只需要顶点个数减一条边

先来讲克鲁斯卡尔：

把边的权值，从小到大查看一遍，如果不产生圈，就把当前边加入生成树中。

如何判断是否产生圈，假设要把连接顶点v和u的边e加入树种，如果u和v不在同一个连通分量里，那么加入e也不会产生圈。可用并查集判断两个顶点是否在一个连通分量里。复杂度O(E*log V) E是边的个数，V是顶点个数。

模板代码：

struct edge{int u,v,cost;};bool cmp1(const edge &a,const edge &b){return a.cost<b.cost;}int par[MAX_N];void init(){for(int i=0;i<=n;i++)par[i]=i;}int find(int x){if(par[x]==x)return x;elsereturn par[x]=find(par[x]);}int kr(){sort(a,a+m,cmp1);init();int cns=0,res=0;for(int i=0;i<m;i++){edge c=a[i];if(find(c.u)!=find(c.v)){par[find(c.u)]=find(c.v);res+=c.cost;if(maxx<c.cost){maxx=c.cost;k=i;}cns++;if(cns>=n-1)break;}}return res;}

普利姆

代码模板：

int prime(){for(int i=1;i<=n;i++){mincost[i]=INF;used[i]=false;}mincost[1]=0;int res=0;while(true){int v=-1;for(int i=1;i<=n;i++){if(!used[i]&&(v==-1||mincost[i]<mincost[v]))v=i;}if(v==-1) break;used[v]=true;res+=mincost[v];for(int i=1;i<=n;i++){mincost[i]=min(mincost[i],cost[v][i]);}}return res;}