浅谈拓扑排序和元素间依赖性
排序 元素 浅谈 拓扑
2023-09-11 14:20:14 时间
浅谈拓扑排序和元素间依赖性
本篇随笔浅谈一下依赖关系问题和拓扑排序的关系。
一、建图的概念和意义
有的时候自己曾经问过自己一个问题:图论的意义是什么?就是考一堆板子么?为什么数学家们要绞尽脑汁YY出一堆图论算法和图论问题?为什么数学竞赛也要学图论?
答案就是,图论这个东西真的和生活中的一些实际问题有关。
或者说,生活中的很多实际问题可以抽象成”图“这种模型,从而把原问题转化成图上问题来求解。这就是我们求什么最短路、最小生成树之类问题的意义。
所以我们发现,这些算法的精髓不是用这些算法解决图上问题,而是如何把实际问题抽象成这种模型。一旦这个模型构建对了,那么往上套算法就变成很简单的事情了。
建模的过程,在图论中就叫建图。
二、元素间关系和图
就拿这个依赖性关系来说。放一波百度的定义:
一个较大的工程往往被划分成许多子工程,我们把这些子工程称作活动(activity)。在整个工程中,有些子工程(活动)必须在其它有关子工程完成之后才能开始,也就是说,一个子工程的开始是以它的所有前序子工程的结束为先决条件的,但有些子工程没有先决条件,可以安排在任何时间开始。
这种问题给人的感觉比较棘手,棘手的原因是元素之间的关系非常复杂。那么我们完全就可以把这种关系抽象成一种图上问题,然后用图论知识求解。对于这种依赖性关系,我们建一张有向图,箭头指向的是后续任务。
说一句,这种表示活动间相互关系的图被称作: 顶点活动网(Activity On Vertex network),简称AOV网。
三、依赖性关系和拓扑排序
刚刚举出的元素间关系的例子其实就是一种依赖性关系。那么解决这种问题,重要的在于处理出一种合法完成工作的序列,使得其满足工作间的前后和依赖关系。
那么,把这个问题抽象到AOV网上,就是:找到一个序列,使得对于每条有向边,出点都在入点之前。
出现了!拓扑排序!
这种问题就用拓扑排序来方便地求解。
相关文章
- 编写排序程序,排序的元素在命令行中输入,完成排序后输出
- Java实现 LeetCode 34 在排序数组中查找元素的第一个和最后一个位置
- 排序及重复元素去重的说明,TreeSet,HashSet
- sql server 按拼音分类排序的功能
- TreeSet的两种排序方法
- TreeSet --实现学生按年龄大小和姓名排序
- LeetCode(82):删除排序链表中的重复元素 II
- LeetCode-169. 多数元素【计数,哈希表,排序,随机化,分治】
- 为什么说任何基于比较的算法将5个元素排序都需要7次?
- TypeScript里对数组元素的自定义属性排序的实现原理
- JavaSE进阶 | 二维数组的定义和使用、查找和排序算法
- 归并排序,我举个例子你就看懂了
- 对List集合中每个对象元素按时间顺序排序
- 排序。
- 1968. 构造元素不等于两相邻元素平均值的数组-快速排序
- 1403. 非递增顺序的最小子序列-二分排序加贪心算法
- C++有序vector之每插入一个元素后重新排序
- oracle表连接------>排序合并连接(Merge Sort Join)
- 拓扑排序
- 1122. 数组的相对排序
- 数据结构 - 希尔排序(Shell's Sort) 具体解释 及 代码(C++)
- jQuery 有条件排序
- 冒泡排序,选择排序,插入排序,折半插入排序
- 785. 快速排序(模板)