这是 2020 年 8 月 4 日的每日一题。拓扑排序的典型例题。在之前矩阵最长递增路径的题中最后就有预感,现在它来了。

题目

你这个学期必须选修 numCourse 门课程,记为 0 到 numCourse-1

在选修某些课程之前需要一些先修课程。 例如,想要学习课程 0 ,你需要先完成课程 1 ,我们用一个匹配来表示他们:[0,1]

给定课程总量以及它们的先决条件,请你判断是否可能完成所有课程的学习?

示例 1

输入: 2, [[1,0]] 
输出: true
解释: 总共有 2 门课程。学习课程 1 之前,你需要完成课程 0。所以这是可能的。

示例 2

输入: 2, [[1,0],[0,1]]
输出: false
解释: 总共有 2 门课程。学习课程 1 之前,你需要先完成​课程 0;并且学习课程 0 之前,你还应先完成课程 1。这是不可能的。

思路

还是传统艺能,转换为有向图。这里点集是所有课程。边集就是题目给的先修条件。箭头的指向指修课的顺序。即 AB 的边表示 AB 的先修条件。

如下图:
首先我们对所有课程编号。然后将先修条件连线。

MDJ4GXGIS`PFYS7PYMC5BYB.png

拓扑排序

拓扑排序 是一个道路。对于一个有向图,我们吧满足以下条件的道路称为这个图的一个 拓扑排序

  1. 经过所有的点。
  2. 对于任意一条边 <a,b>,在道路中都满足 道路中 ab 之前。

我们可以用实例来理解抽象的概念。 本题的修课模型就可以帮助我们理解 拓扑排序。假设每个点都是一门课,且边表示着课程的先修条件,即边 <a, b> 表示要先修完 a 才能修 b

拓扑排序 就对应着一条符合条件的修完所有课程的排列顺序。

显而易见,拓扑排序 存在的一个 充分必要条件 就是有向图中没有回路。

而在这一题中,我们只需返回是否可以修完,所以还是比较简单的。

深搜

因为 深搜 使用的是 递归 ,所以 深搜 一般还是比较好理解的。对于拓扑排序的 深搜,因为途中可能存在回路(有没有回路会影响这过程和结果)。所以我们要考虑标记,也可以说染色。

虽然题目只要求返回是否可以,但这里我们直接求一个路径。求到了就可以求不到就不可以。

我们先规定点的三种状态:未搜索 搜索中已搜索

然后我们每次都从 未搜索 状态的点中选取一个来进行深搜。并对深搜过程中做出如下规定:

  • 遇到 未搜索 的,继续深搜。
  • 遇到 搜索中 的,意味着有环,直接停止整个过程。
  • 遇到 已搜索 的,中止当次深搜(只是中止当次,回到父节点后继续深搜)。
  • 当点回溯的时候,在第一次回溯的时候将该点入栈。

可以看以下动态图:

GIF 2020-8-4 星期二 20-23-36.gif

代码

  • 语言:C++

题目给我们的是边集。在图的搜索中,无论是 广搜 还是 深搜 ,在边集上的操作都是很耗时的,因为我们需要遍历所有边找到当前点的下一个点。所以我们需要先转换为 邻接表示

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> degree(numCourses);
        for(auto p : prerequisites){
            degree[p[0]].push_back(p[1]);
        }
    }
}

邻接表示 后我们可以在 o(1) 的时间内获取到一个点的下一个点。

然后我们直接给出剩下代码吧:

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<int> visit(numCourses,0);
        vector<vector<int>> degree(numCourses);
        for(auto p : prerequisites){
            degree[p[0]].push_back(p[1]);
        }

        bool result = true;
        for(int i = 0 ; i < numCourses ; i ++){
            if(!result){
                return result;
            }
            if (visit[i] == 0){
                dfs(visit,degree,i,result);
            }
        }
        return result;
    }

    void dfs(vector<int>& visit, vector<vector<int>>& prerequisites,int course, bool& result){
        if(!result){
            return;
        }
        if(visit[course] == 1){
            result = false;
            return;
        }
        if(visit[course] == 2){
            return;
        }
        visit[course] = 1;
        for(auto p : prerequisites[course]){
            dfs(visit,prerequisites,p,result);
        }
        visit[course] = 2;
    }
};

广搜

广搜拓扑排序 更加好理解。

还是先补充一下概念:

入度 的定义:有向图中一个点的入度数为以这个点为终点的边的个数。最直观的就是看这个点有几个箭头伸进去,它的入度就为几。

这样就很容易理解一点,入度0 的点或者说课程是当前可以修的,因为它没有任何先修条件。当我把这门课修完后,我们可以吧这个点和邻接边全部删掉。然后剩下的点里 入度0 的点就是我们可以修的下一门课程。

我们可以重复这个过程,直到没有 入度0 的点时,看看是不是所有的课程都修好了。如果没有就说明不存在 拓扑排序 ,如果已经修完了全部课程,则刚刚的修课顺序就是一个 拓扑排序

这里还是看看动态图

GIF 2020-8-4 星期二 20-25-43.gif

代码

  • 语言:C++

这里还是使用了邻接表示。然后使用一个 队列 去进行 广搜
因为需要一个入度表,所以 邻接表示 和入度计算同时可以在一个循环里完成。
然后使用一个变量保存当前经过的点。最后与总的点数进行比较可以得到结果。

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        int courseCount = 0;
        vector<vector<int>> degree(numCourses);
        vector<int> intoDegree(numCourses,0);
        for(auto p : prerequisites){
            intoDegree[p[1]]++;
            degree[p[0]].push_back(p[1]);
        }

        queue<int> q ;
        for(int i = 0 ; i < numCourses ; i ++){
            if (intoDegree[i] == 0){
                q.push(i);
            }
        }
        while(!q.empty()){

            int nowCount = q.front();
            q.pop();
            courseCount ++;

            for(auto n : degree[nowCount]){
                intoDegree[n] --;
                if(intoDegree[n] == 0){
                    q.push(n);
                }
            }

        }

        return courseCount == numCourses;
    }

};

总结

这两种方法的时间复杂度都是 o(m+n),其中 m 为课程数也就是点数 n 为先修课程要求数也就是边数。但是在实际效果中两者还是有区别的:

  • 深搜 在遇到环的时候就能停止,如果你只是想知道是否可以修完全部的话, 深搜 或许更加适合
  • 广搜 的话,几乎要把能修的课程都修完剩下不能修的才能判断。好处是剩下的点和边都能很清楚的看到。如果你想知道具体有哪些课程有环。那么 广搜 或许更加合适。