力扣--课程表--bfs+dfs

本文主要是介绍力扣--课程表--bfs+dfs，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

整体思路：

 这是一道拓扑序列的题目，我们将边的方向定义成从先修课指向后修课的方向，借一下官方的题解图片，我们需要判断的是形成的这个图结构是否存在环，如果存在环，那么代表不能完成所有课程的学习。

bfs思路：

首先将每个点的入度数记录到hmap中，将每个点的后续节点记录到record中（record是一个unordered_map<int,vector<int>>结构，指的是某个节点指向的后续节点），首先遍历hmap中所有入度为0的节点，说明这些课程不需要先修课，他们可以直接被修完。将这些节点去掉，并且将该节点的后续节点的hmap值-1。再次遍历hmap，去掉入度数为0的节点....用什么结构来实现这个过程呢？队列~

代码：

C++：

class Solution {
public:bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {//广度优先搜索---记录入度unordered_map<int,int> hmap;unordered_map<int,vector<int>> record; //记录该门课程的后续课程int cnt=0;//初始化hmap，recordfor(int i=0;i<numCourses;i++){hmap[i]=0;}int len=prerequisites.size();for(int i=0;i<len;i++){int a=prerequisites[i][0];int b=prerequisites[i][1];hmap[a]+=1;record[b].push_back(a);}//将deque<int> q;//初始化qunordered_map<int,int>::iterator iter=hmap.begin();for(auto iter:hmap){if(iter.second==0){q.push_back(iter.first);hmap[iter.first]=-1;}}//while(!q.empty()){int p=q.front();  //该点入度为0，可删除q.pop_front();cnt++;int len=record[p].size();for(int i=0;i<len;i++){hmap[record[p][i]]--;}for(auto iter:hmap){if(iter.second==0){q.push_back(iter.first);hmap[iter.first]=-1;}}}if(cnt==numCourses){return true;}else{return false;}}
};

注意这句代码：

unordered_map<int,int>::iterator iter=hmap.begin();

Python：

class Solution:def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:hmap=[0]*numCourseslen_pre=len(prerequisites)record=[[] for i in range(numCourses)]cnt=0for i in range(len_pre):a=prerequisites[i][0]b=prerequisites[i][1]hmap[a]+=1record[b].append(a)q=deque()for index,value in enumerate(hmap):if value==0:q.append(index)hmap[index]=-1while q:p=q[0]q.popleft()cnt+=1len_=len(record[p])for i in range(len_):hmap[record[p][i]]-=1for index,value in enumerate(hmap):if value==0:q.append(index)hmap[index]=-1if cnt==numCourses:return Trueelse:return False

Python中的deque需要 from collections import deque

注意这句代码：（替代vector<vector<int>>）

record=[[] for i in range(numCourses)] #正确
record=[[]]* numCourses  #错误

注意这句代码：（替代key为索引的字典/替代需要查找索引的list）

for index,value in enumerate(hmap):

dfs思路：

我们利用hmap来记录节点 i 的邻接节点，利用flag来记录节点的状态（flag=0代表该点未被dfs，flag=1代表该点正在被路上的节点dfs，flag=-1代表该点已被其他节点dfs）。

大致dfs的思路是这样的（以节点 i 开始），首先判断节点 i 是否被其他节点 dfs（即flag=1），如果成立，则说明暂时无环，返回false。其次判断节点 i 是否属于正在被路上节点dfs，如果成立，则代表有环，返回true。如果该点未被访问，将该点的邻接节点依次遍历，遍历中如果有环，返回true，如果无环，将 i 节点的flag值记为-1。

代码：

C++：

class Solution {
public:bool dfs(int i,unordered_map<int,vector<int>>& hmap,vector<int>& flag){//以第i个点为起点//有环返回true，无环返回falseif(flag[i]==1){return true;}if(flag[i]==-1){return false;}flag[i]=1;int len=hmap[i].size();for(int j=0;j<len;j++){if(dfs(hmap[i][j],hmap,flag)){return true;}}flag[i]=-1;return false;}bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {int len=prerequisites.size();unordered_map<int,vector<int>> hmap;for(int i=0;i<len;i++){hmap[prerequisites[i][1]].push_back(prerequisites[i][0]);}vector<int> flag(numCourses,0);for(int i=0;i<numCourses;i++){if(dfs(i,hmap,flag)){return false;}}return true;}
};

Python：

class Solution:def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:def dfs(i,hmap:List[List[int]],flag:List[int]) -> bool:if flag[i]==1:return Trueif flag[i]==-1:return Falseflag[i]=1len_hmap=len(hmap[i])for j in range(len_hmap):if dfs(hmap[i][j],hmap,flag):return Trueflag[i]=-1return Falselen_pre=len(prerequisites)hmap=[[]for _ in range(numCourses)]for j in range(len_pre):hmap[prerequisites[j][1]].append(prerequisites[j][0])flag=[0]*numCoursesfor j in range(numCourses):if(dfs(j,hmap,flag)):return Falsereturn True

这篇关于力扣--课程表--bfs+dfs的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---