【优选算法专栏】专题十八：BFS解决拓扑排序--前言

1.有向环形图（DAG图）

看下面这个例子：

上面这个例子就是一个DAG图

入度

有多少条边过来

出度

有多少条边出去

在上面例子中红色是每个点的出度，绿色是每个点的入度。

2.AOV网：顶点活动图

在有向图中，用顶点表示一个活动，用边来表示活动先后顺序的图结构。

例如青椒炒肉丝这道菜的制作就先要通过上面的顺序来进行。

通常AOV网都具有实际意义。

3.拓扑排序

在网上和市面上的书籍中拓扑排序的概念比较专业化，难以理解，我们举一个简单的例子来说一下什么是拓扑排序。

还是以青椒炒肉丝为例，根据流程图，我们可以简单的排一下序：模拟做菜

具体如下：

首先我们可以准备厨具也可以选择买菜两者谁先进行都可以。这里我们选择先准备厨具后买菜。接下来就只能洗菜，因为腌肉要先洗菜才能腌肉，然后切菜，炒菜，装盘，最后就是干饭。

通过上面例子，我们可以发现，通过找到事情的先后顺序，将这个按照先后顺序排个序其实就是一个拓扑排序。当然，我们还可以发现拓扑排序的结果是不唯一的。就比如先买菜还是先准备厨具，最后排完序是两个结果。

介绍了什么是拓扑排序，那么我们应该如何排序？其实刚在例子有实际意义可以很好理解，那要是放在一般情况，又该如何排序？

通过上面例子的排序，我们其实基本可以发现一下规律：

1. 找出图中入度为0的点，然后输出。
2. 删除与该点相连的边
3. 重复1,2操作，知道图中没有点或者没有入度为0的点为止。
   为什么终止条件还有个没有入度为0的点呢?
   这是因为图有可能有环，当图里面有环的时候，就会没有入度为0的点。所以拓扑排序还有个重要的作用：判断有向图中是否有环。

4.如何实现拓扑排序

大体思路还是借助队列，依靠bfs解决此问题。

具体如下：

1. 初始化：把所有入度为0的点加入到队列中
2. 当队列不为空时：

1. 拿出队头元素，加入到最终结果中
2. 删除与该元素相连的边
3. 判断：与删除边相连的点，是否入度为0，如果入度为0，加入到队列中

分析到这其实还有个问题，我们上面的实现的前提是图已经建立好的情况，但是我们应该先如何建图呢？我们通过一个例题和相关代码详细讲解。