从零开始学数据结构系列之第四章《拓扑排序介绍及其方法》
赞
踩
什么是拓扑排序
拓扑排序指的是将有向无环图（又称“DAG”图）中的顶点按照图中指定的先后顺序进行排序。
拓扑排序是一种有向无环图（DAG）的顶点排序方法，它将一个有向无环图中的所有顶点排成一个线性序列，使得图中任意一条有向边上的起点排在终点的前面。这样说还不够具体，我们先来看一个例子。假设某大学的课程安排如下：
| 课程编号 | 课程名称 | 先修课程 |
|---|---|---|
| 1 | 高等数学 | ------- |
| 2 | 程序设计基础 | ------- |
| 3 | 离散数学 | 1,2 |
| 4 | 数据结构 | 2,3 |
| 5 | 高级语言程序设计 | 2 |
| 6 | 编译方法 | 4,5 |
| 7 | 操作系统 | 4,9 |
| 8 | 普通物理 | 1 |
| 9 | 计算机原理 | 8 |
为了顺利修完这九门课程，我们必须安排一个合理的学习顺序。
首先根据以上表格构建一个有向图，即若 j jj 的先修课程有 i ii，则画一条 i ii 到 j jj 的有向边，于是可以得到：
一个合理的学习顺序是：1 → 8 → 9 → 2 → 3 → 5 → 4 → 7 → 6 该序列又称拓扑序列，是对上述有向图进行拓扑排序后的结果。
可以看出，拓扑序列不唯一。例如，1 → 8 → 9 → 2 → 3 → 5 → 4 → 6 → 7
此外还可以证明，DAG一定存在拓扑序列，存在拓扑序列的图也一定是DAG，因此DAG又被称为拓扑图。
拓扑排序的方法
首先我们引入度的概念：
对于有向图每个结点都有入度和出度，入度就是指向该结点的边数，出度就是该结点指向其他结点的边数。
如上面这个图：
A的入度为0，出度为2；
B的入度为1，出度为1；
C的入度为1，出度为1；
D的入度为2，出度为0；
总结一下拓扑排序就是只有从前指向后的边，没有从后指向前的边。
如果是一个有向无环图，那么一定有一个点的入度为0，如果找不到一个入度为0的点，这个图一定是带环的。
拓扑排序满足：每条边(x,y)，x在序列中都在y前面。
拓扑排序的思路：
一个有向图，如果图中有入度为 0 的点，就把这个点删掉，同时也删掉这个点所连的边。
一直进行上面出处理，如果所有点都能被删掉，则这个图可以进行拓扑排序。
我们画图来解释一下，首先我们的有向无环图是这样的：
我们发现A的入度为0，那么A就可以作为源点（不会有边在它前面），然后删除A和A上所连的边，如下图
然后我们发现B和C的入度都是0，那么同样删除B，C和B，C上所连的边，如下图：
然后D的入度为0，我们同样操作，最后图被删除干净，证明可以拓扑排序。
解题思路
1.首先记录各个点的入度
2.然后将入度为 0 的点放入队列
3.将队列里的点依次出队列，然后找出所有出队列这个点发出的边，删除边，同时边的另一侧的点的入度 -1（减一）。
4.如果所有点都进过队列，则可以拓扑排序，输出所有顶点。否则输出-1（减一），代表不可以进行拓扑排序。
☁️ 以上就是所有内容，对大家有用的话点个关注！感谢大家！
往期回顾
1.【第一章】《线性表与顺序表》
2.【第一章】《单链表》
3.【第一章】《单链表的介绍》
4.【第一章】《单链表的基本操作》
5.【第一章】《单链表循环》
6.【第一章】《双链表》
7.【第一章】《双链表循环》
8.【第二章】《栈》
9.【第二章】《队》
10.【第二章】《字符串暴力匹配》
11.【第二章】《字符串kmp匹配》
12.【第三章】《树的基础概念》
13.【第三章】《二叉树的存储结构》
14.【第三章】《二叉树链式结构及实现1》
15.【第三章】《二叉树链式结构及实现2》
16.【第三章】《二叉树链式结构及实现3》
17.【第三章】《二叉树链式结构及实现4》
18.【第三章】《二叉树链式结构及实现5》
19.【第三章】《中序线索二叉树理论部分》
20.【第三章】《中序线索二叉树代码初始化及创树》
21.【第三章】《中序线索二叉树线索化及总代码》
22【第三章】《先序线索二叉树理论及线索化》
23【第三章】《先序线索二叉树查找及总代码》
24【第三章】《后续线索二叉树线索化理论》
25【第三章】《后续线索二叉树总代码部分》
26【第三章】《二叉排序树基础了解》
27【第三章】《二叉排序树代码部分》
28【第三章】《二叉排序树代码部分》
29【第三章】《平衡二叉树基础概念》
30【第三章】《平衡二叉树的平衡因子》
31【第三章】《平衡二叉树的旋转基础详解》
32【第三章】《平衡二叉树的旋转类型图文详解》
33【第三章】《平衡二叉树的旋转类型总结及总代码》
34【第三章】《哈夫曼树简单了解》
35【第三章】《哈夫曼树的构造方法》
36【第三章】《哈夫曼编码构造及代码》
37【第四章】《图的定义》
38【第四章】《图的基本概念和术语》
39【第四章】《图的存储结构》
40【第四章】《图的遍历之深度优先遍历》
41【第四章】《广度优先遍历BFS》
42【第四章】《图的遍历总代码》
43【第四章】《最小生成树概念》
44【第四章】《最小生成树的应用举例》
45【第四章】《prim算法（普里姆算法）详解》
46【第四章】《prim算法（普里姆算法）详解2》
47【第四章】《prim算法（普里姆算法）详解3》
48【第四章】《prim算法（普里姆算法）讲解汇总》
49【第四章】《prim算法（普里姆算法）代码讲解》
50【第四章】《prim算法（普里姆算法）总代码》
51【第四章】《克鲁斯卡尔算法思路介绍》
52【第四章】《克鲁斯卡尔算法步骤思路1》
53【第四章】《克鲁斯卡尔算法步骤思路2》
54【第四章】《克鲁斯卡尔算法应用场景-公交站问题》
55【第四章】《克鲁斯卡尔算法判断回路问题》
56【第四章】《克鲁斯卡尔算法步骤回顾》
57【第四章】《克鲁斯卡尔算法代码初始化详解》
58【第四章】《克鲁斯卡尔算法总代码详解》
59【第四章】《了解最短路径》
60【第四章】《迪杰斯特拉算法了解》
61【第四章】《Dijkstra 迪杰斯特拉算法图解》
62【第四章】《Dijkstra 迪杰斯特拉算法总代码》
63【第四章】《弗洛伊德(floyd)算法简介》
64【第四章】《弗洛伊德算法详解》
65【第四章】《弗洛伊德代码详解》
66【第四章】《拓扑排序之AOV网》
