BFS解决拓扑排序目录BFS解决拓扑排序拓扑排序简介有向无环图DAG图AOV网顶点活动图拓扑排序BFS实现拓扑排序试题1课程表算法原理代码编写试题2课程表II算法原理代码编写试题3火星词典算法原理代码编写拓扑排序简介有向无环图DAG图AOV网顶点活动图在有向无环图中用顶点表示一个活动用边来表示活动的先后顺序的图结构拓扑排序在AOV网中找到做事情的先后顺序拓扑排序的结果可能不是唯一的第一步取出一个入度为0的点第二步删除与该点相连的边第三步重复上述操作直到图中没有点或者没有入度为0的点为止可能有环BFS实现拓扑排序第一步初始化把所有入度为0的点加入到队列第二步当队列不为空拿出队头元素加入最终结果删除与该元素相连的边判断与删除边相连的点入度是否为0如果入度为0则加入到队列试题1课程表算法原理解法BFS能否拓扑排序是否是有向无环图通过STL灵活建图建图时要根据算法流程添加参数比如每个顶点的入度代码编写class Solution { public: bool canFinish(int n, vectorvectorint prerequisites) { // 1. 邻接表建图 unordered_mapint, vectorint edges; // 2. 标记每个点的入度 vectorint in(n); // 3. 建图 for(auto e: prerequisites) { int a e[0], b e[1]; // b → a的一条边 edges[b].push_back(a); in[a]; // 增加a的入度 } // 4. 拓扑排序 queueint q; // 把所有入度为0的点入队 for(int i 0; i n; i) { if(in[i] 0) { q.push(i); } } // BFS while(q.size()) { // 拿出对头元素 int t q.front(); q.pop(); // 删除相连的边 for(int a : edges[t]) { in[a]--; // 入度为0加入队列 if(in[a] 0) { q.push(a); } } } // 5. 判断是否有环 for(int i 0; i n; i) { if(in[i]) { return false; } } return true; } };试题2课程表II算法原理解法BFS实现拓扑排序代码编写class Solution { public: vectorint findOrder(int numCourses, vectorvectorint prerequisites) { // 邻接表 vectorvectorint edges(numCourses); // 入度 vectorint in(numCourses); // 建图 for(auto v : prerequisites) { int a v[0], b v[1]; // b → a edges[b].push_back(a); in[a]; } // 拓扑排序 queueint q; vectorint ret; for(int i 0; i numCourses; i) { if(in[i] 0) { q.push(i); } } // BFS while(q.size()) { int t q.front(); q.pop(); ret.push_back(t); for(int a : edges[t]) { in[a]--; if(in[a] 0) { q.push(a); } } } // 判断 if(ret.size() numCourses) { return ret; } else { return {}; } } };试题3火星词典算法原理解法拓扑排序两层for循环搜集信息用双指针遍历建图hashchar, hashchar避免存多个xxx→xxx edges入度hashchar, int in 统计入度信息必须要初始化收集信息双指针细节问题出现[abcab]直接返回空代码编写class Solution { unordered_mapchar, unordered_setchar edges; // 邻接表 unordered_mapchar, int in; // 入度 bool check; // 处理边界 public: string alienOrder(vectorstring words) { // 1. 初始化入度 for(auto s : words) { for(auto ch : s) { in[ch] 0; } } // 2. 建图 int n words.size(); for(int i 0; i n; i) { for(int j i 1; j n; j) { add(words[i], words[j]); if(check) { return ; } } } // 3. 拓扑排序 queuechar q; for(auto [a, b] : in) { if(b 0) { q.push(a); } } string ret; while(q.size()) { char t q.front(); q.pop(); ret t; for(char ch : edges[t]) { in[ch]--; if(in[ch] 0) { q.push(ch); } } } // 判断 for(auto [a, b] : in) { if(b ! 0) { return ; } } return ret; } void add(string s1, string s2) { int n min(s1.size(), s2.size()); int i 0; for(; i n; i) { if(s1[i] ! s2[i]) { char a s1[i], b s2[i]; // a → b if(!edges.count(a) || !edges[a].count(b)) { edges[a].insert(b); in[b]; } break; } } if(i s2.size() i s1.size()) { check true; } } };