最小生成树Kruscal算法（C++）-创新互联

求点赞，求关注，小UP想变大UP的梦想就靠你实现了！

最近新入了一个画图软件，讲讲图论再合适不过了

创新互联建站"三网合一"的企业建站思路。企业可建设拥有电脑版、微信版、手机版的企业网站。实现跨屏营销，产品发布一步更新，电脑网络+移动网络一网打尽，满足企业的营销需求！创新互联建站具备承接各种类型的网站制作、成都网站设计项目的能力。经过十年的努力的开拓，为不同行业的企事业单位提供了优质的服务，并获得了客户的一致好评。引入

我们来看这样一个东西

找到一棵树，边长之和最小，也就是最小生成树

一个一个选DFS，太慢了

那怎么办呢？

Kruscal

我们注意到，边长之和最小

那我们优先选边长之和最小就可以了呀

但要选的是一棵树，如果按这个想法，可能会有回路产生，那就不好了

我们之前讲了并查集

想一下，可以用并查集吗

我们看两个点的最老的祖先节点，如果两个是同一个点，就不能选了

我们的想法就好了

设每一条边是x-y，长度为k，我们按照k排序，如果两个点x,y的最老的祖先节点一样，那这条边就不添加

我们来模拟一下样例

选中的边红色，不能连的黄色，剩下最小的绿色，没连的蓝色

当你连了点数N-1条边，就是一颗最小生成树

图例1

最终的最小生成树（这个图不太好，没有黄色的边出现）

再来一个

图例2

并查集告诉我们AC不能连

至此，最小生成树产生了

原理讲完了，我们看题

例1

#includeusing namespace std;
#define int long long
int n,tp,f[10005],sum,ans;
struct road{//定义x,y,t
	int x;
	int y;
	int t;
}r[100005];
bool cmp(road a,road b){//排序
	return a.t< b.t;
} 
int fi(int x){
	return f[x] == x ? x : f[x] = fi(f[x]);//找最老的祖先
}
signed main(){
	cin >>n;
    for(int i = 1;i<= n;++i){
        f[i] = i;//注意初始化
        for(int j = 1,a;j<= n;++j){//读入
            cin >>a;
            if(i< j){
                ++tp;
                r[tp].x = i,r[tp].y = j,r[tp].t = a;//添加边
            }
        }
    }
	sort(r + 1,r + tp + 1,cmp);//排序
	for(int i = 1;i<= tp;++i){
		int q = fi(r[i].x),p = fi(r[i].y);//找最老的祖先
		if(q != p){
			++sum;
			f[q] = p;//认“爸爸”
			ans += r[i].t;//加边权
		}
		if(sum == n - 1){//满足要求，退出
			cout<< ans<< endl;
			return 0;
		}
	}
	return 0;
}

练习：

#includeusing namespace std;
#define int long long
int n,tp,f[2005],sum,ans,m;
struct road{
	int x;
	int y;
	int t;
}r[10005];
bool cmp(road a,road b){
	return a.t< b.t;
} 
int fi(int x){
	return ((f[x] == x) ? x : f[x] = fi(f[x]));
}
signed main(){
	cin >>n >>m;
    for(int i = 1;i<= n;++i)f[i] = i;
    for(int i = 1,p,xx,yx,tx;i<= m;++i){
        cin >>p >>xx >>yx >>tx;
        if(p == 1){
            ans += tx;
			int xxx = fi(xx),yyy = fi(yx);
            if(xxx != yyy)f[xxx] = yyy,++sum;
        }
        else{
            ++tp;
            r[tp].x = xx,r[tp].y = yx,r[tp].t = tx;
        }
    }
	if(sum >= n - 1){
		cout<< ans<< endl;
		return 0;
	}
	// cout<< tp<< endl;
	sort(r + 1,r + tp + 1,cmp);
	for(int i = 1;i<= tp;++i){
        // cout<< r[i].x<< " "<< r[i].y<< endl;
		int q = fi(r[i].x),p = fi(r[i].y);
		if(q != p){
			f[q] = p;
			ans += r[i].t;
			++sum;
			// for(int j = 1;j<= n;++j)cout<< f[j]<< " ";
			// cout<< endl;
		}
		if(sum == n - 1){
			cout<< ans<< endl;
			return 0;
		}
	}
	return 0;
}

代码我就不解释了，要做完才能看代码哟

下期讲讲基础A+B，敬请期待

拜了个拜！

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

本文名称：最小生成树Kruscal算法（C++）-创新互联
当前路径：http://cdiso.cn/article/ihgde.html

最小生成树Kruscal算法（C++）-创新互联

其他资讯