An Optimal Algorithm for Prufer Codes
Xiaodong Wang, Lei Wang, Yingjie Wu
DOI: 10.4236/jsea.2009.22016   PDF    HTML     7,978 Downloads   12,752 Views   Citations


This paper studies the algorithms for coding and decoding Prufer codes of a labeled tree. The algorithms for coding and decoding Prufer codes of a labeled tree in the literatures require time usually. Although there exist linear time algorithms for Prufer-like codes [1,2,3], the algorithms utilize the integer sorting algorithms. The special range of the integers to be sorted is utilized to obtain a linear time integer sorting algorithm. The Prufer code problem is reduced to integer sorting. In this paper we consider the Prufer code problem in a different angle and a more direct manner. We start from a naïve algorithm, then improved it gradually and finally we obtain a very practical linear time algorithm. The techniques we used in this paper are of interest in their own right.

Share and Cite:

Wang, X. , Wang, L. and Wu, Y. (2009) An Optimal Algorithm for Prufer Codes. Journal of Software Engineering and Applications, 2, 111-115. doi: 10.4236/jsea.2009.22016.

Conflicts of Interest

The authors declare no conflicts of interest.


[1] [1] S. Caminiti, I. Finocchi, and R. Petreschi, “A unified approach to coding labeled trees,” in Proceedings of the 6th Latin American Symposium on Theoretical Infor-matics (LATIN’04), LNCS 2976, pp. 339-348, 2004.
[2] [2] S. Caminiti, I. Finocchi, and R. Petreschi, “On coding la- beled trees,” To appear on Theoretical Computer Sci-ence, 2006.
[3] [3] H. C. Chen and Y. L. Wang, “An efficient algorithm for generating Prufer codes from labeled trees,” Theory of Computing Systems, Vol. 33, pp. 97–105, 2000.
[4] [4] A. Cayley, “A theorem on trees,” Quarterly Journal of Mathematics, Vol. 23, pp. 376–378, 1889.
[5] [5] L. Devroye, “Non-uniform random variate generation,” Springer-Verlag, New York, Exercise 2, pp. 666, 1986.
[6] [6] A. Nijenhuis and H. S. Wilf, “Combinatorial algorithms for computers and calculators,” Second Editon, Academic Press, New York, Exercise 46, pp. 293, 1978.

Copyright © 2024 by authors and Scientific Research Publishing Inc.

Creative Commons License

This work and the related PDF file are licensed under a Creative Commons Attribution 4.0 International License.