最小生成树

爱被打了一巴掌 2022-05-30 08:56 177阅读 0赞

有n个城市，m条道路，现在输入n到m的道路的长度，用最少的边将图连接，输出让图连接的最小值

这道题我研究了好长时间才把答案看明白，现在给大家分享一下

具体代码如下

#include<iostream>
    using namespace std;
    struct edge
    {
    	int u;
    	int v;
    	int w;
    };//用一个结构体来保存从城市u到城市v的距离w 
    struct edge e[10];//有小于10条路 
    int n,m;//定义n个城市，m条路  
    int f[7]={0},sum=0,count=0;
    void quicksort(int left,int right)
    {
    	int i,j;
    	struct edge t;//定义一个中间转换变量 
    	if(left>right)//如果左边大于右边结束 
    	return;
    	i=left;//i等于左，j等于右 
    	j=right;
    	while(i!=j)
    	{
    		while(e[j].w>=e[left].w&&i<j)//e[left].w是基准数 
    		j--;//往左走 
    		while(e[i].w<=e[left].w&&i<j)
    		i++;//往右走 
    		if(i<j)//交换两个数的位置 
    		{
    			t=e[i];
    			e[i]=e[j];
    			e[j]=t;
    		}
    		
    	}
    	//将基准数归位 
    	t=e[left];
    	e[left]=e[i];
    	e[i]=t;
    	quicksort(left,i-1);//继续往左递归处理 
    	quicksort(i+1,right);// 继续往右递归处理 
    	return;
    }
    //查并集寻找祖先的函数 
    int getf(int v)
    {
    	if(f[v]==v)
    	return v;
    	else
    	{
    		f[v]=getf(f[v]);
    		return f[v]; 
    	}
    }
    //并查集合并两子集合的函数 
    int merge(int v,int u)//v表示出发城市，u表示到达城市 
    {
    	int t1,t2;
    	t1=getf(v);
    	t2=getf(u);
    	if(t1!=t2)
    	{
    		f[t2]=t1;
    		return 1;
    	}
    	return 0;
    }
    int main()
    {
    	 int i;//定义一个循环变量
    	 cin>>n>>m;//输入一共有n个城市，m条路 
    	 for(i=1;i<=m;i++)
    	 cin>>e[i].u>>e[i].v>>e[i].w;//输入从第u个城市到第v个城市的距离w 
    	 quicksort(1,m);//用快速排序的方式按距离从小到大枚举出1到m条边 
    	 for(i=1;i<=n;i++)//并查集初始化 
    	 f[i]=i;
    	 //Kruskal算法核心部分代码 
    	 for(i=1;i<=m;i++)//枚举从小到大的每一条边 
    	 {
    	 	//判断一条边的两个顶点是否已经连通，即判断是否在统一集合中 
    	 	if(merge(e[i].u,e[i].v))//如果目前不连接，则选这条边 
    	 	{
    	 		count++;
    	 		sum=sum+e[i].w;
    	 	}
    	 	if(count==n-1)//选用n-1条边，跳出循环 
    	 	break;
    	 }
    	 cout<<sum<<endl;//输出最短距离 
    	 return 0;
    }

博主本身也是小白，希望大家在评论区分享更好的方法，大家相互学习，共同进步