对Atallah算法的一些改进

Improvements on Atallah's Algorithm

在不增加Atallah算法的时间、空间复杂度的前提下,对Atallah算法进行了以下改进:用回路合并的思想代替原来的缝合思想,简化了算法的第三步,去掉了算法的第四步;简化了辅图的构造。从而避免了二次寻找欧拉回路;避免了大容量数组的引入。

This paper gives a new algorithm from Atallah＇ s algorithm proposed in 1984. The authors of this paper made many improvements. First of all, combining replaced sewing. This simplified the third step. Secondly, the fourth step was deleted. This simplified the construction of the auxiliary graph, and avoided finding Euler tour for the second time. This also avoided the introduction of a mass storage array. These improvements made it quicker and simpler to find the Euler tour of an Euler graph, and the improvements didn＇ t increase time and space complexity of Atallah＇ s algorithm.