并行计算-实验指导-实验03 图论

《并行计算-实验指导-实验03 图论》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验3图论1.1传递闭包11.1传递闭包串行算法11.2传递闭包并行算法32.2连通分量52.1顶点倒塌法算法原理描述52.2连通分量并行算法53.3单源最短路径73.1最短路径串行算法73.2最短路径并行算法84.4最小生成树104.1最小生成树串行算法104.2最小生成树并行算法125.5小结146.参考文献147.附录连通分量并行算法的MPI源程序15图论在计算机科学、信息科学、人工智能、网络理论、系统工程、控制论、运筹学和经济管理等领域有着广泛的应用。但很多图论问题虽易表达，却难以求解，其中有相当多的图论问题均属NP完全问题。本章主要介绍工程实用简单图论问题的

2、并行算法及其MPI编程实现，包括传递闭包、连通分量、最短路径和最小生成树等。1.1传递闭包设A是一个含N个顶点的有向图G的布尔邻接矩阵(BooleanAdjacentMatrix)，即元素aij=1当且仅当从顶点i到j有一条有向边。所谓A的传递闭包（TransitiveClosure），记为A+，是一个N×N的布尔矩阵，其元素bij=1当且仅当：①i=j；或②从i出发存在有向路径到j，又称为顶点i到j可达。从G的布尔邻接矩阵A求出G的传递闭包，就称为传递闭包问题。传递闭包问题有很强的应用背景，在科学计算中广泛存在。传递闭包问题的经典解法之一就是利用布尔矩阵的乘法来求解

3、。本节将把这一算法分别在串行和并行机上实现。1.1传递闭包串行算法利用布尔矩阵相乘求解传递闭包问题的原理为：对于布尔矩阵(A+I)k中的任一元素bij，bij=1表示从i到j存在长度小于等于k的可达路径，否则，bij=0。显然对于k=1，(A+I)1中bij=1当且仅当从i到j路径长度为0（i=j）或为1（从i到j存在有向边）；(A+I)2中，bij=1当且仅当从i到j路径长度小于等于2；((A+I)2)2中，bij=1当且仅当从i到j路径长度小于等于4，等等。因为任意两点间如果存在可达路径，长度最多为N-1，所以k≥N-1时，(A+I)k就是所求的传递闭包A+。于是

4、(A+I)矩阵的㏒N次自乘之后所得的矩阵就是所求的传递闭包。根据前面的叙述，很自然的有下面的传递闭包串行算法15.1，其时间复杂度为O(N3㏒N)。算法15.1传递闭包串行算法输入：图G的布尔邻接矩阵A输出：A的传递闭包MprocedureclosureBegin(1)读入矩阵A/*以下作A=A+I的运算*/(2)fori=0toN-1doa(i,i)=1endfor/*以下是A矩阵的㏒N次自乘，结果放入M矩阵；每次乘后，结果写回A矩阵*/(3)fork=1to㏒Ndo(3.1)fori=0toN-1doforj=0toN-1dos=0while(s

5、i,s)=0ora(s,j)=0)dos=s+1endwhileifs

6、。为了使算法简明，在本章中，仅在算法的MPI实现中才考虑不能整除的情况。在以后的几节中，N、p、n都具有上面约定的意义，不再多说。为了并行处理，这里将矩阵(A+I)进行划分，分别交给p个处理器。在每次矩阵乘法的计算中，将N×N的结果矩阵(A+I)2均匀划分成p×p个子块，每块大小为n×n。处理器i负责计算位于第i子块行上的p个子块。对整个子块行的计算由p次循环完成，每次计算一个子块。每个处理器为了计算一个n×n大小的子块，需要用到源矩阵(A+I)中对应的连续n行（局部数据a）和连续n列的数据（局部数据b）。计算完成后，各处理器循环交换局部数据b，就可以进行下一个子块的

7、计算了。于是，总体算法由2层循环构成，外层是矩阵M=A+I的㏒N次自乘，每次首先完成矩阵M的一次自乘，然后将结果写回M；内层是p个子块的计算，每次首先完成各自独立的计算，然后处理器间循环交换局部数据b。算法运行期间，矩阵M的数据作为全局数据由处理器0维护。根据以上思想，并行算法描述见下面的算法15.2，使用了p个处理器，其时间复杂度为O(N3/p㏒N)。其中myid是处理器编号，下同。算法15.2传递闭包并行算法输入：图G的布尔邻接矩阵A输出：A的传递闭包Mprocedureclosure-parallelBegin/*由处理器0读入矩阵A到M中，并