最小生成树Kruscal算法(C++)-创新互联

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

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

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

我们来看这样一个东西

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

一个一个选DFS,太慢了 

那怎么办呢?

Kruscal

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

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

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

我们之前讲了并查集

想一下,可以用并查集吗

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

我们的想法就好了

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

我们来模拟一下样例

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

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

图例1

最终的最小生成树(这个图不太好,没有黄色的边出现)

再来一个 

图例2 

并查集告诉我们AC不能连

至此,最小生成树产生了

原理讲完了,我们看题

例1

登录 - 沐枫OJhttps://www.mfstem.org/p/688可以说模板题,没啥好讲的,代码里有注释讲解,自己看吧

#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;
}
练习:

登录 - 沐枫OJhttps://www.mfstem.org/p/692我的AC代码:

#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++)-创新互联
文章URL:http://pwwzsj.com/article/ihgde.html