前言：
首先我们需要知道什么是拓扑排序？
在正式讲解拓扑排序这个算法之前，我们需要了解一些前置知识（和离散数学相关）
1、有向无环图：
指的是一个无回路的有向图。
入度：有向图中某点作为图中边的终点的次数之和
出度：有向图中某点作为图中边的起点的次数之和
2、AOV网：顶点活动图
在有向无环图中，用顶点来表示一个活动，用边来表示活动的先后顺序的图结构。
举个例子：
在下面的这张图中，1这个点的入度就是0，2这个点的入度就是2，因为有两条有向线段指向2这个点。
3、拓扑排序：
简而言之就是找到事情的先后顺，拓扑排序的结果可能不是唯一的。
如何排序？
- 找出图中入度为0的点，然后输出
- 删除与该点连接的边
- 重复1、2操作，直到图中没有点或者没有入度为0点为止。（有可能有环）
重要应用：判断有向图中是否有环
4、如何用代码实现拓扑排序呢？（重点）
首先，我们需要根据题意去建图！！！（利用哈希表等容器，会结合题目详细解析）。
接着，建好图后，借助队列，来一次BFS即可。
1、初始化：把所有入度为0的点加入到队列中
2、当队列不为空时：
- 拿出队头元素，加入到最终结果中；
- 删除与该元素相连的边
- 判断：与删除边相连的点，是否入度变成0，如果入度为0，加入到队列中
经典例题1：207. 课程表 - 力扣（LeetCode）
题目描述：
题目解析：
我们可以根据题意，将课程之间的联系抽象成图：
而题目所说的判断能否完成所有的课程学习，问的就是这个图有无环！！！
知道本题利用拓扑排序解决，那第一步就是如何建图呢？
灵活使用语言提供的容器。
邻接表：
我们可以利用哈希表来实现图中点与点之间的关系。
同时我们也需要另一个容器存储每个点的入度。
原码：
class Solution {
public:
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
unordered_map<int,vector<int>> hash; //邻接表存图
vector<int> in(numCourses); //标记每个点的入度
//开始建图
for(auto& e : prerequisites)
{
int a = e[0];
int b = e[1];
hash[b].push_back(a);
in[a]++;
}
queue<int> q;
//将度为0的边存到队列中
for(int i = 0; i < numCourses; i++)//
{
cout << i << endl;
if(in[i] == 0) q.push(i);
}
//进行拓扑排序bfs
while(q.size())
{
int t = q.front();
q.pop();
//将这个点删除，并且删除跟他相连的边
for(int i : hash[t])
{
in[i]--;
if(in[i] == 0) q.push(i);
}
}
//判断是否有环
for(auto i : in)
{
if(i > 0) return false;
}
return true;
}
};例题二：LCR 114. 火星词典 - 力扣（LeetCode）
题目描述：
题目解析：
本题也是拓扑排序的经典例题。
1、如何搜集信息？
两层for循环
2、拓扑排序：
1、建图
hash<char, hash<char>> edges;
注意第一个hash表示map类型，第二个hash表示set。
这就需要我们对容器的灵活使用！
2、统计入度信息
hash<char, int> in; 注意必须要初始化文章来源：https://www.toymoban.com/news/detail-845494.html
3、如何收集信息：双指针
4、细节问题：
abc和ab，若abc在前明显不符合要求，需要提前返回空字符串。文章来源地址https://www.toymoban.com/news/detail-845494.html
原码：
class Solution {
public:
string alienOrder(vector<string>& words) {
unordered_map<char, unordered_set<char>> edges; // 邻接表来存储图
unordered_map<char, int> in; // 统计入度
string ans;
int n = words.size();
//必须要对入度进行初始化，不然入度为0的点根本没有存进去
for(auto& i : words)
{
for(auto k : i)
in[k] = 0;
}
for(int i = 0; i < n; i++)
{
for(int j = i + 1; j < n; j++)
{
string a = words[i];
string b = words[j];
int len1 = a.size(), len2 = b.size();
int len = min(len1, len2);
int flag = 0;
for(int k = 0; k < len; k++)
{
//正常情况
if(a[k] != b[k])
{
if(!edges.count(a[k]) || !edges[a[k]].count(b[k]))
{
edges[a[k]].insert(b[k]);
in[b[k]]++;
}
flag = 1;
break;
}
}
//判断特殊情况
if(len1 > len2 && !flag)
{
return ans;
}
}
}
//开始拓扑排序
queue<char> q;
//注意map的范围for表示！！！
for(auto& [a, b]: in)
{
if(b == 0)
{
q.push(a);
}
}
while(q.size())
{
char tmp = q.front();
q.pop();
ans += tmp;
cout << ans << endl;
for(char i : edges[tmp])
{
in[i]--;
if(in[i] == 0) q.push(i);
}
}
//判断是否有环
for(auto& [a,b] : in)
{
if(b != 0) return "";
}
return ans;
}
};到了这里，关于算法沉淀——拓扑排序的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
