关于拓扑排序
①有向无环图（DAG图）
- 就跟它的名字一样，有方向但是没有环的图，如下图：
- 我们了解下入度和出度，二者都是针对一个点来说的，就以上图为例
- 入度：表示有多少条边指向一个点，比如上面，1的入度就是0，4的入度就是2
- 出度：表示有多少条边从这个点出去，比如1的出度就是2，2的出度就是1
②AOV图：顶点活动图
- 就是在有向无环图的基础上，用顶点来表示一个活动，用边来表示活动的先后顺序的图结构，如下图：
③拓扑排序
- 既然有排序二字，那么这个算法的目的很明确了，就是根据某个依据来排序，结合上面的AOV图，这个排序的依据就是做事的先后顺序，所以拓扑排序的目就是：在AOV网中找到做事情的先后顺序
- 以上面的做饭流程图为例，有些步骤只有前置步骤完成后才能执行，比如炒菜；有些活动直接可以执行，比如准备厨具和买菜，所以拓扑排序的结果可能不是唯一的
- 如果我买完菜了，那么买菜到洗菜的这个箭头就可以去掉，就相当于洗菜，也是一个可以直接执行的步骤了，当准备厨具和洗菜执行完后，就可以腌肉了，然后一直按相同的步骤执行，最后找到的执行结果就是“买菜-->准备厨具-->洗菜-->腌肉-->切菜-->炒菜-->装盘-->干饭”，拓扑排序的目的就是找到这种顺序
④实现拓扑排序（伪代码）
- 我们先把买菜和准备厨具这些入度为0的点拿出来，删除箭头；然后再把入度为0的拿出来删除箭头，然后重复这几步，直到没有点为止，步骤为：
- ①找到途中入度为0的点，然后输出 ②删除于该点连接的边 ③重复上面两步，直到图中没有点或者没有入度为0的点为止（加上这个是防止有环结构出现死循环）
- 所以拓扑排序的一个重要应用就是判断图中是否有环，就是直接搞一次拓扑排序，如果过程中发现没有入度为0的点了，但是图中还有剩余点，可以判断图中一定有环形结构
实现拓扑排序， 只要来一次BFS即可：
- 首先初始化，就是把所有入度为0的点加入到队列中
- 然后就是当队列不为空时，一直循环：拿出队头元素，加入到最终结果中，然后删除与该元素相连的边，删完之后判断与删除相连边的点的入度是否变成0
- 如果入度为0，加入到队列中，继续循环；
还有一个步骤就是“建图”，这个我们在下面的第一道题会详细讲解
部分OJ题详解
207. 课程表
207. 课程表 - 力扣（LeetCode）
题目先给我们一个数，我们用这个数可以构建一个该大小的有序数组，表示我们总共要学习的科目，然后又给我们一个二维数组，其中二维数组里面也是一个一个的大小为2的数组假设为[1， 0]，如果我们要学习课程1，那么必须先学习课程0，然后要我们判断能否学习完所有课程，下面来分析下这道题：
- 题目考察的就是：“能否拓扑排序？”，也就是“是否有有向无环图” --> 有向图中是否有环
- 只要执行一次拓扑排序，能把所有点都给搞出来，那么就返回true；如果最后没有入度为0的点但是有向图中还有剩余的点，返回false
算法原理就是上面的，这道题我们最重要的就是要知道“如何建图”？
建图最重要的，就是灵活使用语言提供的容器：先看图的稠密程序也就是数据量，然后就是根据实际使用邻接矩阵或邻接表，这里我们只介绍下邻接表：
邻接表的概念其实很简单，重要的就是我们如何用代码实现邻接表：
- 我们没有必要真的搞一个链表出来，只要搞一个vector<vector<int>>，或者也可以搞一个哈希表unordered_map<int, int<vector>>,用数组嵌套的话比较局限，只限于数字；第二种方式就很可以用其它的类型代替int
除了建图，我们还有个小细节需要注意解决下：
- 我们需要统计每个顶点的入度是多少，这个很简单，搞一个数组即可vector<int>，下标表示对应的点，里面的值表示入度即可
class Solution
{unordered_map<int, vector<int>> edges; //邻接表图vector<int> in; //保存每个点的入度 queue<int> q;
public:bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {vector<int> in(numCourses); //保存每个点的入度 //1，根据题目信息建图for(auto& e : prerequisites){int a = e[0], b = e[1]; //b --> a 的一条边edges[b].push_back(a);in[a]++; //根据下标添加入度}//2，拓扑排序//把入度为0的点扔队列里去for(int i = 0; i < numCourses; i++)if(in[i] == 0) q.push(i); //此时in[i]是入度，i才是这个点，所以是把i扔队列里去while(q.size()){int t = q.front();q.pop();//我们要把入度为0的点的箭头去掉，其实只要修改下所指向点的入度即可for(auto e : edges[t]) {in[e]--; //减少对应的点的入度if(in[e] == 0) q.push(e);}}//3，判断是否有环//只需要判断入度数组还有没有入度不为0的点for(int i = 0; i < numCourses; i++) if(in[i] != 0) return false;return true;}
};210. 课程表 Ⅱ
210. 课程表 II - 力扣（LeetCode）
这道题其实就是上面那道题稍微变了一下，上面是要我们判断能不能学完，这道题是要我们判断能否学完的同时，要我们返回学习完的顺序即可
- 解题思路是一样的，代码只要在拓扑排序时记录下结果最后修改一下返回即可，如下代码：
class Solution
{unordered_map<int, vector<int>> edges; //邻接表图vector<int> in; //保存每个点的入度 queue<int> q;vector<int> ret;
public:vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {vector<int> in(numCourses); //保存每个点的入度//1，根据题目信息建图for(auto& e : prerequisites){int a = e[0], b = e[1]; //b --> a 的一条边edges[b].push_back(a);in[a]++; //根据下标添加入度}//2，拓扑排序//把入度为0的点扔队列里去for(int i = 0; i < numCourses; i++)if(in[i] == 0) q.push(i); //此时in[i]是入度，i才是这个点，所以是把i扔队列里去while(q.size()){int t = q.front();q.pop();ret.push_back(t);//我们要把入度为0的点的箭头去掉，其实只要修改下所指向点的入度即可for(auto e : edges[t]) {in[e]--; //减少对应的点的入度if(in[e] == 0) q.push(e);}}if(ret.size() == numCourses) return ret;else return {};}
};LCR 144. 火星词典
LCR 114. 火星词典 - 力扣（LeetCode）
这道题难的不是算法思想，算法思想很简单，难的就是题目的意思，光看题目标题就知道了这道题肯定不简单，还是个困难题，下面就分步骤讲解一下题干：
- 现有一个新的字典序，比如英语的字典序是a到z，但是这个新的字典序是b-j，也是26个字母但是顺序不同
- 题目给我们一个字符串数组，如示例1，这个数组作为一门语言的词典，并且里面的字符串已经按这门新语言的字母顺序进行了排序
- 题目要求我们根据字符串数组，还原出已知的字母顺序，并按递增排序并返回，如果有非法字母顺序返回空串，如果有多种可能的顺序，返回任意一个即可
在讲解这道题之前，我们先来复习下如何比较字典序：
- 假设以我们英语的字典序也就是abc为例，给我们一个abf，我们对两个字符串都搞一个指针，从最左边移动，当遇到第一个不相同的字母时，由于c比f小，那么不论后面的字符是什么，都可以认为abc是比abf小的
然后我们通过示例1来还原下“火星语言”的字典序是咋样的：
下面来讲下算法原理：
- 我们最开始可以 通过两层循环遍历字符串数组并用双指针两两比较，就能找出所有的所需要的零碎的顺序，就和上面示例1一样
- 然后就可以尝试把这些零碎的顺序全部拼成一个有向图，以示例1为例，画出来的有向图就是：
- 最开始w是入度为0的，把w拿出来放队列里，然后后面的步骤就不赘述了，就是搞一次拓扑排序，最后的结果就是我们需要的字典序
- ①如何建图？这一道题我们不能用数组嵌套来搞因为数组嵌套只能应付数字，对于字符我们可以用哈希表来搞hash<char, char[]>，后面的数组就是前面这个字符后面连接的点
- 但是我们最前面找零碎顺序时是会有重复的，所以不能无脑地把所有顺序都搞char[]里面去，所以我们再哈希表里面再搞一个哈希表，这就是泛型编程地好处：hash<char, hash<char>>
- ②再然后就是和上一题一样搞一个数组统计入度信息，但是不推荐，因为这道题里面不是所有的字符都会出现，再搞一个数组的话会有误差；这个简单，再搞一个哈希表即可hash<char, int>
- 但是要先遍历一下字典序，每找到一个字符后把这个字符添加到哈希表里并把入度初始化为0，不然后面对图进行拓扑排序时，想加入度为0的点时无法加入，因为哈希里面啥也没有，存东西时只会对入度++，但是不初始化的话根本就没有这个值，所以无法加入
- ③最后收集信息，还是和上一题一样，用双指针来遍历两个字符串即可，识别到第一个不相等的字符串时，根据先后顺序扔哈希表里，然后更新下入度即可
细节处理：
- 如果题目给我们的是{'abc', 'ab'}，这个其实是不合法，因为根据计算机的底层逻辑，像这种情况，是哪个字符串长哪个就要在后面的，所以正确的顺序应该是{'ab', 'abc'}，也就是说题目一开始给我们的字符串数组就是错的，最后应该返回空串
- 但是我们上面的拓扑排序没办法解决这个细节，需要特殊处理一下
- 我们在信息处理时可以处理一下，就是双指针同时移动时，如果后面的指针指向空了，前面的还没有，以abc和ab为例，ptr1指向c，ptr2指向空了，但是由于ptr1在ptr2前面，所以直接返回空即可
class Solution
{unordered_map<char, unordered_set<char>> edges; //邻接表来表示图unordered_map<char, int> in; //统计入度bool check; //处理abc和ab的极端情况
public:string alienOrder(vector<string>& words) {//1，初始化入度哈希表for(auto& e : words)for(auto ch : e) in[ch] = 0;//2，建图int n = words.size();for(int i = 0; i < n; i++)for(int j = i + 1; j < n; j++){add(words[i], words[j]); //add的作用就是把这个对应关系加到 edges 里去，并检测是否出现极端情况if(check) return "";}//3，拓扑排序queue<int> q;string ret;for(auto& [a, b] : in)if(b == 0) q.push(a);while(q.size()){char t = q.front();q.pop();ret += t;for(char e : edges[t]){in[e]--;if(in[e] == 0) q.push(e);}}//4，判断是否有环for(auto& [a, b] : in)if(b != 0) return "";return ret;}void add(string& s1, string& s2){int n = min(s1.size(), s2.size());int i = 0;for(;i < n; i++){if(s1[i] != s2[i]){char a = s1[i], b = s2[i]; //找到一个a --> b 的信息if(!edges.count(a) || !edges[a].count(b)) //如果a是第一次来是可以存的，或者a已经存过，但是a --> b 的这个信息没有存，也可以存{edges[a].insert(b);in[b]++;} break;}}if(i == s2.size() && i < s1.size()) check = true;}
};
