拓扑排序与图遍历：安排课程

大家好，我是小风哥，这是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 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 degree；

为方便得到节点的下游节点我们定义了map> next;

这两个结构的初始化代码为：

  for (auto& v : prerequisites) {
    ++degree[v[0]];
    next[v[1]].push_back(v[0]);
  }

最终完成的代码为：

bool canFinish(int numCourses, vector>& prerequisites) {
  vector degree(numCourses, 0);
  map> next;
  
  for (auto& v : prerequisites) {
    ++degree[v[0]];
    next[v[1]].push_back(v[0]);
  }
  queue 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;
}