目录
0.简介
1.有向无环图(DAG图)
2.AOV网(顶点活动图)
3.拓扑排序
4.实现拓扑排序
2.课程表
题解
3.课程表 II
题解
0.简介
拓扑排序解决的就是 有向无环图的排列问题。
- 接下来先介绍有向无环图，然后是有向无环图的一个应用 AOV网(顶点活动图)，然后根据AOV网再来说说什么是拓扑排序，以及实现拓扑排序。
1.有向无环图(DAG图)
- 有向无环图指的是有方向，但没有环的图。
- 图就是一个顶点和边连接而成的一个数据结构，有向图就是边都是有方向的。
- 有向无环图就是图中是没有环的。
- 如不能从1->2->3，3->2->4 所以这个图就是一个有向无环图。
如 4->5->6 是可以走通的，这就不是有向无环图了。
什么是入度和出度？
- 入度和出度都是针对一个点来说的
- 入度：有多少条边指向这个顶点
- 出度：由这个顶点出去多少条边
2.AOV网(顶点活动图)
AOV网也叫做顶点活动图，它其实是一个有向无环的一个应用。
- 在有向无环图中，用顶点来表示一个活动，用边来表示执行活动的先后顺序的图结构
- 比如我想洗菜，我得先买菜，我想腌肉需要先买菜和准备厨具。。
3.拓扑排序
- 通俗来讲 就是，在AOV网中找到做事情的先后顺序。
- 可以看到在这些活动中，其中一些活动必须在某些活动执行之后才能执行，比如说炒菜，必须先切菜，腌肉。
- 所以在整个工程中这个炒菜绝对不可能先干。
那些活动可以先干呢？
- 可以看到准备厨具、买菜可以先干，原因就是并没有边执行它们俩。
- 可以先准备厨具，或者先买菜。
所以从这里就可以发现一点，拓扑排序的结果可能不是唯一的！
- 如果先买菜，买完菜之后与买菜相连的箭头就可以删掉了
- 因为买完菜就可以解锁洗菜的操作了。所以这个箭头就可以删去了。
接下来可以准备厨具或者洗菜，原因是它俩都没有其他条件来限制。可以任选一个。
- 接下来只能洗菜啦
- 同理重复上面操作，最后我们就可以得到这样的做事情先后的序列，这也是就是拓扑排序的序列。
找到 做事情的先后顺序。
做一个事情之前，存在 前置条件 ，要先做完...再做完...才能做这个
如何排序？
- 找出图中入度为 0 的点，然后输出
- 删除与该点相连的边
- 重复1、2操作，直到图中没有点或者没有入度为 0 的点为止
图中没有点理解，所有活动都找完了可以停止了此时的序列就是拓扑排序的序列。
图中没有入度为 0 的点是怎么回事？
- 其实就是在这个拓扑排序中可能面对的不是有向无环图，是有环形结构的。
- 比如下面这个图，刚开始并不知道这个有向图是不是有环的，所以我们可以先做一下拓扑排序
- 当把1、3、2拿出来之后，发现剩下的都拿不出来了。
- 原因就是4、5、6形成一个环路，是没有入度为0的边。
- 因此这个结束条件还需要加上直到图中没有入度为 0 的点为止 原因就是可能有环！
- 所以说拓扑排序有一个特别重要的应用，判断有向图中是否有环。
如何判断？
- 直接对图来一次拓扑排序，当拓扑排序过程中发现没有入度为0的点的时候
- 但是图中还有剩余点的时候，此时这个图中一定会有环形结构。
4.实现拓扑排序
借助队列，来一次 BFS 即可
- 初始化：把所有入度为 0 的点加入到队列中
- 当队列不为空的时候
-
- 拿出队头元素，加入到最终结果中
- 删除与该元素相连的边
- 判断：与删除边相连的点，是否入度变成 0 ，如果入度为 0，加入到队列中
这里还有一个问题没说，如何建图？ 如何表示一个点的入度呢？下面的题在说。
建完图再进行拓扑排序。
2.课程表
链接： 207. 课程表
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。
- 例如，先修课程对
[0, 1]表示：想要学习课程0，你需要先完成课程1。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
示例 1：
输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。示例 2：
输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。题解
- 你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 ，如 0 、1、2等等。
- 如果给的是一个一个字符串，一会建图的时候还需要先把字符串转换成一个一个数才能映射。
在选修某些课程之前需要一些先修课程。
- 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。
- 请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false。
其实这道题问题的就是有向图中是否有环。
- 我们可以把给的信息抽象称一张有向图，题目问能否完成所有课程学习意思就是能不能把这个课程排个序
- 说白了就是能否拓扑排序
- 能否拓扑排序也就是是否这个图是否是有向无环图 —> 有向图中是否有环？
- 做一次拓扑排序即可，前面已经说过如何拓扑排序，接下来重点就是如何建图？
如何建图？灵活使用语言提供的容器
可以参考 图部分的博客笔记~[数据结构#2] 图(1) | 概念 | 邻接矩阵 | 邻接表 | 模拟
看稠密（看数据量）
- 邻接矩阵（稠密图）
- 邻接表（稀疏图）
这道题我们用邻接表建图
- 相像中的邻接表最左边代表某个节点，这个节点右边一坨代表这个点所连接的点。
- 看起来就像一个个链表，头表示当前所考虑的这个节点，后面相连所有的节点是与我当前点相连的节点。
- 我们建图的目的就是为了方便找到某个点所连接的那个点。
- 不然还要遍历数组去找太麻烦了，所以把这些东西先存到一个数据结构中，这个数据结构就是图。
邻接表我们脑海中想到的应该就是这样的一条一条链表的结构。
那如何实现一个邻接表呢？
我们没有必须真的搞一个链式结构出来，这里有两种方式：
- vector<vector> edges
- unordered_map<int,vector> edges
用vector嵌套一个vector是比较局限的，只能用于节点里面的值是数字表示的。
用unordered_map是比较万能的，可以把int —> string， vector< int > —> vector< string >，等等其他任何类型。
- vector嵌套一个vector，通过下标可以找到与这个节点的值相连的其他节点。
- 仅需在对应下标的vector做push_back就可以把与当前节点相连的节点加入。
- 用unordered_map就比较万能了，完全像刚才想象出来的邻接表结构，我们这里是一个int的数后面挂了一个int数组，那不就和一个节点挂着一个节点的效果一样的吗。
- 用数组表示所连接的节点。
根据算法流程，灵活建图
刚才我们只是实现把所有的边存起来。我们还要根据算法流程多添加一些东西。
- 比如这里我们是做拓扑排序，因此我们需要 知道 每个顶点的入度是多少。
- 可以用一个vector< int > ，数组里面的值就表示这个顶点的入度是多少。
- 总结：建图先看数据量选择邻接矩阵还是邻接表来建图，然后根据算法流程，灵活的在建图的基础上多添加上一点东西。
class Solution {
public:bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {//拓扑排序 判环unordered_map<int,vector<int>> graph;vector<int> in(numCourses,0);//初始化 入度数组for(auto& p:prerequisites){//!!!可以 自动创建 不存在的键graph[p[1]].push_back(p[0]);in[p[0]]++;}//建立 邻接表
//在建图时 判断一下入度为0queue<int> q;for(int i=0;i<numCourses;i++){if(in[i]==0)q.push(i);}//！！！！！！！！记录已完成的课程数
//用于判环int count=0;while(q.size()){int a=q.front();q.pop();count++;for(auto p:graph[a]){// for(int m:p)// ... ...已经 传的是vector了if(--in[p]==0){q.push(p);}}}
//成环部分 是无法入队的return count==numCourses;}
};3.课程表 II
链接： 210. 课程表 II
现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前 必须 先选修 bi 。
- 例如，想要学习课程
0，你需要先完成课程1，我们用一个匹配来表示：[0,1]。
返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 。
示例 1：
输入：numCourses = 2, prerequisites = [[1,0]]
输出：[0,1]
解释：总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。示例 2：
输入：numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
输出：[0,2,1,3]
解释：总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。题解
这道题和上面是一模一样的，还是做一次拓扑排序，不同的是这次要把拓扑排序顺序返回来。
class Solution {
public:vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {//邻接表unordered_map<int,vector<int>> graph;vector<int> in(numCourses,0);for(auto& p:prerequisites){graph[p[1]].push_back(p[0]);in[p[0]]++;}vector<int> ret={};queue<int> q;for(int i=0;i<numCourses;i++){if(in[i]==0){q.push(i);ret.push_back(i);}}while(q.size()){int a=q.front();q.pop();for(int m : graph[a]){if(--in[m]==0){q.push(m);ret.push_back(m);}}}//判环if(ret.size() != numCourses) return {};return ret;}
};
