Advertisement

执行有向无环图(DAG)的topological sort

阅读量:

算法思想

基于给定有向图中的顺序关系,在其基础上将这些顶点排列为一个线性序列。而对于那些在原图中并无指定顺序关系的顶点,则可以根据需要人为设定任意顺序。由此生成的该线性序列被称为拓扑有序序列。显然,在存在回路的情况下无法得到拓扑有序序列。

例如,下图,我们可以人为限定次序:A B C D 或 A C B D

在这里插入图片描述

如何进行拓扑排序?

  1. 在有向图中选择一个无入度(即在其之前没有任何活动)的节点并记录下来;
  2. 移除该节点及其所有以该节点为终点的所有边;
  3. 重复上述操作直至图形为空或无法找到无入度节点为止;
  4. 未被记录下来的顶点自然形成了循环。

例如,在A C B H G D F E(非唯一)的情况下。通过观察图中的所有顶点均被成功打印输出后可得出结论:该有向图不含任何环路。

在这里插入图片描述

在拓扑排序的过程中,在算法执行的第一阶段,在每

全部评论 (0)

还没有任何评论哟~