Peter算法小课堂—拓扑排序与最小生成树

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

拓扑排序

讲拓扑排序前,我们要先了解什么是DAG树。所谓DAG树,就是指“有向无环图”。请判断下列图是否是DAG图

Peter算法小课堂—拓扑排序与最小生成树,图论,建模,算法,图论

Peter算法小课堂—拓扑排序与最小生成树,图论,建模,算法,图论

Peter算法小课堂—拓扑排序与最小生成树,图论,建模,算法,图论

第一幅图,它不是DAG图,因为它形成了一个环。第二幅图,它也不是DAG图,因为它没有方向。第三幅图才叫真正的DAG图(DAG图不一定联通)。

那什么叫DAG图的拓扑排序呢?排序大家都知道。拓扑排序指,按照一定次序(箭头方向)来遍历这幅图。

我们看道题吧。

太戈编程877题

题目描述:

你是一个电子游戏高手,正在研究一款新的游戏。该游戏共有n种关卡有待解锁,编号1到n。你发现关卡的解锁有m条依赖关系,第i条为:解锁关卡ai前必须先解锁关卡bi。请你为n个关卡设计一个可行的解锁顺序,若有多个可行解请输出字典序最小解。本题保证有解。

这道题中,我们怎样画这幅图呢?我们遵守一个原则“若u和v有一条有向边,说明u必须在v之前访问”。那具体怎么解决呢?下面我们介绍两种方法:Kahn算法和DFS实现。

Kahn算法

Peter算法小课堂—拓扑排序与最小生成树,图论,建模,算法,图论

代码:

cin>>n>>m;
for(int i=1;i<=m;i++){
	int a,b;
	cin>>a>>b;
	if(d[b][a]) continue;//d[b][a]代表b要在a之前完成。易错点:重边处理
	d[b][a]=1;
	in[a]++;//in[a]代表关卡a的入度
}
for(int k=1,i;k<=n;k++){
	for(i=1;i<=n;i++) if(!vst[i]&&in[i]==0) break;
	topo[++cnt]=i;
	vst[i]=cnt;//vst[i]代表关卡i是否已解锁
	for(int j=1;j<=n;j++)
		if(d[i][j]) d[i][j]=0,in[j]--;
}
for(int i=1;i<=n;i++) cout<<topo[i]<<" ";

时空复杂度:O(N^2)

DFS

Peter算法小课堂—拓扑排序与最小生成树,图论,建模,算法,图论

代码:

#include <bits/stdc++.h>
using namespace std;
const int N=10009;
vector<int> to[N];
int n,m,topo[N],cnt;
bool vst[N];
void dfs(int x){
	vst[x]=1;
	for(int i=0;i<to[N].size();i++){
		if(!vst[to[x][i]]) dfs(to[x][i]);
	}
	topo[n-cnt]=x;cnt++;
}
int main(){
	cin>>n>>m;
	for(int i=0;i<m;i++){
		int u,v;
		cin>>u>>v;
		to[u].push_back(v);
	}
	for(int i=1;i<=n;i++) if(!vst[i])dfs(i);
	for(int i=1;i<=n;i++) cout<<topo[i]<<" ";
	return 0;
}

我推荐使用DFS啊。练习:158、586。

后面来到我们的正(难)题:Minimum Spanning Tree 最小生成树

最小生成树

简称MST

在无向图中,任意两个顶点都有路径相通,称为连通图

连通图的生成树是包含原图n个顶和n-1条边的一棵树

最小生成树的所有边的长度综合是生成树里最小的

n个顶点的生成树有n-1条边,若再添加一条边,必定成环

大家算一下下列MST权值

Peter算法小课堂—拓扑排序与最小生成树,图论,建模,算法,图论

Peter算法小课堂—拓扑排序与最小生成树,图论,建模,算法,图论

答案:15 7。我们注意到第一幅图有6个点,也就是生成树有5条边,312564。第二幅图有4个点,生成树有3条边,1423。

下面,我们将要教大家如何解决最小生成树问题

Kruskal算法

贪心:每次找最短边,尝试加入最小生成树。

Peter算法小课堂—拓扑排序与最小生成树,图论,建模,算法,图论

所以,大家要先会并查集,不会的小彭友看Peter算法小课堂—并查集-CSDN博客

给大家一个标程啊。

#include <bits/stdc++.h>
using namespace std;
const int N=109;
const int M=5009;
struct edge{int u,v,w;};
edge e[M];
int n,m,id[N];
int root(int u){
	return id[u]==u?u:id[u]=root(id[u]);
}
bool cmp(const edge&a,const edge&b){
	return a.w<b.w;
}
void Kruskal(){
	sort(e,e+m,cmp);
	for(int u=1;u<=n;u++) id[u]=u;
	int ans=0;
	for(int k=0;k<m;k++){
		int ru=root(e[k].u);
		int rv=root(e[k].v);
		if(ru==rv) continue;
		id[ru]=rv;
		ans+=e[k].w;
	}
	cout<<ans<<endl;
}
int main(){
	cin>>n>>m;
	for(int i=0;i<m;i++)
		cin>>e[i].u>>e[i].v>>e[i].w;
	Kruskal();
	return 0;
}

那有的人就会疑惑,为什么Kruskal算法能找到MST呢?下面给出证明。

请你证明:Kruskal选的第1条边e1一定在某棵MST中。

证:假设存在1棵不包含e1的MST记作T。向T中添加e1,必定成环。环中必有边长不小于e1的边f,删除f。新的生成树T+e1-f的边长总和不超过T,不符合最小条件。

可视化网址:最小生成树 MST (Prim算法,Kruskal算法) - VisuAlgo文章来源地址https://www.toymoban.com/news/detail-810212.html

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

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

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

相关文章

  • 【C++算法模板】图论-拓扑排序,超详细注释带例题

    推荐视频链接:D01 拓扑排序 给定一张 有向无环图 ,排出所有顶点的一个序列 A A A 满足:对于图中的每条有向边 ( x , y ) (x,y) ( x , y ) , x x x 在 A A A 中都出现在 y y y 之前,则称 A A A 是该图的顶点的一个拓扑序 拓扑排序 可以判断有向图中是否有环,可以生成拓扑序列 对于下

    2024年04月15日
    浏览(39)
  • Peter算法小课堂—贪心算法

    课前思考:贪心是什么?贪心如何“贪”? 课前小视频:什么是贪心算法 - 知乎 (zhihu.com) 贪心是一种寻找最优解问题的常用方法。 贪心一般将求解过程分拆成若干个步骤,自顶向下,解决问题 题目描述: 你有一台抓娃娃机器,玩法有点特别:机器会随机给你一排N个娃娃(

    2024年02月05日
    浏览(37)
  • 【数据结构】图的应用:最小生成树;最短路径;有向无环图描述表达式;拓扑排序;逆拓扑排序;关键路径

    目录 1、最小生成树 1.1 概念  1.2 普利姆算法(Prim) 1.3 克鲁斯卡尔算法(Kruskal)  2、最短路径 2.1 迪杰斯特拉算法(Dijkstra) 2.2 弗洛伊德算法(Floyd)  2.3 BFS算法,Dijkstra算法,Floyd算法的对比 3、有向无环图描述表达式 3.1 有向无环图定义及特点 3.2 描述表达式 4、拓扑排序

    2024年02月07日
    浏览(46)
  • ⌈算法进阶⌋图论::拓扑排序(Topological Sorting)——快速理解到熟练运用

    目录  一、原理 1. 引例:207.课程表  2. 应用场景 3. 代码思路 二、代码模板 三、练习 1、210.课程表Ⅱ🟢 2、2392.给定条件下构造举证🟡 3、310.最小高度树🟡 4、 2603.收集树中金币 🔴 1. 引例:207.课程表 就如大学课程安排一样,如果要学习数据结构与算法、机器学习这类课程

    2024年02月11日
    浏览(44)
  • Peter算法小课堂—并查集

    我们先来看太戈编程467题 攀亲戚 题目描述: 最近你发现自己和古代一个皇帝长得很像:都有两个鼻子一个眼睛,你想知道这皇帝是不是你的远方亲戚,你是不是皇亲国戚。目前你能掌握的信息有m条,关于n个人:第i条信息包含两个人的编号ai,bi,表示ai和bi是亲戚。你的编号

    2024年01月18日
    浏览(44)
  • Peter算法小课堂—树的应用

    开篇先给大家讲个东西,叫vector,有老师称之为“向量”,当然与数学中的向量不一样啊,所以我要称之为“长度可变的数组” 头文件:#include vector 用法:vectorint d; 尾部增加元素:d.push_back(……); 元素个数:d.size() 数组方括号操作:d[i] 尾部删除元素:d.pop_back(……); 清空数

    2024年02月02日
    浏览(40)
  • Peter算法小课堂—自定义容器

    这个算法复杂度为O(nm),显然有更快的算法  但是,这样写有个很危险的错误,如下 运行出来是这样的,  原因很简单,因为set的功能是排序、去重,然而结构体排序要加上“.\\\",所以会报错 改后代码, 那么,回到原题,代码该怎么写呢? 当然这个代码也有高级版,但要升

    2024年02月04日
    浏览(37)
  • Peter算法小课堂—贪心与二分

    题目描述: 有n辆车大甩卖,第i辆车售价a[i]元。有m个人带着现金来申请购买,第i个到现场的人带的现金为b[i]元,只能买价格不超过其现金额的车子。你是大卖场总经理,希望将车和买家尽量多地进行一对一配对,请问最多卖出多少辆车? 贪心法模板: 比如说:每次挑最便

    2024年02月02日
    浏览(38)
  • Peter算法小课堂—正整数拆分

    大家可能会想:正整数拆分谁不会啊,2年级就会了,为啥要学啊 正整数拆分有好几种,这里我们列举两种讲。 我们看着第一幅图,头向左转90°,记住你看到的图,再来看第二幅图,你会惊奇的发现:第一幅图向左转90°就变成了第二幅图!因此,我们做出来一道题,就能推

    2024年02月07日
    浏览(40)
  • Peter算法小课堂—线性dp

    今天,你读完这篇文章,普及组的动态规划已经可以秒了。 求两个数列的最长公共子序列(Longest Common Subsequence,LCS)的长度。 数列 X 和 Y 的最长公共子序列 Z,是指 Z 既是 X 的子序列,又是 Y 的子序列,而且任意长度超过 Z 的数列 Z∗ 都不符合这个性质。 f[i][j]表示

    2024年04月23日
    浏览(33)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包