拓扑排序简单的例子
拓扑排序是一种用于有向无环图的排序算法，通常用于构建排列结构或确定事件发生的顺序。本文将从多个角度分析拓扑排序，并介绍一个简单的例子，以便更好地理解算法的应用。
一、基本概念
在介绍拓扑排序之前，先了解一下有向无环图的相关概念。
有向图：由若干个结点和若干个有向边组成的图。
有向边：从一个结点指向另一个结点的边。
有向环：在一条路径上，从一个结点出发沿着有向边可以绕回到此结点本身。
有向无环图（DAG）：不包含有向环的有向图。
拓扑排序：对有向无环图中所有结点进行排序，使得所有的有向边从排在前面的结点指向排在后面的结点。
二、应用场景
拓扑排序广泛应用于数据结构、编译原理、工程项目等领域。以下是一些具体场景。
1、计算机编译器
在编译源程序的过程中，要先处理依赖关系，将源程序代码转化成目标代码。拓扑排序可用来解决源文件之间的依赖关系问题。
2、工程项目
在一个大型工程项目中，往往需要规划出各个任务的执行顺序，以便在时间、物力、人力等方面安排合理，使工程项目能够顺利完成。
3、课程安排
在教育领域，拓扑排序可用于制定课程表。比如，编程类课程，要求学生掌握一些基础知识后再学习高级内容，此时拓扑排序就可以派上用场。
三、简单例子
考虑以下有向无环图，其中表示任务，并且每个任务之间存在着依赖关系。
进行拓扑排序的过程如下：
1、选择没有入边即入度为零的点，即A。
2、将A从图中删除，并把A相邻的结点的入度减一，得到以下图。
3、重复执行上述步骤，得到拓扑排序结果：A,B,C,D,E,F。
四、算法实现
实现拓扑排序的算法有两种：Kahn算法和DFS算法。这里以Kahn算法为例。
1、构建入度表。首先，用一个数组inDegree来存储每个结点的入度值，并初始化所有值为0，然后遍历所有的边，将终点结点的入度值+1，如下：
```
edges = {{"A","B"},{"A","C"},{"B","D"},{"C","D"},{"D","E"},{"E","F"}};
unordered_map
for(auto edge: edges) {
inDegree[edge[1]]++;
}
```
2、找出入度为0的结点。创建一个队列q，将所有入度为0的结点都放到队列中。
```
queue
for(auto entry: inDegree) {
if(entry.second == 0) {
q.push(entry.first);
}
}
```
3、执行拓扑排序。不断从队列中取出入度为0的结点，并将其相邻结点的入度值-1，如果某个结点的入度值减少为0，则将其加入队列。
```
vector
while(!q.empty()) {
string cur = q.front();
q.pop();
res.push_back(cur);
for(auto edge: edges) {
if(cur == edge[0]) {
inDegree[edge[1]]--;
if(inDegree[edge[1]] == 0) {
q.push(edge[1]);
}
}
}
}
```
