宽度优先遍历(bfs)(4)——解决拓扑排序

欢迎来到博主的专栏：算法解析
博主ID:代码小豪

有向无环图

图是一个由顶点和边组成的数据结构，其中如果边会代表一个方向，或者顺序，那么就是一个又向图，所谓的有向无环图，其实就是一个不会构成循环回路的有向图，比如如果一个有向图可以a->b->c->a。那么这个图就是一个有环图。我们可以画出一个如下的有向无环图。

图1

对于一个有向无环图，我们任取图中任意顶点，以及这些顶点构成的边。其都不会构成一个循环回路。

那么一个有环的有向图又是怎么样的呢？如果我们让e出现一个边指向b。

图2

此时b->c->e->b构成循环回路。

实际上如何判断一个有向图我们可以借助树这个数据结构，我们可以假设顶点代表树的一个节点，而边代表父节点与子节点的链接关系。那么对于有向无环图，我们总是可以用树来表示整个图中的关系。

比如图1，如果我们以A为根节点，那么树如下：

但是对于有环图，我们无法用树型结构来表示有环图的顶点之间的关系。

其实如果我们用树这个结构中的祖先节点来解释就很好理解了。我们将图中的每一个顶点都视为树中的节点。所谓的有环图如果画成树，那么就是节点的子节点指向祖先节点。这很显然不符合树的结构。因此有向有环图是不能画成树的。

AOV图

AOV图是有向无环图的一个应用，全称叫做顶点活动图，即对于图中的每个顶点，都表示一个活动，边表示顶点之间的优先关系（或者说是先后顺序）。

我们可以写一个符合现实逻辑的AOV图，以完成一道青椒炒肉为例：

比如顶点切菜，如果我们要切菜，那么首要要将菜洗一洗吧，如果要洗菜，首先要有菜吧，所以要去买菜。当我们开始炒菜时，我们首先要把菜切好，然后起锅热油，当这两个活动都完成之后，我们才能开始炒菜。而对于准备厨具和买菜来说，我们无论先干什么都无所谓。

那么我们怎么知道一件事可以直接开始做，当我们完成一件事之后，下一件被解锁的·是什么？那么这里我们就可以引入两个概念：分别是入度和出度。

对于一个顶点来说，指向顶点的边的个数称为入度。从顶点出去的指向其他顶点的边的个数，称之为出度。

以下面的图为例：

如果AOV图中，一个顶点（活动）入度为0，则代表该活动已经可以执行了，当活动执行结束之后，我们将该顶点以及对应的边删除，此时该顶点指向的其他顶点的入度必然会减少，然后可以继续选择入度为0的顶点，执行对应的活动。

拓扑排序

拓扑排序可以帮助我们完成对AOV图的执行的先后顺序进行排序。比如上图中的青椒炒肉。我们可以用肉眼进行一下排序：

我们可以发现，AOV图的执行结果并非唯一的，但是我们确实可以依靠拓扑排序展现出一个完成AOV图所有活动的一种可能性。

那么拓扑排序该如何做呢?我们遍历一遍所有图中所有顶点，找出入度为0的顶点加入到队列当中。

接着将队头顶点取出，将该顶点对应的所有边删除，此时判断与顶点有链接的其他顶点的入度是否为0，若为0，则将其加入队列当中。以此类推，直到队列中不存在其他顶点为止。

实际上这一步操作与bfs无异。因此拓扑排序的核心算法就是bfs，为什么说是核心呢?因为还有其他问题没有解决。

那么我们随便拿一个AOV图来模拟一遍吧：

如何写拓扑排序呢？

虽然我们已经知道拓扑排序的方法，但是有一个问题，我们的AOV图怎么建图呢？毕竟STL中又没有图这个数据结构。（虽然有map和unordered_map，但是它们的底层是RB_tree和哈希表）。

我们可以用vector<vector<int>>或者unordered_map<int,vector<int>>来做一个邻接表。关于如何建邻接表以及如何利用邻接表做拓扑排序，博主不想干讲，那一个OJ题来辅助学习吧。

leetcode210——课程表II

题目解析

假设我们学校这学期要求在网课修完选修课程0，课程1，课程2，课程3。在平台中存在这么一个规定，课程0和课程1可以直接看，课程2要求修完课程1，课程3要求修完课程0，课程1，课程2。

那么我们可以用如下的顺序来修完这学期的所有选修课程。
0->1->2->3
1->2->0->3
1->0->2->3

算法原理

对于这种有明确的活动优先级，并且要求我们找到完成所有活动的方法的问题，我们都可以尝试用拓扑排序来完成，而且拓扑排序还有一个隐藏的作用，就是可以辨别该有向图是否有环。

对于一个有环的有向图来说，当我们进行拓扑排序时，总是有两个以上的顶点入度不为0，因此我们可以排序完成，检测一下图中顶点的入度是否全为0，如果存在有一个顶点的入度不为0，那么就说明该有向图存在有环。这意味着我们无法完成所有活动。

首先，如果要用拓扑排序，我们首先要有一个AOV图（是否有环无法确定）。那么我们改用什么数据结构来建立一个AOV图呢？

邻接表使用表示顶点之间的关系的，对于邻接表的第一个元素，表示起始顶点，后续跟着的该顶点能出度到的所有顶点，对于一个有向无环图，我们可以用邻接表来表示这些点的之间的关系：

可以发现这个邻接表有点像链表数组，我们也可以用unordered_map<int,list<int>>来做，但是如果我们将链表之间的节点链接删除，就会变成下面的结构：

这意味着我们可以用vector<vector<int>>或者unordered_map<int,vector<int>>来实现邻接表。

对于这题，我们可以用vector<vector<int>>，来作为邻接表，其中，vector[i]表示第i个课程，需要完成多少前置课程。但是这个方法并非适用大部分题。因此我们用unordered_map<int,vector<int>>来作为邻接表。

接下来就是如何表示节点的入度，我们可以创建一个入度表，入度表的底层结构是一个哈希表，即unordered_map<int,int>。其中key表示顶点，value表示该顶点的入度表。

那么最后的问题就是如何创建入度表和邻接表了。我们看看题目中的示例2，对于输入[[1,0],[2,0],[3,1],[4,2]]。其解释为：如果想要学习课程1和2，那么就要学习课程0，当课程1,2都被完成之后，才能开始学习课程3，那么我们可以画出如下的AOV图：

首先是如何创建邻接表，将邻接表命名为edges，对于输入中的[1,0]。我们令edges[0].push_back(1)。然后创建一个入度表in，由于0的优先级比1高，因此在AOV图中是从顶点0有一个边指向1，顶点1的入度++。即in[1]++。

那么最后的邻接表和入度表如下：

最后就是根据邻接表和入度表进行拓扑排序，第一步是将入度表遍历一遍，将入度为0的顶点加入到队列中，然后将队头元素取出，根据队头元素的邻接表，更新与其链接的顶点的入度。如果某个顶点在更新入度表之后入度为0，则将该顶点加入队列当中，当队列为空(bfs结束)时，若入度表中依然有入度不为0的顶点，则说明该AOV有环，对应就是任务无法排出完整的优先级。若入度为0，则将所有出队列的顶点加入到一个vector容器当中，最后将这个vector容器返回。

题解代码

class Solution {
public:vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {//建邻接表和入度表unordered_map<int,vector<int>> edges;//邻接表unordered_map<int,int> in;//入度表//初始化入度表for(int i=0;i<numCourses;i++) in[i]=0;for(auto &vec:prerequisites){edges[vec[1]].push_back(vec[0]);in[vec[0]]++;}//开始拓扑排序queue<int> q;//1.遍历入度表，将所有入度为0的顶点加入队列中for(auto [x,y]:in){if(y==0) q.push(x);}//bfsvector<int> ret;while(q.size()){int t=q.front();q.pop();ret.push_back(t);for(auto dots:edges[t]){in[dots]--;if(in[dots]==0) q.push(dots);}}for(auto [x,y]:in){if(y>0) return vector<int>();}return ret;}
};