关键路径

缘起

如上图所示, V1表示工程的开始, V9表示工程的结束. 其中的边表示相应的活动，而边上的数值表示活动要进行的天数. 对于上图节点的解读以V5为例. V5 表示要开始V5之后的活动（即v7和v8）的话, 需要完成V2和V3. 那么我们感兴趣的是, 完工最短要几天? 而且那一条图上的路径对应这个工期? 换言之, 图中哪条路径拖慢了整个工期. 再或者说, 哪条路径是这个工期的短板? 这条路径我们把它称为关键路径. 显然, 根据目测,v1->v2->v5->v8->v9 是关键路径, 整个工期是18天.

Read More

DAG判定的除拓扑序之外的另一种方法

缘起

在参考【1】和【2】中，我们分别提出了无向图是否有环的判定和有向图是否有环的判定（亦即是否是DAG图）. 并指出了有向图是否有环和无向图是否有环的判定方法是不一样的. 因为有向图在遍历过程中边的终点有被遍历到并不能断言存在环，因为这两个顶点很可能在不同的dfs树上. 即这条边仅仅是横叉边. 但是无向图就不一样,无向图的边没有方向. 不存在存在边相连而不在一个连通分支的情形. 所以才有了另辟蹊径的拓扑序判定DAG的方法. 但是本文将介绍依旧是dfs的架子来判定有向图是否含环.

Read More

拓扑排序

缘起

我一直认为学习操作系统是一件很酷的事情. 兴致勃勃的准备学习的时候, 却发现了如下的先需课程

  1. C语言
  2. 数据结构和算法
  3. 编译原理
  4. 计算机组成原理

其中, 1->2->3 是不能乱序的. 但是4和1 2 3之间没有绝对的谁先学、谁后学的顺序. 所以这就构成了一个有向图. 而且我采用了如下的学习顺序

​ 1–>2–>3–>4

但其实也可以采用如下的学习顺序

​ 1–>2–>4–>3

甚至有些巨巨

​ 4–>1–>2–>3

这个顺序就是有向图的拓扑序. 所以需求来了——求出有向图的拓扑序.

Read More