17.拓扑排序

Topological sort 又称 Topological order,这个名字有点迷惑性,因为拓扑排序并不是一个纯粹的排序算法,它只是针对某一类图,找到一个可以执行的线性顺序。

有向无环图

刚刚我们提到,拓扑排序只是针对特定的一类图,那么是针对哪类图的呢?

答:Directed acyclic graph (DAG),有向无环图。即:

  1. 这个图的边必须是有方向的;
  2. 图内无环。

那么什么是方向呢?

比如微信好友就是有向的,你加了他好友他可能把你删了你却不知道。。。那这个朋友关系就是单向的。。

什么是环?环是和方向有关的,从一个点出发能回到自己,这是环。

所以下图左边不是环,右边是。

那么如果一个图里有环,比如右图,想执行1就要先执行3,想执行3就要先执行2,想执行2就要先执行1,这成了个死循环,无法找到正确的打开方式,所以找不到它的一个拓扑序。

总结:

  • 如果这个图不是 DAG,那么它是没有拓扑序的;
  • 如果是 DAG,那么它至少有一个拓扑序;
  • 反之,如果它存在一个拓扑序,那么这个图必定是 DGA.

所以这是一个充分必要条件

拓扑排序

那么这么一个图的「拓扑序」是什么意思呢?

9 门课程,有些课程是有先修课程的要求的,就是你要先学了「最右侧这一栏要求的这个课」才能再去选「高阶」的课程。

那么这个例子中拓扑排序的意思就是:
就是求解一种可行的顺序,能够让我把所有课都学了。

那怎么做呢?

首先我们可以用来描述它,
图的两个要素是顶点和边
那么在这里:

  • 顶点:每门课
  • 边:起点的课程是终点的课程的先修课

画出来长这个样:

这种图叫 AOV (Activity On Vertex) 网络,在这种图里:

  • 顶点:表示活动;
  • 边:表示活动间的先后关系

所以一个 AOV 网应该是一个 DAG,即有向无环图,否则某些活动会无法进行。
那么所有活动可以排成一个可行线性序列,这个序列就是拓扑序列

那么这个序列的实际意义是:
按照这个顺序,在每个项目开始时,能够保证它的前驱活动都已完成,从而使整个工程顺利进行。

回到我们这个例子中:

  1. 我们一眼可以看出来要先学 C1, C2,因为这两门课没有任何要求嘛,大一的时候就学呗;
  2. 大二就可以学第二行的 C3, C5, C8 了,因为这三门课的先修课程就是 C1, C2,我们都学完了;
  3. 大三可以学第三行的 C4, C9;
  4. 最后一年选剩下的 C6, C7。

这样,我们就把所有课程学完了,也就得到了这个图的一个拓扑排序

注意,有时候拓扑序并不是唯一的,比如在这个例子中,先学 C1 再学 C2,和先 C2 后 C1 都行,都是这个图的正确的拓扑序,但这是两个顺序了。

我们总结一下,

**在这个图里的表示的是一种依赖关系**,如果要修下一门课,就要先把前一门课修了。

这和打游戏里一样一样的嘛,要拿到一个道具,就要先做 A 任务,再完成 B 任务,最终终于能到达目的地了。

算法详解

在上面的图里,大家很容易就看出来了它的拓扑序,但当工程越来越庞大时,依赖关系也会变得错综复杂,那就需要用一种系统性的方式方法来求解了。

那么我们回想一下刚刚自己找拓扑序的过程,为什么我们先看上了 C1, C2?

*因为它们没有依赖别人啊,也就是它的入度为 0.

所以我们先执行入度为 0 的那些点,那也就是要记录每个顶点的入度。因为只有当它的 入度 = 0 的时候,我们才能执行它。

那在这个算法里第一步就是得到每个顶点的入度。

Step0: 预处理得到每个点的入度

我们可以用一个 HashMap 来存放这个信息,或者用一个数组会更精巧。

Step1

拿到了这个之后,就可以执行入度为 0 的这些点了,也就是 C1, C2.

那我们把可以被执行的这些点,放入一个待执行的容器里,这样之后我们一个个的从这个容器里取顶点就好了。

至于这个容器究竟选哪种数据结构,这取决于我们需要做哪些操作,再看哪种数据结构可以为之服务。

那么首先可以把[C1, C2]放入容器中,

然后想想我们需要哪些操作吧!

我们最常做的操作无非就是把点放进来把点拿出去执行了,也就是需要一个 offerpoll 操作比较高效的数据结构,那么 queue 就够用了。

(其他的也行,放进来这个容器里的顶点的地位都是一样的,都是可以执行的,和进来的顺序无关,但何必非得给自己找麻烦呢?一个常规顺序的简简单单的 queue 就够用了。)

然后就需要把某些点拿出去执行了。

【划重点】当我们把 C1 拿出来执行,那这意味这什么?

答:意味着「以 C1 为顶点」的「指向其他点」的「边」都消失了,也就是 C1 的出度变成了 0.

如下图,也就是这两条边可以消失了。

那么此时我们就可以更新 C1 所指向的那些点也就是 C3 和 C8入度 了,

那我们这里看到很关键的一步,C8 的入度变成了 0!

也就意味着 C8 此时没有了任何依赖,可以放到我们的 queue 里等待执行了。

Step2

下一个我们再执行 C2,

那么 C2 所指向的 C3, C5入度-1

。。。以此类推直到。。。

C6C7入度00

C6 和 C7 的入度都变成 0 啦!!把它们放入 queue,继续执行到直到 queue 为空即可。

总结

好了,那我们梳理一下这个算法:

数据结构

这里我们的入度表格可以用 map 来存放,

Map: <key = Vertex, value = 入度>

但实际代码中,我们用一个 int array 来存储也就够了,graph node 可以用数组的 index 来表示,value 就用数组里的数值来表示,这样比 Map 更精巧。

然后用了一个普通的 queue,用来存放可以被执行的那些 node.

过程

我们把入度为 0 的那些顶点放入 queue 中,然后通过每次执行 queue 中的顶点,就可以让依赖这个被执行的顶点的那些点的 入度-1,如果有顶点的入度变成了 0,就可以放入 queue 了,直到 queue 为空。

细节

这里有几点实现上的细节:

当我们 check 是否有新的顶点的 入度 == 0 时,没必要过一遍整个 map 或者数组,只需要 check 刚刚改动过的就好了。

另一个是如果题目没有给这个图是 DAG 的条件的话,那么有可能是不存在可行解的,那怎么判断呢?很简单的一个方法就是比较一下最后结果中的顶点的个数和图中所有顶点的个数是否相等,或者加个计数器,如果不相等,说明就不存在有效解。所以这个算法也可以用来判断一个图是不是有向无环图

很多题目给的条件可能是给这个图的 edge list,也是表示图的一种常用的方式。那么给的这个 list 就是表示图中的。这里要注意审题哦,看清楚是谁 depends on 谁。其实图的题一般都不会直接给你这个图,而是给一个场景,需要你把它变回一个图。

时间复杂度

注意⚠️:对于图的时间复杂度分析一定是两个参数,面试的时候很多同学张口就是 O(n)…

对于有 v 个顶点和 e 条边的图来说,

第一步,预处理得到 map 或者 array,需要过一遍所有的边才行,所以是 O(e);

第二步,把 入度 == 0 的点入队出队的操作是 O(v),如果是一个 DAG,那所有的点都需要入队出队一次;

第三步,每次执行一个顶点的时候,要把它指向的那条边消除了,这个总共执行 e 次;

总:O(v + e)

空间复杂度

用了一个数组来存所有点的 indegree,之后的 queue 也是最多把所有的点放进去,所以是 O(v).

###输出所有拓扑排序

POJ 1270 Following Orders(拓扑排序:输出所有可能

------ 本文结束感谢您的阅读 ------
请我一杯咖啡吧!
微信打赏