最小生成树算法理解

约定不等于承诺〃 2022-05-18 07:18 204阅读 0赞

#                                    最小生成树算法理解 #

最小生成树的算法主要有两种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;
    }