最小生成树算法理解

最小生成树的算法主要有两种Kruskal算法和Prim算法；Kruskal算法是通过逐个找短的边来去找点，最后实现最小生成树；而Prim算法是由先确定一点去找边，再通过点去找短边来实现最小生成树的。

Kruskal算法：先将所有的边进行从小到大排序，从短边开始找，若边的两个点还没有相连则这个边可以使用加入生成树，若两点已经相连则这个边不再使用，继续下一遍；因共有n个点，当找够n-1条边时说明n个点已经全部连接到一起了，又因为是从短边开始查找的，所以找到的一定是最小生成树。对于如何判断两个点是否已经相连，Kruskal算法中是运用的并查集算法来进行判断。定义一个数组f[ ]用来存储它们的祖先，也就是哪个点与它们相连，刚开始因所有点都未连接，所以f[ ]数组中存储的祖先都是他们自己，当两个点的祖先不相等时说明两个点还为相连，边就可是使用；边使用后两个点相连则f[t1]=t2；即把t1的祖先变为t2，t1、t2是调用了一个递归函数查找到的点的祖先；因为相连的点的祖先都为一个，从而可以判断出两个点是否已经相连，从而实现Kruskal算法实现最小生成树。

模板题n个点m条边：

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int f[100010];
struct nate
{
	int x;
	int y;
	int z;
}q[1000010];
int cmp(struct nate a,struct nate b)
{
		return a.z<b.z;
}
int get(int i)//查找祖先 
{
	if(f[i]==i)
		return i;
	else
	{
		f[i]=get(f[i]);
		return f[i];
	}
}
int merge(int u,int v)
{
	int t1,t2;
	t1=get(u);
	t2=get(v);
	if(t1!=t2)//若不相等即不同祖先还未相连 
	{
		f[t2]=t1;
		return 1;
	}
	return 0;
}
int main()
{
	int i,j,n,m,count,sum;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		for(i=1;i<=m;i++)
			scanf("%d%d%d",&q[i].x,&q[i].y,&q[i].z);
		sort(q+1,q+m+1,cmp);//对边进行排序 
		count=0;
		sum=0;
		for(i=1;i<=n;i++)//初始化，祖先都为自己 
			f[i]=i;
		for(i=1;i<=m;i++)
		{
			if(merge(q[i].x,q[i].y)==1)//判断是否已经相连 
			{
				count++;
				sum=sum+q[i].z;
			}
			if(count==n-1)
				break;
		}
		printf("%d\n",sum);
	}
	return 0;
}

Prim算法：先把各个点之间的距离存入到一个二维数组中，与求最短路的迪杰斯特拉算法类似，迪杰斯特拉算法的dis[ ]数组存储的是个点到处发点的最小距离，而Prim算法dis[ ]数组存储个点到生成树的最小距离；Prim算法从一个点开始找，各点到生成树的最小距离即为个点到这个点的距离，在dis[ ]数组中找到最小的且还没加入生成树的，找到的最小值与之有关的点加入生成树并标记，在根据刚加入生成树的点更新dis[ ]数组，如果之前到某一未加入生成树的点的距离可以变小就更新，更新完后继续找未加入生成树dis[ ]数组的最小值；因为每次确定了一个dis[ ]数组最小值，即每次确定了一条边，循环n-1次找到n-1条边实现最小生成树。

模板题n个点及各点间的距离：

#include<stdio.h>
#include<string.h>
# define inf 99999999
int map[1010][1010];
int dis[1010],book[1010];
int main()
{
	int n,i,j,u,v,count,sum,min;
	while(scanf("%d",&n)!=EOF)
	{
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
				scanf("%d",&map[i][j]);
		memset(book,0,sizeof(book));
		for(i=1;i<=n;i++)
			dis[i]=map[1][i];//初始化dis[]数组 
		book[1]=1;
		sum=0;
		for(i=1;i<n;i++)
		{
			min=inf;
			for(j=1;j<=n;j++)//查找为加入生成树，且dis[]数组的最小值 
			{
				if(book[j]==0&&dis[j]<min)
				{
					min=dis[j];
					u=j;
				}
			}
			book[u]=1;//最小的加入生成树 
			sum=sum+dis[u];
			for(v=1;v<=n;v++)
			{
				if(book[v]==0&&dis[v]>map[u][v])//判断能否更新 
					dis[v]=map[u][v];
			}
		}
		printf("%d\n",sum);
	}
	return 0;
}