执行有向无环图(DAG)的topological sort
发布时间
阅读量:
阅读量
算法思想
基于给定有向图中的顺序关系,在其基础上将这些顶点排列为一个线性序列。而对于那些在原图中并无指定顺序关系的顶点,则可以根据需要人为设定任意顺序。由此生成的该线性序列被称为拓扑有序序列。显然,在存在回路的情况下无法得到拓扑有序序列。
例如,下图,我们可以人为限定次序:A B C D 或 A C B D

如何进行拓扑排序?
- 在有向图中选择一个无入度(即在其之前没有任何活动)的节点并记录下来;
- 移除该节点及其所有以该节点为终点的所有边;
- 重复上述操作直至图形为空或无法找到无入度节点为止;
- 未被记录下来的顶点自然形成了循环。
例如,在A C B H G D F E(非唯一)的情况下。通过观察图中的所有顶点均被成功打印输出后可得出结论:该有向图不含任何环路。

在拓扑排序的过程中,在算法执行的第一阶段,在每
全部评论 (0)
还没有任何评论哟~
