目录
- 一、什么是拓扑排序？
- 二、拓扑排序的实现
-
- 2.1 拓扑排序模版
- 三、拓扑排序的应用
-
- 3.1 有向图的拓扑序列
- 3.2 家谱树
- 3.3 奖金
- 3.4 可达性统计
- 3.5 Directing Edges
一、什么是拓扑排序？
拓扑排序是一种有向无环图（DAG）的顶点排序方法，它将一个有向无环图中的所有顶点排成一个线性序列，使得图中任意一条有向边上的起点排在终点的前面。
这样说还不够具体，我们先来看一个例子。假设某大学的课程安排如下：
| 课程编号 | 课程名称 | 先修课程 |
|---|---|---|
| 高等数学 | ||
| 程序设计基础 | ||
| 离散数学 | ||
| 数据结构 | ||
| 高级语言程序设计 | ||
| 编译方法 | ||
| 操作系统 | ||
| 普通物理 | ||
| 计算机原理 |
为了顺利修完这九门课程，我们必须安排一个合理的学习顺序。
首先根据以上表格构建一个有向图，即若 的先修课程有
，则画一条
到
的有向边，于是可以得到：
版权声明：本文为博主作者：Iareges原创文章，版权归属原作者，如果侵权，请联系我们删除！
