最小生成树,克鲁斯卡尔算法入门。

最小生成树,克鲁斯卡尔算法入门。

目录

 

 

一、概述

二、kruskal算法


 

一、概述

恩,最小生成树问题顾名思义,概括来说就是路修的最短。

接下来引入几个一看就明白的定义:

最小生成树相关概念:

带权图:边赋以权值的图称为网或带权图,带权图的生成树也是带权的,生成树T各边的权值总和称为该树的权。

最小生成树(MST):权值最小的生成树。

最小生成树的性质:假设G=(V,E)是一个连通网,U是顶点V的一个非空子集。若(u,v)是一条具有最小权值的边,其中u∈U,v∈V-U,则必存在一棵包含边(u,v)的最小生成树。

完成构造网的最小生成树必须解决下面两个问题:

      (1)尽可能选取权值小的边,但不能构成回路;

      (2)选取n-1条恰当的边以连通n个顶点;

       prim算法适合稠密图(暂时不敢看,主要是从一个顶点出发,然后依次找最短路径的顶点,然后更新一波顶点,最后直到形成最小生成树),kruskal算法适合简单图。

关于这两个算法原理的展示这里有两个生动形象的视频可供理解,ps(真tm良心!)

想看点这里

二、kruskal算法

 

kruskal远离更为简单粗暴,但是需要借助并查集这一知识。克鲁斯卡尔算法的基本思想是以边为主导地位,始终选择当前可用的最小边权的边(可以直接快排或者algorithm的sort这个贼方便)。每次选择边权最小的边链接两个端点是kruskal的规则,并实时判断两个点之间有没有间接联通(就是看有没有形成环,形成环就肯定不是最小生成树)。

难点就是对并查集的理解,这是关键,推荐看b站一个博主正月打灯笼的并查集三讲,最原始形态的和优化的,不懂就多看看。

这是链接,请过客收下:https://www.bilibili.com/video/av38498175?from=search&seid=7867423306707863524

洛谷 3366

题目描述
如题,给出一个无向图,求出最小生成树,如果该图不连通,则输出 orzorz
输入输出格式
输入格式:
第一行包含两个整数N、MN、M,表示该图共有 NN 个结点和 MM 条无向边。(N≤5000,M≤200000N≤5000,M≤200000)

接下来 MM 行每行包含三个整数 Xi、Yi、ZiXi、Yi、Zi,表示有一条长度为 ZiZi 的无向边连接结点Xi、YiXi、Yi
输出格式:
输出包含一个数,即最小生成树的各边的长度之和;如果该图不连通则输出 orzorz
输入输出样例
输入样例#1:
4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3

输出样例#1:
7

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,tot=0,k=0;//n端点总数,m边数,tot记录最终答案,k已经连接了多少边 
int fat[200010];//记录集体老大 
struct node
{
	int from,to,dis;//结构体储存边 
}edge[200010];
bool cmp(const node &a,const node &b)//sort排序(当然你也可以快排) 
{
	return a.dis<b.dis;
}
int father(int x)//找集体老大,并查集的一部分 
{
	if(fat[x]!=x)
	return father(fat[x]);
	else return x;
}
void unionn(int x,int y)//加入团体,并查集的一部分 
{
	fat[father(y)]=father(x);
}
int main()
{
	scanf("%d%d",&n,&m);//输入点数,边数 
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&edge[i].from,&edge[i].to,&edge[i].dis);//输入边的信息 
	}
	for(int i=1;i<=n;i++) fat[i]=i;//自己最开始就是自己的老大 (初始化) 
	sort(edge+1,edge+1+m,cmp);//按权值排序(kruskal的体现) 
	for(int i=1;i<=m;i++)//从小到大遍历 
	{
		if(k==n-1) break;//n个点需要n-1条边连接 
		if(father(edge[i].from)!=father(edge[i].to))//假如不在一个团体 
		{
			unionn(edge[i].from,edge[i].to);//加入 
			tot+=edge[i].dis;//记录边权 
			k++;//已连接边数+1 
		}
	}
	printf("%d",tot);
	return 0;
}

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/114886.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号