拓扑排序与图遍历：安排课程
Editor's Note
这是小风哥的数据结构与算法号，欢迎大家关注。
The following article is from 小风算法 Author 码农的荒岛求生
点击“小风算法”，选择“设为星标”
大家好，我是小风哥，这是LeetCode刷题系列第10篇。
今天的题目LeetCode第207号题目，安排课程，有numCourses个课程，并给定一个数组prerequisites，对于每一项prerequisites[i] = [ai, bi]表示课程bi是课程ai的先修课，基于给定的数组prerequisites确定是否能完成课程。
假设numCourses = 2, prerequisites = [[1,0]]那么我们能完成课程，但如果给定numCourses = 2, prerequisites = [[1,0],[0,1]] 则无法完成课程，因为第0号和第1号课程相互依赖。
实际上课程之间的依赖关系会组成一张图，那么显然，如果这个图中没有环那么可以修完课程，但如果图中有环则无法完成课程。
这个问题就转变为了判断图是否有环的问题，这个问题就很多种解法，这里讲解一种相对简单的，即，拓扑排序，怎么排呢？
假设有这样一张图：
我们首先需要找到入度为0的节点(也就是不依赖任何其它节点的节点)，也就是节点A：
然后将其从图中删除，这样我们得到：
此时节点B、C、D的入度都变为0，因此我们可以将BCD从图中删除，得到：
此时节点E的入度为0，因此可以将E从图中删除，之后重复上述操作，最终我们可以将所有节点从图中删除。
但是如果图中有环，就像这样：
此时我们无法将任何一个节点从图中删除，因为没有任何一个节点的入度为0，此时我们则可以认为无法完成课程。
怎么样，拓扑排序还是很简单的吧。
我们只需要一个队列，队列中保存入度为0的节点，然后不断的从队列中取出节点，并将该节点的下游节点的入度加一，如果下游节点的入度为0则将其放到队列中，重复这个过程直到队列为空：
...
queue<int> q;
...
while(!q.empty()) {
int now_c = q.front();
q.pop();
--numCourses;
for (auto c : next[now_c]) {
if (--degree[c] == 0) {
q.push(c);
}
}
}
为方便计算节点的入度，我们定义了数组vector<int> degree；
为方便得到节点的下游节点我们定义了map<int,vector<int>> next;
这两个结构的初始化代码为：
for (auto& v : prerequisites) {
++degree[v[0]];
next[v[1]].push_back(v[0]);
}
最终完成的代码为：
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
vector<int> degree(numCourses, 0);
map<int,vector<int>> next;
for (auto& v : prerequisites) {
++degree[v[0]];
next[v[1]].push_back(v[0]);
}
queue<int> q;
for (int i = 0; i < numCourses; i++) {
if (degree[i] == 0)
q.push(i);
}
while(!q.empty()) {
int now_c = q.front();
q.pop();
--numCourses;
for (auto c : next[now_c]) {
if (--degree[c] == 0) {
q.push(c);
}
}
}
return numCourses == 0;
}