LeetCode 热题 100 | 图论（二）

目录

1  基础知识

1.1  什么是拓扑排序

1.2  如何进行拓扑排序

1.3  拓扑排序举例

2  207. 课程表

3  210. 课程表 II

---

菜鸟做题，语言是 C++

1  基础知识

1.1  什么是拓扑排序

含义：根据节点之间的依赖关系来生成一个有序的序列。

应用：

• 在项目管理中，按照任务之间的的依赖关系来安排执行顺序。
• 在编译原理中，按照编译单元的依赖关系来确定编译单元的生成顺序。
• 在程序设计中，按照模块之间的依赖关系来确定模块的加载和执行顺序。

突然想起来好像在操作系统原理里学过！

1.2  如何进行拓扑排序

排序步骤：

1. 选择入度为 0 的节点加入到排序结果中，并从图中移除该节点以及它的所有出边；
2. 重复步骤 1，每次都选择入度为 0 的节点加入到排序结果中，并更新图中剩余节点的入度；
3. 重复步骤 1 和 2，直到所有的节点都被加入到排序结果中，或者不再存在入度为 0 的节点。

名词解释：

• → 节点  属于节点的 入边
• 节点 →  属于节点的 出边

如果图中不再存在入度为 0 的节点，且并非所有的节点都被加入到排序结果中，那么说明原图中存在环。综上，拓扑排序的主要功能是帮助安排顺序，顺带帮助检测图中有没有环。

1.3  拓扑排序举例

下图描述了一个拓扑排序过程。

① 入度为 0 的节点有 B、D，我们任意选择 B，并删除它的出边：

② 入度为 0 的节点有 A、D，我们任意选择 A，并删除它的出边；更新后，入度为 0 的节点有 C、D，我们任意选择 C，并删除它的出边：

③ 入度为 0 的节点有 D，我们选择 D，并删除它的出边；更新后，入度为 0 的节点有 F，我们选择 F，并删除它的出边：

以此类推，不再赘述。通过 “任意选择” 一词可以看出，拓扑排序的结果不止一种。

2  207. 课程表

感觉解题方法和拓扑排序关系不大，更多的是从题意出发；想了很久要怎么才能把思路表述清楚，最终认为还是看代码来得快 TT

解题思路：假设有先修课程对 [0，1] 和 [0，2]

• 初始化：获取每门课程的先修课程数组，比如：0 对应 [1，2]
• 初始化：设置记录访问状态的数组，并将访问状态全部置为 0
• 循环：访问每门课程，判断它的先修课程是否已经被全部修完
• 如果它的先修课程未被全部修完，则表明无法完成所有课程的学习

访问状态：

• visited[course] = 0：该门课程还未被学习
• visited[course] = 1：该门课程正在被学习
• visited[course] = 2：该门课程已经被学习

针对 “该门课程正在被学习” 的说法，需要说明的是，这是算法题而不是现实生活！如果一门课正在被学习，不是代表学习它需要一段时间，而是代表它的先修课程不可能被修完，导致我们永远学不了它。

class Solution {
public:
    vector<int> visited;
    vectorint>> mustFinish;
    bool possible = true;
 
    void helper(int course) {
        // 指明该门课程正在被学习
        visited[course] = 1;
        // 判断其先修课程是否已被修完
        for (auto & preCourse : mustFinish[course]) {
            // 递归访问未被学习的先修课程
            if (visited[preCourse] == 0) {
                helper(preCourse);
                if (!possible) return;
                // 先修课程正在被学习（因为卡住了）
            } else if (visited[preCourse] == 1) {
                possible = false;
                return;
            }
        }
        // 指明该门课程已经被学习
        visited[course] = 2;
    }
 
    bool canFinish(int numCourses, vectorint>>& prerequisites) {
        visited.resize(numCourses);
        mustFinish.resize(numCourses);
 
        // 获取每门课程的先修课程数组
        for (auto & p : prerequisites) {
            mustFinish[p[0]].push_back(p[1]);
        }
        // 循环访问每门课程
        for (int i = 0; i < numCourses && possible; ++i) {
            helper(i);
        }
 
        return possible;
    }
};

3  210. 课程表 II

在  207. 课程表  的基础上，增加一个数据结构来存储课程顺序即可。

唯一区别在于：

for (int i = 0; i < numCourses && possible && !visited[i]; ++i)

新增条件 !visited[i]，不允许已经被访问过的课程再被访问，避免了课程重复被学习。

class Solution {
public:
    vector<int> visited;
    vectorint>> mustFinish;
    bool possible = true;
    vector<int> ans;
 
    void helper(int course) {
        visited[course] = 1;
        for (auto & preCourse : mustFinish[course]) {
            if (visited[preCourse] == 0) {
                helper(preCourse);
                if (!possible) return;
            } else if (visited[preCourse] == 1) {
                possible = false;
                return;
            }
        }
        visited[course] = 2;
        ans.push_back(course);
    }
 
    vector<int> findOrder(int numCourses, vectorint>>& prerequisites) {
        visited.resize(numCourses);
        mustFinish.resize(numCourses);
 
        for (auto & p : prerequisites) {
            mustFinish[p[0]].push_back(p[1]);
        }
 
        for (int i = 0; i < numCourses && possible && !visited[i]; ++i) {
            helper(i);
        }
 
        if (possible) return ans;
        return {};
    }
};