拓扑排序(一) C语言详解

拓扑排序介绍

拓扑排序(Topological Order)是指，将一个有向无环图(Directed Acyclic Graph简称DAG)进行排序进而得到一个有序的线性序列。

这样说，可能理解起来比较抽象。下面通过简单的例子进行说明！

例如，一个项目包括A、B、C、D四个子部分来完成，并且A依赖于B和D，C依赖于D。现在要制定一个计划，写出A、B、C、D的执行顺序。这时，就可以利用到拓扑排序，它就是用来确定事物发生的顺序的。

在拓扑排序中，如果存在一条从顶点A到顶点B的路径，那么在排序结果中B出现在A的后面。

拓扑排序的算法图解

拓扑排序算法的基本步骤：

1. 构造一个队列Q(queue) 和 拓扑排序的结果队列T(topological)；

2. 把所有没有依赖顶点的节点放入Q；

3. 当Q还有顶点的时候，执行下面步骤：

3.1 从Q中取出一个顶点n(将n从Q中删掉)，并放入T(将n加入到结果集中)；

3.2 对n每一个邻接点m(n是起点，m是终点)；

3.2.1 去掉边<n,m>;

3.2.2 如果m没有依赖顶点，则把m放入Q;

注：顶点A没有依赖顶点，是指不存在以A为终点的边。

以上图为例，来对拓扑排序进行演示。

更多精彩内容：http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/