基于CREW PRAM模型上的一种树的后根遍历的并行算法

摘要

本文探讨了基于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)。

目录

文摘

英文文摘

独创性声明

1前言

1.1并行计算及并行算法在现实中的的应用

1.2并行计算及并行算法在国内外发展的情况

1.2.1并行计算发展的现状

1.2.2国内外在并行计算方面重点研究的领域

1.2.3并行算法的研究现状

1.3本论文研究的背景和意义

2图和树的基本知识

2.1图的基本概念

2.2树的基本知识

2.2.1树的定义

2.2.2树的遍历

2.2.3二叉树的中序遍历递归算法

2.2.4二叉树的中序遍历非递归算法

3并行算法的基本知识和并行计算模型

3.1并行算法的基本知识

3.1.1并行算法的定义与分类

3.1.2并行算法的复杂性

3.1.3并行算法运行的时间

3.2并行计算模型

3.2.1二叉树模型

3.2.2网络模型

3.2.3超立方体(k-立方体)

3.2.4网格网络

3.2.5金字塔网络

3.2.6 PRAM模型

4基于欧拉圈的树的后根遍历并行算法

4.1基于欧拉圈的树的后根遍历并行算法的基本思想

4.2欧拉圈及其构造算法

4.2.1欧拉图

4.2.2树的欧拉圈

4.2.3构造树的欧拉圈的串行程序

4.2.4构造树的欧拉圈的并行算法

4.3部分和

4.3.1求数组的部分和的并行算法

4.3.2部分和并行算法复杂度分析

4.4求树中结点的双亲

4.4.1有根树

4.4.2求树中结点双亲的串行程序

4.4.3求树中结点双亲的并行算法

4.4.4复杂度分析

4.5树的后根遍历

4.5.1基于欧拉圈的树的后根遍历的一种方法

4.5.2基于欧拉圈的树的后根遍历的串行程序

4.5.3基于欧拉圈的树的后根遍历的并行算法

4.5.4复杂度分析

4.6几种遍历算法的比较

5总结

参考文献

致谢