拓扑排序与图遍历:安排课程
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;
}