图论——最小生成树

这篇具有很好参考价值的文章主要介绍了图论——最小生成树。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

No.1 概念

想了解最小生成树,首先得明白什么是生成树。

生成树的概念:包含连通图中所有的顶点,且任意两顶点之间有且仅有一条通路。

那什么是最小生成树?

最小生成树(Minimum Spanning Trees)的概念:连通图的一颗生成树(Spanning Tree)是包含图的所有顶点的连通无环子图(也就是一棵树)。加权连通图的一颗最小生成树是图的一颗权重最小的生成树,其中,树的权重定义为所有边的权重总和。最小生成树问题就是求一个给定的加权连通图的最小生成树问题。

直接地讲,它就是在无向图中选择边把图的所有的节点连接成一棵树,要求边权之和最小。


No.2 Prim算法

1)Prim算法是什么?

Prim算法通过一系列不断扩张的子树来构造一棵最小生成树。

2)Prim算法的思想

  1. 我们从图的顶点集合中任意选择的一个单项点,作为序列中的初始子树。
  2. 每一次迭代时,以一种贪心的思想来扩张当前的生成树,即把不在树的最近顶点添加到树中(我们所说的最近顶点,是指一个不在树中的顶点,它以一条边权最小的边和树中的顶点相连,而树的形状是无所谓的)。
  3. 当图的所有顶点都包含在所构造的树中以后,该算法就停止了。

3)Prim算法需注意的点

其实Prim算法的思想和Dijkstra相像,都是分两部分来操作。

4)举栗

如图,我们确定一个起点编号1,将1加入1号阵营。设变量mst求最小生成树。mst此时为0。

图论——最小生成树

顶点编号 1 2 3 4 5
连接边 2 4 5 1 1
边权 1 2 1 2 3
阵营 1 0 0 0 0

找到与1相连边权最小的顶点2,加入1号阵营,mst+=1。

顶点编号 1 2 3 4 5
连接边 2 4 5 1 1
边权 1 2 1 2 3
阵营 1 1 0 0 0

找到与2相连边权最小的顶点4,加入1号阵营,mst+=2。

顶点编号 1 2 3 4 5
连接边 2 4 5 3 1
边权 1 2 1 2 3
阵营 1 1 0 1 0

找到与4相连边权最小的顶点3,加入1号阵营,mst+=2。

顶点编号 1 2 3 4 5
连接边 2 4 5 3 1
边权 1 2 1 2 3
阵营 1 1 1 1 0

找到与3相连边权最小的顶点5,加入1号阵营,mst+=1。

顶点编号 1 2 3 4 5
连接边 2 4 5 3 1
边权 1 2 1 2 3
阵营 1 1 1 1 1

此时,所有顶点已加入确定最小生成树的阵营,退出循环,答案mst为6.

5)Prim算法的优化

Prim算法思想上与Dijkstra算法相似,优化也区别不大。

我们可以定义一个优先队列,队列中元素记录了节点的编号和节点和树中的顶点相连的边权,将源点压入队列。当队列非空,执行以下操作:

1.u等于队顶的节点,w等于队顶节点的最短边权。

2.遍历u的所有边,如果能找到节点v小于v的当前值,更新v,将v压入队列。

以上就实现了优化。

6)核心代码

Code


void Prim(int s){
	memset(d,0x3f,sizeof(d));
	memset(vis,0,sizeof(vis));
	d[s]=0;
	q.push(node(s,0));
	while(!q.empty()){
		int u=q.top().u;
		q.pop();
		if(vis[u]){
			continue;
		}
		mst+=d[u];
		vis[u]=1;
		for(int i=0;i<Graph[u].size();i++){
			int v=Graph[u][i].v;
			long long w=Graph[u][i].w;
			if(d[v]>w){
				d[v]=w;
				q.push(node(v,w));
			}
		}
	}
}

7)Prim算法总结

Prim算法优化后节省了很多时间,用于稠密图,也就是边多的图较好。


No.3 Kruskal算法

1)Kruskal算法是什么?

Kruskal算法按照权值从小到大的顺序选择 n-1 条边,并保证这 n-1 条边不构成回路

2)Kruskal算法的思想

使用并查集,(并查集是什么?-Link)将加权图每个顶点都看做森林,然后将图中每条邻接边的边权按照升序的方式进行排列,接着从排列好的邻接边表中抽取边权最小的边,写入该边的起始顶点和结束顶点,连接顶点将森林构成树,然后读取起始结束顶点的邻接边,优先抽取边权小的邻接边,继续连接顶点将森林构成树。

添加邻接边的要求是加入到图中的邻接边不构成回路(环)。如此反复进行,直到已经添加n-1条边为止。

3)Kruskal算法的目标

Kruskal根据边权以递增的方式逐渐建立最小生成树,是以边为目标去构建最小生成树。

4)核心代码

Code

 void Kruskal(){
    sort(ed+1,ed+m+1,cmp);
    for(int i=1;i<=m;i++){
        int p=FindSet(ed[i].u);
        int q=FindSet(ed[i].v);
        if(p!=q){
            UnionSet(p,q);
            mst+=ed[i].bq;
            if(si[q]==n){
                return;
            }
        }
    }
}

5)Kruskal算法总结

Kruskal算法易理解,易上手,时间复杂度也很低,用于稀疏图,也就是点多的图较好。


完结!

 文章来源地址https://www.toymoban.com/news/detail-411939.html

到了这里,关于图论——最小生成树的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【图论】最小生成树的应用

    P1550 [USACO08OCT] Watering Hole G - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 1.我们是要使所有的农场都要有水 2.可以从起点引水,也可以互相引水。 3.费用要最小 这时我们可以想到最小生成树,建立一个虚拟节点即可。思路一目了然。 当看到这些条件,可以想到最小生成树 1.涉及

    2024年02月10日
    浏览(40)
  • 【图论】最小生成树(python和cpp)

    本帖持续更新中 如有纰漏望指正! (a)点云建立的k近邻图 (b)k近邻图上建立的最小生成树 最小生成树 (Minimum Spanning Tree,简称 MST) 是一种在带权无向图中的树,它连接了图中所有节点并且总权重最小。在最小生成树中,任意两个节点之间有且仅有一条路径,同时这些路径

    2024年02月05日
    浏览(35)
  • [图论第三节]最小生成树/二分图

    Prim算法 朴素版Prim O(n^2) 稠密图 步骤: S:表示最小生成树的集合 初始化距离 找距离集合S最近的节点 将节点加入集合S 用该节点更新非S点到集合S点的距离 代码: 堆优化版Prim O(mlogn) 用堆优化找最短距离的过程将O(n)--O(1) Kruskal算法 O(mlogm) 稀疏图 步骤: 将所有边的权值从小

    2024年02月14日
    浏览(36)
  • 【蓝桥杯--图论】最小生成树prim、kruskal

    今日语录: 成功不是终点,失败不是致命,勇气才是取胜的关键。

    2024年01月24日
    浏览(47)
  • 【刷题】图论——最小生成树:Prim、Kruskal【模板】

    假设有n个点m条边。 Prim适用于邻接矩阵存的稠密图,时间复杂度是 O ( n 2 ) O(n^2) O ( n 2 ) ,可用堆优化成 O ( n l o g n ) O(nlogn) O ( n l o g n ) 。 Kruskal适用于稀疏图,n个点m条边,时间复杂度是 m l o g ( m ) mlog(m) m l o g ( m ) 。 Prim:遍历n次,每次选择 连通块和外面的点 到连通块距离

    2024年04月13日
    浏览(43)
  • 图论与算法(遍历、最小生成树、最短路径)

    图是由顶点集合及顶点间的关系组成的一种数据结构:G = (V, E),其中:顶点集合V = {x|x属于某个数据对象集}是有穷非空集合;E = {(x,y)|x,y属于V}或者E = {x, y|x,y属于V Path(x, y)}是顶点间关系的有穷集合,也叫做边的集合。(x, y)表示x到y的一条双向通路,即(x, y)是无方向的;Path

    2024年04月14日
    浏览(44)
  • 图论基本知识--->最短路练习--->最小生成树

    自环 重边 孤点 简单图 有向图,无向图 简单图: 无向图的度数 有向图的度数:出度,入度 每个图的最大度,最小度 完全图(无向图): 完全图(有向图): 子图,生成子图: 补图:点集相同,边集不相交,并集为完全图 连通图,连通块: 图的储存方式:邻接矩阵,邻

    2024年01月23日
    浏览(60)
  • 图论13-最小生成树-Kruskal算法+Prim算法

    基本思想:按照权值从小到大的顺序选择 n-1 条边,并保证这 n-1 条边不构成回路 具体做法:首先构造一个只含 n 个顶点的森林,然后依权值从小到大从连通网中选择边加入到森林中,并使森林中 不产生 回路,直至森林变成一棵树为止。 2.2.1 如果图不联通,直接返回空,该

    2024年02月01日
    浏览(46)
  • 图论的高级技巧:最小生成树和最大匹配

    图论是一门关于研究图的数学学科,它在计算机科学、数学、物理、生物学等多个领域中发挥着重要作用。图论可以用来解决许多实际问题,如路径问题、循环问题、最小生成树问题、最大匹配问题等。在本文中,我们将深入探讨图论的两个重要领域:最小生成树和最大匹配

    2024年02月03日
    浏览(34)
  • 【算法每日一练]-图论(保姆级教程篇7 最小生成树 ,并查集模板篇)#村村通 #最小生成树

    目录 题目:村村通 并查集  题目:最小生成树 kruskal算法 prim算法          先引入问题: 要在n个城市之间铺设光缆,主要目标是要使这 n 个城市的 任意两个之间都可以通信 ,但铺设光缆的费用很高,且各个城市之间铺设光缆的费用不同,因此另一个目标是要 使铺设光

    2024年02月04日
    浏览(76)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包