基于元胞自动机的拓扑排序算法

目的 利用元胞自动机的特性,找到一种新的拓扑排序算法.方法 将AOV网构造成一个元胞自动机模型,采用经过改造的邻接链表作为元胞的数据结构,并在其中引入随机编号项,所有元胞依据随机编号顺序地遵守演化规则进行演化,实现拓扑排序.结果 利用元胞自动机的时空局部规则和并行计算特性,设计并验证了拓扑排序算法.结论 与传统算法相比本算法在时间、空间复杂性上都有较大改善,并且在应用元胞自动机理论解决图的问题方面有所贡献.

Topological sequencing algorithm based on cellular automata model