Algorithm 版 (精华区)

发信人: Lerry (想不开·撞树), 信区: Algorithm
标  题: 并行算法——欧拉回路技术
发信站: 哈工大紫丁香 (2002年03月22日14:52:52 星期五), 站内信件

并行算法——指针转移
 上一页 | 返回目录 | 下一页
1.3 欧拉回路技术
在本节中，我们将介绍欧拉回路技术，并说明如何运用这一技术在n个结点的二叉树中计
算出每个结点的深度。在这个O(lgn)时间的EREW算法中，关键的一步就是并行前缀计算
。
为了在PRAM中存储二叉树，我们采用了简单的二叉树表示法。每个结点i有三个域paren
t[i],left[i],right[i]，分别指向结点i的父母、左子女和右子女。假定每个结点用一
个非负整数来表示。我们为每个结点联接三个而不是一个处理器，其原因我们在下面将
会明白。称这三个处理器为结点的A，B和C处理器，我们可以很容易地在结点与其三个处
理器之司找出对应关系。例如，结点i可以与处理器3i，3i+1和3i+2相联接。
在串行RAM上，计算包含n个结点的树中每个结点的深度所需运行时间为O(n)。采用一种
简单的并行算法来计算结点深度时，算法可以从树的根结点开始把一种“波”向下传输
。这种波同时到达深度相同的所有结点，因此通过对波载计数器增值，我们就能计算出
每个结点的深度。这种并行算法对完全二叉树很适用，这是因为其运行时间与树的高度
成正此。而树的高度最大为n-1，这时算法的运行时间为O(n)，这并不优于串行算法。但
是，如果我们运用欧拉回路技术，不论树的高度是多少，都能够在EREW PRAM上用O(lgn
)的运行时间计算出结点的深度。
一个图的欧拉回路是通过图的每条边一次一个回路，当然，在此过程中它可以多次访问
一个结点。根据图论算法可知，一个有向连通图具有欧拉回路当且仅当对所有结点v，v
的出度等于v的入度。因为无向图每条无向边(u，v)对应于相应的有向图中的两条边(u，
v)和(v，u)，因此任何无向连通图改成的有向图均包含欧拉回路，这对无向树也自然成
立。
(a)
(b)
图4 运用欧拉回路技术来计算每个结点在二叉树中的深度
为了计算二叉树T中结点的深度，首先在改写的有向树T中形成一个欧拉回路。该回路对
应于树的遍历过程，如图4(a)所示，它可以用一个连接树中所有结点的链表来表示。其
结构如下：
如果结点的左子女存在，则结点的A处理器指向其左子女的A处理器，否则就指向自身的
B处理器。
如果结点存在右子女，则结点的B处理器指向其右子女的A处理器，否则就指向其自身的
C处理器。
如果一个结点是其父母结点的左子女，则结点的C处理器指向其父母的B处理器，如果该
结点是其父母结点的右子女，则结点的C处理器指向其父母的C处理器。根结点的C处理器
指向NIL。
因此，根据欧拉回路形成的链表的表头是根结点的A处理器，表尾是根节点的C处理器。
如果已知构成原始树的指针，则我们可以在O(1)的时间内构造出欧拉回路。
在我们获得表示T的欧拉回路的链表后，我们在每个A处理器中放入值1，在每个B处理器
中放入值0，在每个C处理器中放入值-1，如图4(a)所示。然后如第1.2节中那样，我们运
用满足结合律的普通加法来执行并行前缀计算。图4(b)说明了并行前缀计算的结果。
我们说，在执行完并行前缀计算过程后，每个结点的深度值在结点的C处理器中。为什么
呢？我们按以下要求把数放入A，B和C三个处理器中：访问子树的最后结果是把运行和加
上0。每个结点i的A处理器对其左子女树的运行和加1，这表明i的左子女的深度比i的深
度大1。B处理器对运行和没有影响，这是因为i的左子女的深度与其右子女的深度相等。
C处理器使运行和减1，以便对i的父母结点来说，对以i为根结点的子树进行访问后运行
和不会改变。
我们可以在O(1)的时间内计算出表示欧拉回路的列表。列表中包含3n个对象，所以执行
并行前缀计算过程仅需O(lgn)的运行时间。因此，计算所有结点深度所花费的全部运行
时间为O(lgn)。又因为算法执行中不需要对有存储器执行并发存取操作，所以该算法是
一个EREW算法。

--
　　不在乎天长地久，就怕你从来没有！

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 天外飞仙]