【优选算法】BFS解决拓扑排序

题目描述：

思路讲解：
本道题需要我们判断是否能完成所有课程的学习，本质是判断课程依赖关系构成的有向图是否存在环。若存在环，则无法完成所有课程；否则可以。使用BFS 拓扑排序可以解决此类问题，通过逐层移除入度为 0 的节点，最终判断是否所有节点都被处理。以下是具体思路：

1. 邻接表 um 存储每个课程的后续课程列表（即学完当前课程后可以学习哪些课程），入度数组 in 记录每个课程的前置课程数量
2. 将所有入度为 0 的课程加入队列
3. BFS 处理队列：
   • 每次从队列中取出一个课程，将其后续课程的入度减 1
   • 若某个后续课程的入度变为 0，将其加入队列
4. 若最终入度数组 in 中课程的入度都为0，说明所有课程都被处理，无环；否则存在环

编写代码：

class Solution {
public:bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {unordered_map<int,vector<int>> um;vector<int> in(numCourses,0);for(auto& prs : prerequisites){int a = prs[0] , b = prs[1]; // b -> aum[b].push_back(a);in[a]++;}queue<int> qu;for(int i = 0 ; i < numCourses ; i++){if(in[i] == 0){qu.push(i);}}while(!qu.empty()){int cour = qu.front();qu.pop();for(auto x : um[cour]){in[x]--;if(in[x] == 0)  qu.push(x);}}for(int i = 0 ;  i < numCourses ; i++){if(in[i] != 0)  return false;}return true;}
};

题目描述：

思路讲解：
本道题需要我们找到课程学习顺序，思路与上一题完全一致，使用拓扑排序判断判断课程依赖关系构成的有向图是否存在环，如果无环则返回拓扑排序中取出课程的顺序，否则返回空数组。以下是具体思路：

1. 邻接表 um 存储每个课程的后续课程列表（即学完当前课程后可以学习哪些课程），入度数组 in 记录每个课程的前置课程数量，结果数组用来存储课程顺序
2. 将所有入度为 0 的课程加入队列
3. BFS 处理队列：
   • 每次从队列中取出一个课程，将其后续课程的入度减 1，并加入到结果数组中
   • 若某个后续课程的入度变为 0，将其加入队列
4. 若最终入度数组 in 中课程的入度都为0，说明所有课程都被处理，有向图无环，返回结果数组；否则存在环，返回空数组

编写代码：

class Solution {
public:vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {unordered_map<int,vector<int>> um;vector<int> in(numCourses);for(auto& prs : prerequisites){int a = prs[0] , b = prs[1];  // b -> aum[b].push_back(a);in[a]++;}queue<int> qu;for(int i = 0 ; i < numCourses ; i++){if(in[i] == 0)  qu.push(i);}vector<int> ans;while(!qu.empty()){int cour = qu.front();ans.push_back(cour);qu.pop();for(auto x : um[cour]){in[x]--;if(in[x] == 0)  qu.push(x);}}for(int i = 0 ; i < numCourses ; i++){if(in[i] != 0)  return vector<int>();}return ans;}
};

题目描述：

思路讲解：
本道题需要我们根据给定的已排序字符串列表还原出外星语言的字母顺序。这本质上是一个拓扑排序问题，通过比较相邻字符串的首个不同字符来构建字母之间的依赖关系，然后使用 BFS 生成合法的字母顺序。以下是具体思路：

1. 遍历相邻字符串对，找到首个不同字符，建立依赖关系；邻接表 ans 存储每个字符的后续字符列表；入度数组 in 记录每个字符的前置字符数量；结果字符串存储字母顺序
2. 将所有入度为 0 的字符加入队列
3. BFS 处理队列：
   • 每次从队列中取出一个字符，将其加入结果字符串，并将其后续字符的入度减 1。
   • 若某个后续字符的入度变为 0，将其加入队列
4. 若最终入度数组 in 中课程的入度都为0，说明所有字符都被处理，无环返回结果字符串；否则存在环，返回空字符串

注意：处理前缀情况（如 “abc” 在 “abcd” 前是合法的，但 “abcd” 在 “abc” 前是非法的），遇到非法情况，可以直接返回空字符串。

编写代码：

class Solution {unordered_map<char,unordered_set<char>> um;unordered_map<char,int> in;
public:string alienOrder(vector<string>& words) {for(auto& word : words){for(auto& ch : word){in[ch] = 0;}}int size = words.size();for(int i = 0 ; i < size - 1 ; i++){for(int j = i + 1 ; j < size ; j++){string& str1 = words[i];string& str2 = words[j];int len1 = str1.size();int len2 = str2.size();int len = min(len1,len2);int pos = 0;for(; pos < len ; pos++){char ch1 = str1[pos] , ch2 = str2[pos];if(ch1 != ch2){if(um[ch1].find(ch2) == um[ch1].end()){um[ch1].insert(ch2);in[ch2]++;}break;}}if(pos == len2 && len1 > len2)return "";}}queue<char> qu;for(auto& tmp : in){if(tmp.second == 0){qu.push(tmp.first);}}string ans;while(!qu.empty()){char ch = qu.front();ans += ch;qu.pop();for(auto& c : um[ch]){if(--in[c] == 0)  qu.push(c);}}for(auto& tmp : in){if(tmp.second != 0) return "";}return ans;}
};