DAG有向无环图 拓扑排序解法
题意解释
一共有 n 门课要上,编号为 0 ~ n-1。
先决条件 [1, 0],意思是必须先上课 0,才能上课 1。
给你 n、和一个先决条件表,请你判断能否完成所有课程。
再举个生活的例子
先穿内裤再穿裤子,先穿打底再穿外套,先穿衣服再戴帽子,是约定俗成的。
内裤外穿、光着身子戴帽子等,都会有点奇怪。
我们遵循穿衣的一条条先后规则,用一串 顺序行为,把衣服一件件穿上。
我们遵循课程之间的先后规则,找到一种上课顺序,把所有课一节节上完。
用有向图描述依赖关系
示例:n = 6,先决条件表:[[3, 0], [3, 1], [4, 1], [4, 2], [5, 3], [5, 4]]
课 0, 1, 2 没有先修课,可以直接选。其余的课,都有两门先修课。
这种叫 有向无环图,把一个 有向无环图 转成 线性的排序 就叫 拓扑排序。
有向图有 入度 和 出度 的概念:
如果存在一条有向边 A --> B,则这条边给 A 增加了 1 个出度,给 B 增加了 1 个入度。
所以,顶点 0、1、2 的入度为 0。顶点 3、4、5 的入度为 2。
每次只能选你能上的课
每次只能选入度为 0 的课,因为它不依赖别的课,是当下你能上的课。
假设选了 0,课 3 的先修课少了一门,入度由 2 变 1。
接着选 1,导致课 3 的入度变 0,课 4 的入度由 2 变 1。
接着选 2,导致课 4 的入度变 0。
现在,课 3 和课 4 的入度为 0。继续选入度为 0 的课……直到选不到入度为 0 的课。
这很像 BFS
让入度为 0 的课入列,它们是能直接选的课。
然后逐个出列,出列代表着课被选,需要减小相关课的入度。
如果相关课的入度新变为 0,安排它入列、再出列……直到没有入度为 0 的课可入列。
BFS 前的准备工作
每门课的入度需要被记录,我们关心入度值的变化。
课程之间的依赖关系也要被记录,我们关心选当前课会减小哪些课的入度。
因此我们需要选择合适的数据结构,去存这些数据:
入度数组:课号 0 到 n - 1 作为索引,通过遍历先决条件表求出对应的初始入度。
邻接表:用哈希表记录依赖关系(也可以用二维矩阵,但有点大)
key:课号
value:依赖这门课的后续课(数组)
怎么判断能否修完所有课?
BFS 结束时,如果仍有课的入度不为 0,无法被选,完成不了所有课。否则,能找到一种顺序把所有课上完。
或者:用一个变量 count 记录入列的顶点个数,最后判断 count 是否等于总课程数。
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
vector<int> inDegree(numCourses, 0); // 入度数组
unordered_map<int, vector<int>> adjList; // 邻接表
for (const auto& pre : prerequisites) {
inDegree[pre[0]]++; // 求课的初始入度值
if (adjList.count(pre[1])) { // 当前课已经存在于邻接表
adjList[pre[1]].push_back(pre[0]); // 添加依赖它的后续课
} else { // 当前课不存在于邻接表
adjList[pre[1]] = {pre[0]};
}
}
// 示例:n = 6,先决条件表:[[3, 0], [3, 1], [4, 1], [4, 2], [5, 3], [5, 4]]
// 0
// 3
// 1 5
// 4
// 2
// 入度数组 邻接表
// inDegree adjList
// 0 {0, [3]}
// 0 {1, [3, 4]}
// 0 {2, [4]}
// 2 {3, [5]}
// 2 {4, [5]}
// 2
queue<int> que; // 用于存放入度为0的课
for (int i = 0; i < numCourses; i++) { // 所有入度为0的课入列
if (inDegree[i] == 0) {
que.push(i);
}
}
int count = 0;
while (!que.empty()) {
int selected = que.front(); // 当前选的课,出列
que.pop();
count++; // 选课数+1
if (adjList.count(selected)) { // 获取这门课对应的后续课
vector<int> toEnQueue = adjList[selected]; // 确实有后续课
for (int i = 0; i < toEnQueue.size(); i++) {
inDegree[toEnQueue[i]]--; // 依赖它的后续课的入度-1
if (inDegree[toEnQueue[i]] == 0) { // 如果因此减为0,入列
que.push(toEnQueue[i]);
}
}
}
}
return count == numCourses; // 选了的课等于总课数,返回 true,否则返回 false
}
};