论文部分内容阅读
本文探讨了基于CREW PRAM模型上的一种树的后根遍历的并行算法。
首先介绍了并行计算模型，提出了一种基于CREWPRAM模型上的一种树的后根遍历并行算法，并给出了对应的串行程序，以便对照分析其时间复杂度。欧拉圈是图论中的重要概念，树本身并不含欧拉圈，用两个有向弧〈u，v〉和〈v，u〉代替树中的每条边(u,v)，此时该树便是一个欧拉图，由所有有向弧构成了该树的欧拉圈。在欧拉圈中，先记下每个结点的双亲，然后从根结点开始顺着欧拉圈进行如下操作：对于每一个弧〈u，v〉，如果u是v的双亲，则对弧〈u，v〉赋权重0；如果v是u的双亲，则对弧〈u，v〉赋权重1；然后对上述加权弧执行前缀和操作。显然前缀和将按自然数序列依次递增。若执行到弧〈u，v〉得到一个新的前缀和，则此前缀和就是结点u在后根遍历序列中的位置。最后得到的树的后根遍历并行算法使用O(n)个处理器，时间复杂度为O(logn)。