拓扑排序简单的例子

拓扑排序是一种用于有向无环图的排序算法，通常用于构建排列结构或确定事件发生的顺序。本文将从多个角度分析拓扑排序，并介绍一个简单的例子，以便更好地理解算法的应用。

一、基本概念

在介绍拓扑排序之前，先了解一下有向无环图的相关概念。

有向图：由若干个结点和若干个有向边组成的图。

有向边：从一个结点指向另一个结点的边。

有向环：在一条路径上，从一个结点出发沿着有向边可以绕回到此结点本身。

有向无环图（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 inDegree;

for(auto edge: edges) {

inDegree[edge[1]]++;

}

```

2、找出入度为0的结点。创建一个队列q，将所有入度为0的结点都放到队列中。

```

queue q;

for(auto entry: inDegree) {

if(entry.second == 0) {

q.push(entry.first);

}

}

```

3、执行拓扑排序。不断从队列中取出入度为0的结点，并将其相邻结点的入度值-1，如果某个结点的入度值减少为0，则将其加入队列。

```

vector res;

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]);

}

}

}

}

```