百度360必应搜狗淘宝本站头条
当前位置:网站首页 > 技术教程 > 正文

《算法导论》随笔3-1 Kruskal算法 第23章

csdh11 2025-03-18 21:05 1 浏览

这个是图论的倒数第二章。我会着重讲解最小生成树和拓扑排序两个算法。如果哪些地方我写错的,或者没写清楚的,可以评论区吐槽~

先看一道洛谷上面的题目。



题目大意就是给n个点,m对长度,求一个最小生成树。

什么叫做最小生成树?我们之前讲树的时候提到过,树一共有n-1条边,然后每条边都是一个割边—删去这条边,图就不连通。最小生成树就像上题所说,找出一部分边,保证整个图是联通的,并且所有边的长度最小。

我们再仔细思考一下,要保证边的总长度最小,是不是必须要是一棵树?可以说是的,如果这一张图,某条边不是割边(删除后依旧是连通图),那么我们删去他,也能满足条件,并且边的长度更小。(这里的前提是所有边的权值是正数)同时,如果所有的边都是割边,那显然这应该是一棵树。

好的。我们该如何找到这棵树?

很明显,我们能想到一个贪心的算法。实际上我们的目标就是找到n-1条长度最小的边,然后要保证这些边能使得所有点连通。

我们来试一试。下面有一张图。





这个算法叫Kruskal算法。时间复杂度O(ElgV)

我重新描述一下整个算法过程。

1. 先将所有的边按照长度从小到8大排序。

2. 从小到大遍历。如果这条边没必要连接(连接会导致成环),就舍弃这条边;否则我们就将这条边连起来。

3. 最后形成的图就是最小生成树。

并查集可以让我们知道两个区块是否联通,我们只要判断这条边连接的两个点是否是联通的就行(即根节点是否相同)

洛谷标程如下:

#include<bits/stdc++.h>

#define ll long long

using namespace std;

ll fa[100005];

struct node{

ll x,y,c;

}a[100005]; //代表每条边连接x和y长度为c

ll n,m;

ll find_fa(ll x){return x!=fa[x]?fa[x]=find_fa(fa[x]):x;} //并查集核心算法

bool cmp(node x,node y){return x.c<y.c;} //边排序

ll read(){ //快读

char c=getchar();ll x=0;

while(!isdigit(c)) c=getchar();

while(isdigit(c)){x=x*10+c-'0';c=getchar();}

return x;

}

int main(){

n=read();m=read();

ll ans=0;

for(ll i=1;i<=m;i++){a[i].x=read();a[i].y=read();a[i].c=read();}

for(ll i=0;i<n;i++) fa[i]=i;

sort(a+1,a+1+m,cmp);

for(ll i=1;i<=m;i++){

ll fx=find_fa(a[i].x),fy=find_fa(a[i].y);

if(fx!=fy){

ans+=a[i].c;

fa[fx]=fy;

}

}

cout<<ans<<endl;

return 0;

}

存稿用完啦!大家有问题可以留言~

相关推荐

deepseek VS chatgpt (399)—— 算法导论25.2 8题

八、给出一个〇(VE)时间复杂度的算法来计算有向图G=(V,E)的传递闭包。如果要写代码,请用go语言。chatgpt:...

智能算法导论 第十章 差分进化算法

遗传算法流程:1.初始化种群2.选择操作:根据适应度函数选择个体,将其复制到下一代3.交叉操作:将选择的个体随机组合,生成新的个体...

deepseek VS chatgpt (400)-- 算法导论25.2 9题

九、假定我们可以在的时间内计算出一个有向无环图的传递闭包,其中是一个自变量为和的单调递增函数。证明:计算一个通用的有向图,的传递闭包的时间复杂度为。如果要写代码,请用go语言。...

文心一言 VS 讯飞星火 VS chatgpt (370)—— 算法导论24.4 2题

二、请给出下面差分约束系统的可行解或证明该系统没有可行解。...

deepseek VS chatgpt (398)—— 算法导论25.2 6题

六、我们怎样才能使用Floyd-Warshall算法的输出来检测权重为负值的环路?如果要写代码,请用go语言。chatgpt:...

deepseek VS chatgpt (405)-- 算法导论25.3 5题

五、假定在一个权重函数为w的有向图上运行Johnson算法。证明:如果图包含一条权重为0的环路,那么对于环路上的每条边,。如果要写代码,请用go语言。...

推荐引擎算法学习导论(算法引擎是什么意思)

之前已经介绍过推荐算法基础知识,在此再介绍一点基础的知识,方便大家温故学习。作者:July。出处:结构之法算法之道引言昨日看到几个关键词:语义分析,协同过滤,智能推荐,想着想着便兴奋了。于是昨天下午开...

文心一言 VS 讯飞星火 VS chatgpt (200)—— 算法导论15.2 4题

四、用go语言,对输入链长度为n的矩阵链乘法问题,描述其子问题图:它包含多少个顶点?包含多少条边?这些边分别连接哪些顶点?文心一言:...

操作系统概论:第三章 进程调度与死锁

进程调度的功能是按照某种策略或算法从就绪态进程中为当前空闲的cPU选择在其上运行的新进程。选择调度方式和算法的若干准则:1)周转时间短周转时间是指从作业被提交给系统开始,到作业完成为止系统的平均...

C#经典算法实践,回顾往生,更是致敬《算法导论》

概述本系列博文将会向大家介绍本人在钻研《算法导论第3版》过程中的点点滴滴,并使用C#语言实现该书中所有的经典算法,附带相应的时间复杂度分析。知识储备C#算法设计之知识储备...

deepseek VS chatgpt (401)-- 算法导论25.3 1题

一、请在图25-2上使用Johnson算法来找到所有结点对之间的最短路径。给出算法计算出的和值。如果要写代码,请用go语言。chatgpt:...

《算法导论》随笔3-1 Kruskal算法 第23章

这个是图论的倒数第二章。我会着重讲解最小生成树和拓扑排序两个算法。如果哪些地方我写错的,或者没写清楚的,可以评论区吐槽~先看一道洛谷上面的题目。...

算法圣经——《算法导论》中文版PDF免费分享

作为最著名的算法书之一,这本书深入浅出,全面论述了算法的内容,从一定深度上涵盖了算法的诸多方面,同时其讲授和分析方法又兼顾了各个层次读者的接受能力。各章内容自成体系,可作为独立单元学习。全书选材经典、...

洛阳规划馆版地图(分解版)(洛阳规划馆什么时候闭馆)

规划馆版地图组图规划馆版地图组图规划馆版地图组图规划馆版地图组图规划馆版地图组图规划馆版地图组图规划馆版地图组图规划馆版地图组图...

《意义地图》(意象地图五大要素)

意义是人的终极命题。人对于世界的意义,也就是世界对于人的意义。本书从人性的层面,从人际的视角,探讨了人如何活出意义的心理和精神路径,描绘了属于人的意义地图。我们都乘坐在属于自己的意义之舟上,时刻在掂量...