数据结构与算法(28): 图- 拓扑排序

发表于   |   分类于

定义

  拓扑排序(Topological Order)是指：将一个有向无环图(Directed Acyclic Graph, DAG)进行排序而得到一个有序的线性序列。拓扑排序不必是唯一的，任何合理的排序都是可以的。

算法步骤

  1. 构造一个队列Q和拓扑排序的结果队列T；
  2. 把所有没有依赖顶点的节点放入Q；
  3. 当Q还有顶点的时候
    3.1. 从Q中取出一个顶点i（将i从Q中删除），并放入T；
    3.2. 对顶点i的每一个邻接点j（i是起点，j是终点），去掉边(i, j)，如果j没有依赖顶点，则把j放入Q。

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