leetcode 207. 课程表---拓扑排序篇一
课程表题解集合
引言
本题涉及到了拓扑排序相关的概念，如果对拓扑排序不了解的，建议看这篇文章AOV网与拓扑排序
拓扑排序----BFS
图解：
拓扑排序实际上应用的是贪心算法。贪心算法简而言之：每一步最优，全局就最优。
具体到拓扑排序，每一次都从图中删除没有前驱的顶点，这里并不需要真正的做删除操作，我们可以设置一个入度数组，每一轮都输出入度为 0 的结点，并移除它、修改它指向的结点的入度（−1即可），依次得到的结点序列就是拓扑排序的结点序列。如果图中还有结点没有被移除，则说明“不能完成所有课程的学习”。
拓扑排序保证了每个活动（在这题中是“课程”）的所有前驱活动都排在该活动的前面，并且可以完成所有活动。拓扑排序的结果不唯一。拓扑排序还可以用于检测一个有向图是否有环。相关的概念还有 AOV 网，这里就不展开了。
算法流程：
1、在开始排序前，扫描对应的存储空间（使用邻接表），将入度为 0 的结点放入队列。
2、只要队列非空，就从队首取出入度为 0 的结点，将这个结点输出到结果集中，并且将这个结点的所有邻接结点（它指向的结点）的入度减 1，在减 1 以后，如果这个被减 1 的结点的入度为 0 ，就继续入队。
3、当队列为空的时候，检查结果集中的顶点个数是否和课程数相等即可。
思考这里为什么要使用队列？（马上就会给出答案。）
在代码具体实现的时候，除了保存入度为 0 的队列，我们还需要两个辅助的数据结构：
1、邻接表：通过结点的索引，我们能够得到这个结点的后继结点；
2、入度数组：通过结点的索引，我们能够得到指向这个结点的结点个数。
这个两个数据结构在遍历题目给出的邻边以后就可以很方便地得到。
代码:
class Solution {
public:
//a[0]=1--->学习0，需要先学习1: 1---->0
bool canFinish(int numCourses, vector<vector<int>>& prerequisites)
{
//入度数组----记录学习每门学科前需要学习几门其他的学科
vector<int> inDegree(numCourses, 0);
//邻接表-----学习完当前课程后，能够去学习其他什么课程
vector<vector<int>> rej(numCourses);
//计算入度数组和邻接表
for (auto p : prerequisites)
{
//想要学习学科p[0],需要先去学习学科p[1]
//对应关系为---p[1]--->p[0]
inDegree[p[0]]++;
rej[p[1]].push_back(p[0]);
}
queue<int> q;
//将入度为0的点入队
for (int i = 0; i < numCourses; i++)
{
if (inDegree[i] == 0)
{
q.push(i);
}
}
//记录已经出队的课程数量
int cnt = 0;
while (!q.empty())
{
//获取队头
int front = q.front();
q.pop();
cnt++;
//检查队头的后继节点，将其后继节点入度减去一
for (auto p : rej[front])
{
//判断入度减去一后，后继节点的入度数量是否为0，如果为0，就入队
if (--inDegree[p] == 0) q.push(p);
}
}
//如果无环存在，那么所有课程都会出队一次，否则，存在环
return cnt == numCourses;
}
};
这里回答一下使用队列的问题，如果不使用队列，要想得到当前入度为 0 的结点，就得遍历一遍入度数组。使用队列即用空间换时间。
DFS
原理是通过 DFS 判断图中是否有环。
算法流程：
- 借助一个标志列表 flags，用于判断每个节点 i （课程）的状态： 未被 DFS 访问：i == 0； 已被其他节点启动的 DFS 访问：i == -1； 已被当前节点启动的 DFS 访问：i == 1。
- 对 numCourses 个节点依次执行 DFS，**
判断每个节点起步 DFS 是否存在环**，若存在环直接返回 False。DFS 流程；终止条件：当 flag[i] == -1，说明当前访问节点已被其他节点启动的 DFS 访问，无需再重复搜索，直接返回 True。当 flag[i] == 1，说明在本轮 DFS 搜索中节点 i 被第 2 次访问，即 课程安排图有环 ，直接返回 False。将当前访问节点 i 对应 flagi 置 1，即标记其被本轮 DFS 访问过； 递归访问当前节点 i 的所有邻接节点 j，当发现环直接返回 False；当前节点所有邻接节点已被遍历，并没有发现环，则将当前节点 flag 置为 -1 并返回 True。 - 若整个图 DFS 结束并未发现环，返回 True。
简而言之:
第 1 步：构建逆邻接表； 第 2 步：递归处理每一个还没有被访问的结点，具体做法很简单：对于一个结点来说，先输出指向它的所有顶点，再输出自己。 第 3 步：如果这个顶点还没有被遍历过，就递归遍历它，把所有指向它的结点都输出了，再输出自己。注意：当访问一个结点的时候，应当先递归访问它的前驱结点，直至前驱结点没有前驱结点为止。
图解:
代码:
class Solution {
public:
//a[0]=1--->学习0，需要先学习1
bool canFinish(int numCourses, vector<vector<int>>& prerequisites)
{
//逆邻接表---记录学习每一门课程前需要学习的课程
vector<vector<int>> res(numCourses);
//p[1]---->p[0]
for (int i = 0; i <prerequisites.size(); i++)
res[prerequisites[i][1]].push_back(prerequisites[i][0]);
//标记数组，标记当前课程是正在访问，还是已经访问过了
vector<int> marked(numCourses, 0);
//递归处理每一个还没有被访问的结点，具体做法很简单：对于一个结点来说，先输出指向它的所有顶点，再输出自己。
for (int i = 0; i < numCourses; i++)
{
// 注意方法的语义，如果图中存在环，表示课程任务不能完成，应该返回 false
if (dfs(i, res, marked)) return false;
}
// 在遍历的过程中，一直 dfs 都没有遇到已经重复访问的结点，就表示有向图中没有环
// 所有课程任务可以完成，应该返回 true
return true;
}
/**
* 注意这个 dfs 方法的语义
* @param i 当前访问的课程结点
* @param graph
* @param marked 如果 == 1 表示正在访问中，如果 == 2 表示已经访问完了
* @return true 表示图中存在环，false 表示访问过了，不用再访问了
*/
bool dfs(int i, vector<vector<int>>& graph, vector<int>& marked)
{
// 如果访问过了，就不用再访问了
// 从正在访问中，到正在访问中，表示遇到了环
if (marked[i]==1) return true;
//表示在访问的过程中没有遇到环，这个节点访问过了
if (marked[i] == 2) return false;
// 走到这里，是因为初始化呢，此时 marked[i] == 0
// 表示正在访问中
marked[i] = 1;
//遍历学习当前课程前需要学习的课程
for (auto gra : graph[i])
{
// 层层递归返回 true ，表示图中存在环
if (dfs(gra, graph, marked)) return true;
}
// i 的所有后继结点都访问完了，都没有存在环，则这个结点就可以被标记为已经访问结束
// 状态设置为 2
marked[i] = 2;
// false 表示图中不存在环
return false;
}
};
复杂度分析：
- 时间复杂度：O(E + V)；
- 空间复杂度：O(E + V)。
腾讯云开发者
