【搜索回溯算法篇】：拓宽算法视野--BFS如何解决拓扑排序问题
✨感谢您阅读本篇文章，文章内容是个人学习笔记的整理，如果哪里有误的话还请您指正噢✨
✨ 个人主页：余辉zmh–CSDN博客
✨ 文章所属专栏：搜索回溯算法篇–CSDN博客
文章目录
- 一.广度优先搜索（BFS）解决拓扑排序
- 1.拓扑排序简介
- 2.解决拓扑排序的原理
- 二.例题
- 1.课程表
- 2.课程表||
- 3.火星词典
一.广度优先搜索（BFS）解决拓扑排序
1.拓扑排序简介
拓扑排序是对有向无环图（DAG, Directed Acyclic Graph）的顶点的一种排序，使得如果存在一条从顶点 u u u 到顶点 v v v 的有向边 ( u , v ) (u, v) (u,v)，那么在排序中 u u u 出现在 v v v 之前。它在许多实际应用场景中有重要作用，例如任务调度（每个任务有前置任务要求）、课程安排（先修课程的顺序安排）等。
2.解决拓扑排序的原理
-
入度的概念
- 对于有向图中的每个顶点，我们定义其入度为指向该顶点的边的数量。例如，在有向图中，如果顶点 v v v 有三条边指向它，那么顶点 v v v 的入度为3。
-
BFS - 基于入度的操作
- 首先，计算图中每个顶点的入度。
- 将所有入度为0的顶点放入队列中。这些顶点是可以作为拓扑排序的起始点，因为没有边指向它们，也就没有前置的依赖关系。
- 然后开始进行BFS：
- 从队列中取出一个顶点 u u u，将其加入到拓扑排序的结果序列中。
- 对于顶点 u u u 的所有邻接顶点 v v v，将它们的入度减1（因为 u u u 到 v v v 的边被“处理”了，相当于减少了 v v v 的一个入度来源）。
- 如果某个邻接顶点 v v v 的入度变为0，就将其加入队列。
- 重复上述步骤，直到队列为空。
-
正确性证明
- 由于我们首先选择入度为0的顶点加入队列，这些顶点没有前置依赖，可以首先出现在拓扑排序结果中。
- 当我们处理一个顶点并减少其邻接顶点的入度时，实际上是在逐步消除依赖关系。当一个顶点的入度变为0时，说明它之前的所有依赖都已经被处理过了，所以可以将其加入队列并放入拓扑排序结果中。
- 因为图是有向无环图，所以这个过程最终会处理完所有顶点，得到正确的拓扑排序结果。
二.例题
1.课程表
题目：
算法原理：
首先明白题意要求，给定一个二维数组，每一行中存储的是一对数字，比如示例一（1，0），表示学习课程1之前需要先学习课程0，用有向图表示就是0->1；要求判断给定的所有数字对是否能完成所有课程的学习；
本道题的重点就是如何使用拓扑排序来判断，但是在拓扑排序之前必须是有向图才可以拓扑排序，所以需要先根据给定的数组来建立有向图；建图通常借助两个哈希表或者数组来实现，一个用来表示指向关系，比如a->b；一个用来表示每个节点的入度个数；
在本道题中，因为课程是用数字来表示，正好对应下标，所以可以用数组来实现，这里我写的是用哈希表来表示指向关系，用数组来表示入度个数，具体可以看代码中的注释。
代码实现：
bool canFinish(int numCourses, vector<vector<int>>& prerequisites){
// 用哈希表来表示邻接表
// key值表示一个节点，val表示一个数组，里面存放的是key值节点指向的下一个节点
// key=0;val=[1,2,3];表示0指向1，2，3三个节点
unordered_map<int, vector<int>> edges;
//用数组来存放每个节点的入度,本道题中下标正好对应节点
vector<int> in(numCourses);
//建图
for(auto& nums : prerequisites){
//[a,b]表示b->a,在完成a之前先完成b
int a = nums[0], b = nums[1];
//b->a,存放b的下一个节点
edges[b].push_back(a);
//节点a入度+1
in[a]++;
}
//将入度为0的入队
queue<int> q;
for (int i = 0; i < in.size(); i++){
if(in[i]==0){
q.push(i);
}
}
//拓扑排序
while(!q.empty()){
//获取队头节点并出队
int t = q.front();
q.pop();
//遍历当前下标对应的所有下一个节点，将对应的节点入度-1，表示删除指向的边
for(auto num : edges[t]){
in[num]--;
//如果对应节点的入度为0，入队
if(in[num]==0){
q.push(num);
}
}
}
//遍历入度数组，如果出现某个节点的入度不为0说明存在环,不能遍历所有节点
for (auto num : in){
if(num==1){
return false;
}
}
return true;
}
2.课程表||
题目：
算法原理：
本道题和上面一道题可以说是一模一样，只不过是如果可以完成所有的课程，就输出课程顺序，所以在上一道题的基础上在bfs实现拓扑排序时，只需要将每个出队的头节点存放到数组中即可，因为出队顺序就是拓扑排序的顺序。
代码实现：
vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites){
//本道题是上一道的变形，具体过程一模一样
//用哈希表表示邻接表，数组存放每个节点的入度
unordered_map<int, vector<int>> edges;
vector<int> in(numCourses);
//建表
for(auto& e : prerequisites){
//b->a
int a = e[0], b = e[1];
edges[b].push_back(a);
in[a]++;
}
//将所有入度为0的入队
queue<int> q;
for (int i = 0; i < in.size(); i++){
if(in[i]==0){
q.push(i);
}
}
//建立一个数组用来返回最终的结果
vector<int> ret;
//拓扑排序，bfs实现
while(!q.empty()){
//获取队头节点并出队
int t=q.front();
q.pop();
ret.push_back(t);
//通过当前节点遍历所有指向的节点
for(auto num : edges[t]){
//修改指向的节点的入度
in[num]--;
//如果入度为0，入队
if(in[num]==0){
q.push(num);
}
}
}
//遍历入度数组，如果出现某个节点的入度不为0，说明存在环，返回空数组
for(auto num : in){
if(num!=0){
ret.clear();
return ret;
}
}
return ret;
}
3.火星词典
题目：
算法原理：
本道题其实也是根据拓扑排序的原理来解决，题意要求根据词典（words数组）来找到每个字母的先后顺序，然后返回正确的字母顺序；比如，示例一中的"wrt"和"wrf"因为前两个字母是一样的，而在第三个字母出现不同，但又因为"wrt"出现在"wrf"前面，所以字母"t"的顺序在字母"f"的前面，对应题意中的第一种情况；还有就是"abc"和"abcde"，因为第一个字符串的长度小于第二个字符串，但是前三个字符又正好相同，没有找到不相同的字符，如果是这种情况，输出的字母顺序那就是字母"de"的顺序在前，然后"abc"三个字母的顺序随便，因为无法判断出这三个字母的顺序；但是可能会出现这种情况第一个字符串是"abcde"而第二个字符串是"abc"，这种情况就是违反规则，直接返回空串即可。
所以实现过程还是先根据给定的信息建立有向图，然后拓扑排序，获取信息其实就是将给定的词典数组，两两字符串进行比较获取每个字母的顺序关系，根据上面的两种情况来获取信息。具体的过程注释可以看代码中写的。
代码实现：
string alienOrder(vector<string>& words){
// 建立一个边哈希表，key值表示字符，val值表示哈希表用来存放该字符指向的所有字符
// 因为查找该字符的指向字符时，可能会重复出现，所以内层哈希表用set型去重
// 例：key=t;val=[d,c,a];表示t->d&&t->c&&t->a;
unordered_map<char, unordered_set<char>> edges;
//建立一个入度哈希表，用来存放每个字符的入度
//key值表示字符，val值表示该字符对应的入度
unordered_map<char, int> in;
//先遍历整个词典，将所有出现的字符存放到入度哈希表中并将入度初始化为0，防止后面某些字符没有遍历到
for(auto s : words){
for(auto ch : s){
if(in.count(ch)==0){
in[ch] = 0;
}
}
}
//两层for循环遍历词典，建AOV图
for (int i = 0; i < words.size(); i++){
string s1 = words[i];
for (int j = i + 1; j < words.size(); j++){
string s2 = words[j];
//两个指针，一个指向第一个字符串中的起始位置，一个指向第二个字符串的起始位置
int cur1 = 0, cur2 = 0;
while(cur1<s1.size()&&cur2<s2.size()){
//如果两个指针指向对应字符串中的字符不相同，表示s1[cur1]->s2[cur2]
//s1的字符指向s2的字符，s2的字符入度+1
if(s1[cur1]!=s2[cur2]){
//这里有一个细节，如果b->a重复出现，a字符的入度就会重复+1
//所以要进行一个判断，如果b字符的哈希表中已经存在字符a，直接跳过
if(edges[s1[cur1]].count(s2[cur2])==0){
edges[s1[cur1]].insert(s2[cur2]);
in[s2[cur2]]++;
}
//找到第一对不相同的字符就结束
break;
}
else{
cur1++;
cur2++;
}
}
// 如果两个字符串没有找到相同的字符，有两种情况
// 1.s1=ab;s2=abc;不用处理
// 2.s1=abc;s2=ab;直接返回空串，因为违反规则
if(cur2==s2.size()&&cur1<s1.size()){
return "";
}
}
}
//设置一个结果字符串用来存放字符的顺序
string ret;
//设置一个队列
queue<char> q;
//遍历入度哈希表将所有入度为0的字符入队
for(auto& [ch,count] : in){
if(count==0){
q.push(ch);
}
}
//bfs实现拓扑排序
while(!q.empty()){
//获取队头字符并出队
char ch = q.front();
q.pop();
//结果字符串加上队头字符
ret += ch;
//找到该字符指向的所有字符，将指向的字符入度-1,表示删除指向的边
for(auto& nextch : edges[ch]){
in[nextch]--;
//如果指向的字符入度减为0，将该字符入队
if(in[nextch]==0){
q.push(nextch);
}
}
}
//遍历入度哈希表，如果出现某个字符的入度不为0，说明顺序错误，不能将所有字符拓扑排序
for(auto& [ch,count] : in){
if(count!=0){
//直接返回空串
return "";
}
}
return ret;
}
以上就是关于bfs解决拓扑排序的讲解，如果哪里有错的话，可以在评论区指正，也欢迎大家一起讨论学习，如果对你的学习有帮助的话，点点赞关注支持一下吧！！！
