【数据结构与算法10】拓扑排序


一、概念

定义

拓扑排序,其实就是对一个有向图构造拓扑序列的过程。

AOV 网

在一个表示工程的有向图中,用定点表示活动,用弧表示活动之间的有限关系,这样的有向图为顶点表示活动的网,我们称为AOV 网(Activity On Vertex Network)。

拓扑序列

设 G= (V, E) 设一个具有n 个顶点的有向图, V 中的顶点序列 v1, v2, …… vn,满足若从订单 vi 到 vj 有一条路径,则在顶点序列中定点 vi 必在顶点 vj 之前。则我们称这样的顶点序列为一个拓扑序列

二、排序算法

三、流程解析


文章作者: 李佳
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 李佳 !
评论
 上一篇
【数据结构与算法】查找算法(一) 【数据结构与算法】查找算法(一)
一、概论1.1 基本概念查找(searching)就是根据给定的某个值,在查找表中确定一个其关键字等于给定制的数据元素(或记录)。 查找表(search table)是由同一类型的数据元素(或记录)构成的组合。例如下图: 关键字(key)
2020-05-13 李佳
下一篇 
【多线程】锁分析 【多线程】锁分析
一、概念1.1 同步为了避免多个线程同时读写同一个数据而产生不可预料的后果,我们要将各个线程对同一个数据的访问同步(Synchronization)。 所谓同步,即指在一个线程访问数据未结束的时候,其他线程不得对同一个数据进行访问。如此,对
2020-05-13 李佳
  目录