【LeetCode热题100】BFS解决拓扑排序
本篇记录了使用BFS解决拓扑排序的几道题，包括课程表、火星词典。
【拓扑排序】
1.有向无环图（DAG图）
每条边都是有方向的。所谓无环，就是随便找几个边，这几个边不能构成一个封边的环。如果再加一条6->4的边，那就是有环图了。
此外，我们再补充入度和出度的概念。入度和出度是针对一个点来说的，入度是有多少边指向这个点，出度是从这个点出去多少边。比如，1点的入度为0，出度为2；4点的入度为2，出度为1。
2.AOV网：顶点活动图
在有向无环图中，用顶点来表示一个活动，用边来表示活动的先后顺序的图结构，就是顶点活动图。如下图：
3.拓扑排序
拓扑排序的作用说白话就是找到做事情的先后顺序。在上图中，我们发现有些活动需要在某些活动之后才能被执行。我们发现准备厨具和买菜的入度为0，可以先执行它俩，所以拓扑排序的结果可能不是唯一的。比如先执行买菜，执行完买菜后，就可以删除这个活动，如图，
然后就可以“解锁”洗菜，依次类推。最后形成的序列就是拓扑排序的序列。
那如何排序呢？
1.找出图中入度为0的点，然后输出这个点。
2.删除与该点相连的点。
3.重复12操作，直到图中没有点或者没有入度为0的点（因为图中可能有环形结构）。
4.实现拓扑排序
借助队列，来一次BFS即可。
1）初始化：把所有入度为0的点加入到队列中
2）当队列不为空时：
1.拿出队头元素，加入到最终结果中；
2.删除与该元素相邻的边；
3.判断，与该边相连的点，是否入度变成0，如果入度为0，加入到队列中。
class Solution {
public:
bool canFinish(int n, vector<vector<int>>& prerequisites)
{
//1.准备工作
unordered_map<int, vector<int>> edges; //邻接表存图
vector<int> in(n, 0); // 标记每一个点的入度
//2.建图
for(auto& e: prerequisites) // y->x
{
int x = e[0], y = e[1];
edges[y].push_back(x);
in[x]++;
}
//3.拓扑排序
queue<int> q;
//(1)把所有入度为的点加入到队列中
for(int i = 0; i < n; i++)
{
if(in[i] == 0) q.push(i);
}
//(2)bfs
while(q.size())
{
auto front = q.front();
q.pop();
for(auto e : edges[front])
{
in[e]--;
if(in[e] == 0) q.push(e);
}
}
//4.判断是否有环
for(auto e : in)
if(e != 0) return false;
return true;
}
};题目分析：我们可以将这道题转换为拓扑排序问题，根据能否拓扑排序或是否有有向无环图来判断结果。所以要根据所给数组建图，我们先画图模拟一下建图过程，
根据稠密程度，我们采用邻接表来建图，邻接表是用来表示一个点所连接的点。
在实现邻接表时，我们需要灵活使用语言提供的容器，可以使用vector<vector<int>>/unordered_map<int,vector<int>>来构建邻接表，
除了创建邻接表外，还需要创建一个入度数组，用来记录每个节点的入度。将入度为0的节点放到队列中，然后使用这个队列来一次BFS即可。
class Solution {
unordered_map<char, unordered_set<char>> hash;
unordered_map<char, int> in;
bool iserror = false;
public:
string alienOrder(vector<string>& words)
{
//初始化in
for(auto w : words)
{
for(auto e : w)
{
in[e] = 0;
}
}
int sz = words.size();
for(int i = 0; i < sz ; i++)
{
for(int j = i+1; j < sz; j++)
{
record(words[i], words[j]);
if(iserror) return "";
}
}
//拓扑排序
queue<char> q;
string ret;
for(auto& [x,y] : in)
{
if(y == 0) q.push(x);
}
while(q.size())
{
char t = q.front();q.pop();
ret += t;
for(auto e : hash[t])
{
in[e]--;
if(in[e] == 0) q.push(e);
}
}
for(auto& [x,y] : in)
{
if(y != 0) return "";
}
return ret;
}
void record(string s1, string s2)
{
int sz = min(s1.size(), s2.size());
int i = 0;
for(; i < sz ; i++)
{
if(s1[i] != s2[i])
{
if(!hash[s1[i]].count(s2[i]))
{
hash[s1[i]].insert(s2[i]);
in[s2[i]]++;
}
break;
}
}
if(i == sz && i < s1.size())
iserror = true;
}
};题目分析：首先，我们需要搜集信息，通过两层for循环，将搜集到的字母顺序放到创建的哈希表unordered_map<char,unordered_set<char>> hash中，这表示char后面都有哪些字符。然后进行一次拓扑排序即可。需要注意的是，在搜集信息时，如果前一个字符串长于后一个字符串且共同长度的部分都相同，那表明这是一个错误的顺序，直接返回""。另外，如果hash中如果已经存在某个字符后，就不需要重新插入，可以使用if(!hash[s1[i]].count(s2[i]))判断。