拓扑排序
思路:判定所给图是否为有向无环图。(即是否能够进行拓扑排序)
DFS、BFS实现
广度优先遍历
class Solution { public: bool canFinish(int numCourses, vector<vector<int>>& prerequisites) { if(prerequisites.empty()) return true; // 采用邻接表法 vector<vector<int>>v(numCourses,vector<int>()); // 保存各结点入度 vector<int>inDegree(numCourses,0); int cnt = 0; // BFS queue<int>q; for(auto v1 : prerequisites) { inDegree[v1[0]]++; v[v1[1]].push_back(v1[0]); } // 度为0的结点入队 for(int i=0;i<numCourses;++i) { if(inDegree[i]==0) q.push(i); } while(!q.empty()) { auto node = q.front(); q.pop(); cnt ++; // 一个结点出队后,将它指向的结点的入度-1 for(int i=0;i<v[node].size();++i) { if(--inDegree[v[node][i]]==0) q.push(v[node][i]); } } // 出队结点数是否等于给定结点数 return cnt == numCourses; } };
深度优先遍历
class Solution { public: bool canFinish(int numCourses, vector<vector<int>>& prerequisites) { if(prerequisites.empty()) return true; // 采用邻接表法 vector<vector<int>>v(numCourses,vector<int>()); for(auto v1 : prerequisites) { v[v1[1]].push_back(v1[0]); } // DFS 记忆化搜索 // flags标志位来记录结点状态:0 未访问; // 1 由本次发起dfs的结点出发访问到,说明有环; // -1 由非本次发起dfs的结点访问过 vector<int>flags(numCourses,0); for(int i=0;i<numCourses;++i) if(!dfs(v,flags,i)) return false; return true; } bool dfs(vector<vector<int>>& v,vector<int>& flags,int k) { if(flags[k]==1) return false; if(flags[k]==-1) return true; flags[k] = 1; for(int i=0;i<v[k].size();++i) { if(!dfs(v,flags,v[k][i])) return false; } flags[k] = -1; return true; } };