拓扑排序应用，207.课程表

下班回来写了一道题，207.课程表。试用dfs和bfs写一下

题目的描述如下：

你这个学期必须选修 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 <= 105
• 0 <= prerequisites.length <= 5000
• prerequisites[i].length == 2
• 0 <= ai, bi < numCourses
• prerequisites[i] 中的所有课程对 互不相同

看完题简单画个图就能看出来，是判断有向无环图，也就是求拓扑排序的

下面看看dfs和bfs的代码

dfs来说，我们要对每一个点进行一次深度遍历，看它是否形成环。主要是需要一个数组，去记录着当前结点以及他指向的结点数组，，是个二维的。还需要一个判断是否被标记了的数组，如果走过了这个结点那么就标记1，如果这个结点相关的走完了，也没有环，说明这个结点是ok的，那么就在标记他是-1，说明这个结点相关的构不成环。当然这俩就算是退出条件了，当然还有如果这个结点后面没有关联的结点，比如(2,2)这种，他就是单独的。那肯定也是可以的

具体看代码

 vector<int>visit;bool dfs(int ti,vector<vector<int>>&vv) //每个结点，和他相连的结点数组{if(visit[ti]==1){return false;}if(visit[ti]==-1){return true;  }if(vv.size()==0){return true;}visit[ti]=1;//走过了 标记bool ans=true;//从ti 开始dfsfor(int i=0;i<vv[ti].size();++i){ans=dfs(vv[ti][i],vv);if(!ans){break;}}visit[ti]=-1;//走完这个结点的dfs 没环 ，也标记一下return ans;}bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {vector<vector<int>>vv(numCourses);//和每个点关联的有哪些visit=vector<int>(numCourses+1);bool ans=true;//要去接受结果for(int i=0;i<prerequisites.size();++i){//3 -> 2 0 1//2 ->1 0// 0->1//1 ->3vv[prerequisites[i][0]].emplace_back(prerequisites[i][1]);}for(int i=0;i<numCourses;++i){for(int j=0;j<vv[i].size();++j){ans=dfs(vv[i][j],vv);if(!ans){return false;}}}return true;}

写这种题我一直很钟意dfs，当然bfs也看看

bfs需要：

入度数组：课号 0 到 numCourses 作为索引，通过遍历先决条件表求出对应的初始入度
邻接表：二维数组adjacency，记录每门课程的后续课程有哪些。
辅助队列：存放入度为零的课程节点（可自由学习的课程）
入队：当某个课程的入度为零，则可被自由学习；
出队：已经学习了的课程数加一，其所有后续课程的入度减一；

因为队列是先入先出，所以出队的顺序即是学习课程的拓扑排序。如果出队的次数count等于课程总数，则证明可以完成所有课程的学习。

bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {int n = prerequisites.size();// 没有依赖关系，必然能完成所有课程的学习if (n == 0) return true;vector<int> indegree(numCourses);           // 每个节点的入度vector<vector<int> > adjacency(numCourses); // 邻接矩阵：先修课程-->(后续课程集合)queue<int> help;                            // 辅助队列，存放入度为0的节点// 统计所有节点的入度，构建邻接矩阵for (int i = 0; i < n; i++){indegree[prerequisites[i][0]]++;adjacency[prerequisites[i][1]].push_back(prerequisites[i][0]);}// 将所有入度为0的节点加入队列，入度为0的节点意味着没有先修课程的自由课程for (int i = 0; i < numCourses; i++){if (indegree[i] == 0)help.push(i);}int count = 0;                              // 已学的课程数while (!help.empty()){int visited = help.front();             // 当前学习的课程count++;help.pop();                             // 学完，出队// 将刚学完的课程的所有后续课程的入度减一for (int i = 0; i < adjacency[visited].size(); i++){indegree[adjacency[visited][i]]--;// 如果有后续课程的入度减为零了，则其变为了自由课程，加入队列if (indegree[adjacency[visited][i]] == 0)help.push(adjacency[visited][i]);}}// 如果学完的课程数=课程总数则返回true，否则返回falsereturn count == numCourses;}