Prufer编解码的最优算法

摘要：

讨论标号树的Prufer编码的编解码算法.文献中常见的Prufer编解码算法需要O(n log n)时间.文献[1,2,4,9]提出了Prufer编解码的线性时间算法.这些算法都用到了整数排序算法,利用待排序整数的取值特殊性,得到线性时间整数排序算法.由此将Prufer编解码问题的计算归结为整数排序问题.本文从更直接的角度考察Prufer编解码问题,从简单算法出发,挖掘问题的本质特征,逐步简化,得到Prufer编码的一个非常简单实用的线性时间最优编解码算法.本文采用的解决问题的方法也具有一定的技巧,可供解决类似问题时借鉴.

关键词：标号树、Prufer编码、整数排序、最优算法

所属期刊栏目：29

分类号：TP30(计算技术、计算机技术)

资助基金：国家自然科学基金60172017;福建省自然科学基金A0510008

在线出版日期：2008-05-26（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：687-690