LeetCode#207: Course Schedule
Problem
There are a total of n courses you have to take, labeled from 0 to n - 1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
For example:
2, [[1,0]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.
2, [[1,0],[0,1]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.
Note:
- The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
- You may assume that there are no duplicate edges in the input prerequisites.
题意
现在总共有n门要上的课，编号从0到n - 1。
有些课必须先上一些前置课程才能上，比如说要上编号为0的课，必须先完成编号为1的课程才行，这样的关系被表示为一个pair：[0, 1]。
给出课程总数n和一个pair的表，判断是否有可能完成所有的课程？
分析
这个题本质上是一个判断一张图是否为有向无环图（DAG）的题目。
DAG，顾名思义，如果一个有向图中从任意点出发都不能回到该点的话，这张图就是一个有向无环图
课程就表示图中的点，而前置课程的关系则表示了图中的有向边。需要特别注意的是，完成事件A才能继续完成事件B，这样的关系我们通常表示为A->B；但是在题目中，要先完成课程1才能完成课程0，这个关系被表示为了[0, 1]，所以在代码中构造图的信息时，需要留意。
根据《算法概论》中对有向无环图的讲解，判断一个有向图是否有环，有两个算法：
-
拓扑排序
即找出该图的一个线性序列，使得需要事先完成的事件总排在之后才能完成的事件之前。如果能找到这样一个线性序列，则该图是一个有向无环图 -
DFS
遍历图中的所有点，从i点出发开始DFS，如果在DFS的不断深入过程中又回到了该点，则说明图中存在回路。
对这道题，自己没有得到很好的解法，代码也不是很优雅，所以主要以Leetcode上Solution中的C++代码为例，看看是如何实现这两种算法的。
Code
拓扑排序
/*******************************************/
/* 类拓扑排序算法的实现
/* 说明：
/* 由于题目只要求判断是否存在环，并不需要直接给出线性序列解
/* 所以代码只是用了拓扑排序的思想，而不是真正实现了拓扑排序
/* 实现思路：
/* 每次从图中去掉一个入度为0的点，去掉该点后，该点指向的点的入度-1；
/* 如果最后所有的点都被去掉了，则说明该图是dag
/* 步骤：
/* 1. 建立一个二维出表，存放了每个点指向的点
/* 2. 初始化得到每个点的入度
/* 3. for循环次数为n次，每次遍历整个出表，如果没有找到入度为0的点则return false；否
/* 则记录j，将j的入度标为-1，防止重复访问该点
/* 4. 将j点指向的点的入度全部减一
/* 5. 开始新的循环
/*******************************************/
class Solution {
public:
bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
_iniInDegree(numCourses, prerequisites);
_iniOutTable(numCourses, prerequisites);
for (int i = 0; i < numCourses; i++){
int j = 0;
for (; j < numCourses; j++){
if (inDegree[j] == 0) break;
}
if (j == numCourses) return false;
inDegree[j] = -1;
for (int k = 0; k < outTable[j].size(); k++)
inDegree[outTable[j][k]]--;
}
return true;
}
private:
vector<int> inDegree;
vector<vector<int>> outTable;
void _iniInDegree(int numCourses, vector<pair<int, int>>& prerequisites){
inDegree.resize(numCourses);
for (int i = 0; i < numCourses; i++)
inDegree[i] = 0;
for (int i = 0; i < prerequisites.size(); i++)
inDegree[prerequisites[i].first]++;
}
void _iniOutTable(int numCourses, vector<pair<int, int>>& prerequisites){
outTable.resize(numCourses);
for (int i = 0; i < prerequisites.size(); i++)
outTable[prerequisites[i].second].push_back(prerequisites[i].first);
}
};
DFS
/*******************************************/
/* DFS算法的实现
/* 说明：
/* 从一点开始进行DFS，如果在DFS深入的过程中又回到了该点，则该图存在环路；否则该图是DAG
/* 步骤：
/* 1. 同上
/* 2. 建立两个bool容器visited和onpath，大小均为numCourses，初始值均为false
/* 3. visited标记被访问过的点；onpath标记某个点当前是否正在被dfs
/* 4. for循环次数为n次，每次判断一个点：
/* 如果该点未被访问过，则对该点进行DFS（用&&来实现）
/* 如果该点DFS的结果为true，表明从这一个点出发得到了环路（取决于DFS的返回值设定，也可以设定为false），return false
/* 如果该点DFS的结果为false，则表明没有在该点探测到环路，return true
/* 5. DFS函数的结构
/* 先判断当前dfs的点是否被访问过了，如果被访问过，return false
/* 如果没有被访问过，那么将该点的visited和onpath置为true
/* 遍历该点指向的点，如果有一点正在被dfs（onpath为true），则表明存在环路，返回true；如果没有，则对该点进行dfs
/* Note：不要把多线程的概念混进来，对于DFS而言，任意时刻只有一棵DFS树在生长，只有当这棵树被完全return了之后才会进行下一轮的DFS
/*******************************************/
class Solution {
public:
bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
_iniOutTable(numCourses, prerequisites);
visited.resize(numCourses);
onpath.resize(numCourses);
for (int i = 0; i < numCourses; i++)
visited[i] = onpath[i] = false;
for (int i = 0; i < numCourses; i++){
/* 在C++中，进行与运算时，如果第一个表达式的值是false，则后面的表达式都不用判断；否则，继续判断下一个表达式 */
if (!visited[i] && _dfs(i))
return false;
}
return true;
}
private:
vector<vector<int>> outTable;
vector<bool> visited;
vector<bool> onpath;
void _iniOutTable(int numCourses, vector<pair<int, int>>& prerequisites){
outTable.resize(numCourses);
for (int i = 0; i < prerequisites.size(); i++)
outTable[prerequisites[i].second].push_back(prerequisites[i].first);
}
bool _dfs(int v){
if (visited[v]) return false;
visited[v] = onpath[v] = true;
for (int i = 0; i < outTable[v].size(); i++){
/* 在C++中，进行或运算时，如果第一个表达式的值是true，则后面的表达式都不用判断；否则，继续判断下一个表达式 */
if (onpath[outTable[v][i]] || _dfs(outTable[v][i]))
return true;
}
/* return false */
return onpath[v] = false;
}
};
