详解最小生成树——Prim&Kruskal

生成树是指在一个有个点的图中由n-1条边构成的子图并且每一个点都在这个子图中，其中总边权值最小的生成树就被称为最小生成树。
如图所示：

Prim

Prim算法是通过扩展边来求最小生成树，其思路和Dijkstra非常相似，它从一个未被加入最小生成树的点开始，枚举所以从其出发的所有边，选出其中权值最小的一条边，将其加入最小生成树，将其到达的点加入最小生成树并将点标记，直到最小生成树里有n-1条边。如图所示，就是prim构造最小生成树的过程。

核心代码如下:

void prim(){
	memset(dis,0x3f,sizeof(dis));
	memset(vis,0,sizeof(vis));
	dis[1]=0;
	for(int i=1;i<n;i++){
		int x=0;
		for(int j=1;j<=n;j++){
			if(!v[j]&&(x==0||dis[j]<dis[x])){
				x=j;
			}
		}//找相邻最小边权 
		vis[x]=1;
		for(int j=1;j<=n;j++){
			if(!v[j]){
				dis[j]=min(dis[j],a[x][j]);//与当前最小权值进行比较 
			}
		}
	}
}

Kruskal

Kruskal,以下简称K，是通过扩展点来构造最小生成树，需要并查集辅助。其基本思想是将所有边权值从小到大排一个序，这样先遍历的边就一定是剩下的边中最小的然后我们就尝试将此条边加入最小生成树，如果其父亲节点是同一个，那么如果选择此条边则在最小生成树中会构造出一个环，所以我们不能选择这条边，就跳过它。如此图，即是K算法的过程。

主要代码如下：

int get(int x){
	if(fa[x]==x){
		return fa[x];
	}
	return fa[x]=get[fa[x]];
}//并查集 
bool cmp(node a,node b){
	return a.edge<b.edge;
}//结构体排序 
...
sort(a+1,a+1+tot,cmp);
for(int i=1;i<=tot;i++){
	int x=get(a[i].fro);
	int y=get(a[i].to);//求出这条边的两个端点的父亲节点 
	if(x!=y){//如果父亲节点不同 
		fa[x]=y;//合并这两个点 
		ans+=a[i].edge;
	}
}