@[TOC]在这里插入代码片
问题描述
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。
例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
示例 1：
输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。
示例 2：
输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成?课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。
提示：
1 <= numCourses <= 1050 <= prerequisites.length <= 5000prerequisites[i].length == 20 <= ai, bi < numCoursesprerequisites[i] 中的所有课程对 互不相同
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/course-schedule
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
法I：无前驱的顶点优先算法
这个题实际上就是在判断一个有向图是否无环。
我用一个邻接矩阵来表示这幅图，用一个辅助数组来记录每个结点的入度，用一个辅助集合来记录当前已经输出的结点。
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
//建立辅助数组：记录每个点的入度
vector<int> inDegree(numCourses, 0);
//建立辅助结构：记录当前输出结点
set<int> out;
//为该图建立邻接矩阵
vector<vector<int>> graph(numCourses, vector<int>(numCourses, 0));
for (int i = 0; i < prerequisites.size(); i++) {
graph[prerequisites[i][1]][prerequisites[i][0]] = 1;
inDegree[prerequisites[i][0]]++;
}
//开始进行无前驱的顶点优先算法
while (out.size() < numCourses) {
int flag = 0;
for (int i = 0; i < numCourses; i++) {
if (inDegree[i] == 0) {//该节点入度为0
flag = 1;
out.insert(i);
inDegree[i] = -1;
//删除这个结点的所有出边
for (int j = 0; j < numCourses; j++) {
if (graph[i][j] == 1) {
graph[i][j] = 0;
inDegree[j]--;
}
}
}
}
if (flag == 0) {
break;
}
}
if (out.size() == numCourses) {
return true;
}
else {
return false;
}
}
};
看看执行结果吧：
法II：图的深度优先遍历——递归
其实与有向无环图相关的一个概念就是拓扑序列，该题只是在确定是否存在拓扑序列，在210.课程表II题目中，要求输出拓扑序列或nullptr。其实我们的处理思路可以是一致的，涉及图，我们便可以考虑图的两种遍历方式：深度优先遍历和广度优先遍历。在这里我们先来介绍一下深度优先遍历。
（1）没有优化内存，用result数组记录拓扑序列
代码有点冗余，大家凑活看看：
//图的深度优先遍历——递归
class Solution {
private:
vector<vector<int>> graph;//邻接矩阵存储图
vector<int> visited;//标记结点状态，0为未搜索，1为搜索中，2为已完成
vector<int> result;//存放拓扑序列
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
//建立邻接矩阵存储,入度数组
visited = vector<int>(numCourses, 0);
graph = vector<vector<int>>(numCourses, vector<int>(numCourses, 0));
for (int i = 0; i < prerequisites.size(); i++) {
graph[prerequisites[i][1]][prerequisites[i][0]]++;
}
//遍历所有未搜索结点
for (int i = 0; i < numCourses; i++) {
if (visited[i] == 0) {
bool res = dfs(i, numCourses);
if (res == false) {
return false;
}
}
}
return true;
}
bool dfs(int u, int numCourses) {//对结点u进行深度优先遍历
if (visited[u] == 1) {//当前结点为搜索中——有环，返回false
return false;
}
if (visited[u] == 2) {//当前节点已经搜索完成，不影响，但不用再dfs了，所以直接返回true
return true;
}
visited[u] = 1;//把当前结点(未搜索)设置为搜索中（1）
for (int i = 0; i < numCourses; i++) {//寻找当前结点的出边结点
int tmp = graph[u][i];
while (tmp > 0) {
bool res = dfs(i, numCourses);
if (res == false) {
return false;
}
tmp--;
}
}
//该节点的所有出边结点都已经遍历完成，设置该节点为“已完成”
visited[u] = 2;
result.push_back(u);
return true;
}
};
（2）省略了result的官方代码
class Solution {
private:
vector<vector<int>> edges;
vector<int> visited;
bool valid = true;
public:
void dfs(int u) {
visited[u] = 1;
for (int v: edges[u]) {
if (visited[v] == 0) {
dfs(v);
if (!valid) {
return;
}
}
else if (visited[v] == 1) {
valid = false;
return;
}
}
visited[u] = 2;
}
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
edges.resize(numCourses);
visited.resize(numCourses);
for (const auto& info: prerequisites) {
edges[info[1]].push_back(info[0]);
}
for (int i = 0; i < numCourses && valid; ++i) {
if (!visited[i]) {
dfs(i);
}
}
return valid;
}
};
执行结果的差距还是挺大的，我们来分析一下原因：
- 官方代码减少了不必要的递归：对于已经搜索完成和搜索中的结点，官方在进入递归之前就判断了，这样便减少了递归所需的时间和空间。
- 官方采用邻接链表来存储图，确实搜索时容易一点。
法III：图的广度优先遍历
广度优先遍历通过队列来实现。其实就类似于方法I，直接上官方代码吧：
class Solution {
private:
vector<vector<int>> edges;
vector<int> indeg;
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
edges.resize(numCourses);
indeg.resize(numCourses);
for (const auto& info: prerequisites) {
edges[info[1]].push_back(info[0]);
++indeg[info[0]];
}
queue<int> q;
for (int i = 0; i < numCourses; ++i) {
if (indeg[i] == 0) {
q.push(i);
}
}
int visited = 0;
while (!q.empty()) {
++visited;
int u = q.front();
q.pop();
for (int v: edges[u]) {
--indeg[v];
if (indeg[v] == 0) {
q.push(v);
}
}
}
return visited == numCourses;
}
};