首页 > 其他分享 >图的应用--最小生成树

图的应用--最小生成树

时间:2023-07-10 21:11:20浏览次数:34  
标签:return fa -- 最小 生成 int 顶点

图的应用--最小生成树

生成树

概念:所有顶点均由边连接在一起.但不存在回路.

一个图可以有许多不同的生成树.

生成树特点:

  1. 生成树的顶点个数与图的顶点个数相同.
  2. 生成树是图的极小联通子图,去掉一条边则非联通
  3. 一个有n个顶点的连通图的生成树有n-1条边
  4. 在生成树中再加一条边必然形成回路
  5. 生成树中任意两个顶点间的路径是唯一的

还有n个顶带n-1条边的图不一定是生成树

image-20230707104426774

image-20230707104510979

无向图的生成树

使用dfs搜索找到的生成树.叫做深度优先生成树

使用bfs搜索找到的生成树,叫做广度优先生成树.

image-20230707105647844

最小生成树的定义

给定一个无向网络,在该网的所有生成树中,使得各边权值之和最小的那颗生成树成为该网的最小生成树,也叫最小代价生成树.

image-20230707110119351

典型用途

image-20230707110459675

构造最小生成树(MST)

image-20230710095606968

在生成树的构造过程中,图中n个顶点分属两个集合:

  1. 已落在生成树上的顶点集:U
  2. 尚未落在生成树上的顶点集:V-U
  3. 接下来则应在所有连通U中顶点和V-U中顶点的边中选取权值最小的边.

image-20230710100118173

方法1:Prim算法

image-20230710101214576

方法2:Kruskal算法

直接了当的贪心,但是不能形成环.

最小生成树可能不唯一

image-20230710101834607

两种算法的比较

image-20230710102209926

P3366 【模板】最小生成树

使用并查集来构建Kruskal算法

image-20230710112056919

#include <bits/stdc++.h>
#define yes cout<<"YES"<<'\n'
#define no 	cout<<"NO"<<'\n'

using namespace std;
typedef pair<int, int> PII;
const int N = 200008;

struct Node {
	int x, y, v;
} a[N];
int fa[50008], n, m;
bool cmp(Node a, Node b) {//自定义排序按照边权的大小进行排序
	return a.v < b.v;

}
int findset(int x) {//并查集的findset
	if (fa[x] == x) {
		return x;
	}
	int y = findset(fa[x]);
	fa[x] = y; //路径压缩
	return fa[x];
}
void Kruskal() {
	for (int i = 1; i <= n; i++) {
		fa[i] = i; //并查集初始化
	}
	sort(a + 1, a + m + 1, cmp);//排序
	int ans = 0;//记录答案
	int cnt = n;//现在有几个连通块,初始化的时候有n个
	for (int i = 1; i <= m; i++) {
		int x = findset(a[i].x);
		int y = findset(a[i].y);
		if (x != y) {//如果a[i].x和a[i].y不在一个集合里面的话
			fa[x] = y;//合并两个集合
			ans += a[i].v;//将边权加入到里面
			cnt--;//连通块的数量减1
		}
		if (cnt == 1) {//如果cnt为1就退出循环
			break;
		}
	}
	if (cnt == 1) {//打印结果
		cout << ans << '\n';
	} else {
		cout << "orz" << '\n';
	}

}
int main () {

	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		cin >> a[i].x >> a[i].y >> a[i].v;
	}
	Kruskal();


	return 0;
}

P1546 [USACO3.1] 最短网络 Agri-Net

标签:return,fa,--,最小,生成,int,顶点
From: https://www.cnblogs.com/harper886/p/17542355.html

相关文章

  • 广度优先搜索(BFS)
    广度优先搜索(BFS)点亮所有的灯BFS的方法非连通图的广度优先遍历算法实现按广度优先搜索遍历连通图GBFS算法效率分析DFS和BFS算法效率比较空间复杂度相同,都是O(n)(借助栈和队列)时间复杂度与储存结构(邻接矩阵或邻接表)有关,而与搜索路径无关.......
  • JVM常用工具分析
    JVM基础分析、故障解决工具常用jdk工具jps:JvmProcessStatusTool显示系统内全部的虚拟机进程;jstat:JvmStatisticsMonitoringTool动态收集指定进程运行时数据;jinfo:ConfigurationInfoForJava实时显示或调整虚拟机的配置信息;jmap:MemoryMapForJava生......
  • 【数据结构与算法】队列算法题
    TS实现队列interfaceIQueue<T>{//入队enqueue(item:T):void;//出队dequeue():T|undefined;//队首peek():T|undefined;//是否为空isEmpty():boolean;//大小size():number;}classArrayQueue<T>implementsIQueue<T>{......
  • ssm框架使springmvc放行资源(java配置类)
    在springmvc中,如果配置了拦截所有请求交给springmvc处理,会出现一些静态web资源加载不出来的情况,或者想放行指定web资源可以通过修改通过修改配置达到相应目的,这里使用覆写WebMvcConfigurationSupport中的方法作介绍。@ConfigurationpublicclassSpringMvcSupportextendsWeb......
  • 系统托盘如何实现
    qt中有这么一个类(系统托盘类QSystemTrayIcon),但是我们要设置一些自定义功能,所以要对此类进行重写。1.如何调用:需要的地方使用自定义托盘类:MySysTray*systray=newMySysTray(this);若是仅仅在此继承类中改变图标的话,是会在托盘中显示出来的,但是却没有任何点击效果(即点击后无反应)......
  • 数学
    x的y次方使用函数pow(x,y)例如2的10次方pow(2,10)pow函数也可以用来开根号,例如开2次方根其实就是二分之一次方例如16开4次方根pow(16,1.0/4)输出注意输出是要求保留n位有效数字还是保留n位有效小数位cout输出浮点数默认保留6位有效数字printf可以自定义保留的小数位......
  • 【笔者感悟】笔者的工作感悟【二】
    写在前面在上一篇笔者的工作感悟【一】笔者讲到了一些个人经历,帮助大家从思维上学生转换到社会人士,在思维成功转换以后,接下来我们就要学会干活,除了一些比较恶劣的职场环境,大部分职场都是把活干好了才能拿到报酬,因此这里笔者想给大家分享一些拙见,帮助大家能够把活干好问题解答问......
  • CODE FESTIVAL 2017 Final J 题解
    problem&blog。萌萌点分治,积累个trick/qq。对于完全图\((V,E)\),将\(E\)分成\(E_1,E_2,\cdots,E_k\)(\(E_1\cupE_2\cup\cdots\cupE_k=E\))。对每个边集求MST,得到新边集\(E_1^{'},E_2^{'},\cdots,E_k^{'}\),再求MST。最终剩下的边集,等同于原边集的MST。......
  • HTML5
    HTML5HTML5的更新:使用网页实现动态渲染图形、图表、图像和动画,不需要安装插件直接使用网页播放视频。W3C(万维网联盟):W3C标准:结构化标准语言(HTML、XML)表现标准语言(CSS)行为标准(DOM)IDE:WebStorm块元素:无论内容多少,该元素独占一行行内元素:内容撑开宽度,左右都是行内元素的......
  • 20230710-20230711 数论
    数论被薄纱了/kk授课老师:南京大学-朱富海教授20230710裴蜀定理对于给定不全为零的整数的\(a,b\)一定存在一对整数\(x,y\)满足\(ax+by=gcd(a,b)\)。证明:\(a==0\)\(or\)\(b==0\)显然成立;设\(gcd(a,b)=d\),即求证存在\(x,y\)满足\(ax+by=d\),等式两边同时除......