算法优选系列（9.BFS 解决拓扑排序）
目录
拓扑排序简介：
编辑
课程表（medium）：
课程表II（medium）:
火星词典（hard）：
拓扑排序简介：
- 有向无环图（DAG图）
如上图每条边都有方向即为有向，任意几个点与边都不能形成一个环即为无环。
入度：即一个顶点有几个边指向它
出度：即一个顶点有几个边指向其他顶点
- AOV网：顶点活动图
在有向无环图中，用顶点表示一个活动，用边来表示向后顺序的图结构
- 拓扑排序
略
（在这里理解为找到做事情的先后顺序，拓扑排序的结果可能不唯一）
如何排序？
1. 找出图中入度为0的点然后输出
2. 删除与该点链接的点
3. 重复1 2操作直到图中没有点 或者 没有入度为0的点（有可能有环，因此另一个拓扑排序应用就是判断图中是否有环）
... ...
-
实现拓扑排序
借助队列，来一次BFS
1. 初始化：把所有入度为0的点加入队列
2. 当队列不为空的时候：
a. 拿出队头元素，加入最终结果
b. 删除与该元素相邻的边
c. 判断：与删除边相邻的点，是否入度变成零
如果入度为0加入队列
建图：第一题讲
课程表（medium）：
题目链接：207. 课程表 - 力扣（LeetCode）
算法：
原问题可以转换成⼀个拓扑排序问题。
用BFS 解决拓扑排序即可。
拓扑排序流程：
- 将所有入度为 0 的点加入到队列中；
- 当队列不空的时候，一直循环：
- 取出队头元素；
- 将于队头元素相连的顶点的入度 - 1；
- 然后判断是否减成 0,。如果减成 0，就加⼊到队列中。
eg：
课程表II（medium）:
题目链接：210. 课程表 II - 力扣（LeetCode）
算法：
和上题一样~
火星词典（hard）：
题目链接：LCR 114. 火星词典 - 力扣（LeetCode）
算法：
将题意搞清楚之后，这道题就变成了判断有向图时候有环，可以⽤拓扑排序解决。
如何搜集信息（如何建图）：
- 两层 for 循环枚举出所有的两个字符串的组合；
- 然后利⽤指针，根据字典序规则找出信息。
