图论.doc

文档介绍：3 图论
图论在计算机科学、信息科学、人工智能、网络理论、系统工程、控制论、运筹学和经济管理等领域有着广泛的应用。但很多图论问题虽易表达,却难以求解,其中有相当多的图论问题均属NP完全问题。本章主要介绍工程实用简单图论问题的并行算法及其MPI编程实现,包括传递闭包、连通分量、最短路径和最小生成树等。
传递闭包
设A是一个含N个顶点的有向图G的布尔邻接矩阵(Boolean Adjacent Matrix),即元素aij=1当且仅当从顶点i到j有一条有向边。所谓A的传递闭包(Transitive Closure),记为A+,是一个N×N的布尔矩阵,其元素bij=1当且仅当:①i=j;或②从i出发存在有向路径到j,又称为顶点i到j可达。从G的布尔邻接矩阵A求出G的传递闭包,就称为传递闭包问题。
传递闭包问题有很强的应用背景,在科学计算中广泛存在。传递闭包问题的经典解法之一就是利用布尔矩阵的乘法来求解。本节将把这一算法分别在串行和并行机上实现。
传递闭包串行算法
利用布尔矩阵相乘求解传递闭包问题的原理为:对于布尔矩阵(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+。于是(A+I)矩阵的㏒N次自乘之后所得的矩阵就是所求的传递闭包。
根据前面的叙述,,其时间复杂度为O(N3㏒N)。
算法
输入:图G的布尔邻接矩阵A
输出:A的传递闭包M
procedure closure
Begin
读入矩阵A
/* 以下作A = A+I的运算*/
for i=0 to N-1 do
a(i, i) = 1
endfor
/* 以下是A矩阵的㏒N次自乘,结果放入M矩阵;每次乘后,结果写回A矩阵*/
for k=1 to ㏒N do
()for i=0 to N-1 do
for j=0 to N-1 do
s=0
while (s<N) and (a(i,s)=0 or a(s,j)=0) do
s = s+1
endwhile
if s<N then m(i,j)=1 else m(i,j)=0
endfor
endfor
/* 计算结果从M写回A */
()for i=0 to N-1 do
for j=0 to N-1 do
a(i, j) = m(i, j)
endfor
endfor
endfor
End
传递闭包并行算法
本小节将把上一小节里的算法并行化。在图论问题的并行化求解中,经常使用将N个顶点(或连通分量)平均分配给p个处理器并行处理的基本思想。其中每个处理器分配到n个顶点,即n=N/p。无法整除时,一般的策略是在尽量均分的前提下,给最后一个处理器分配较少的顶点。为了使算法简明,在本章中,仅在算法的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,就可以进行下一个子块的计算了。
于是,总体算法由2层循环构成,外层是矩阵M=A+I的㏒N次自乘,每次首先完成矩阵M的一次自乘,然后将结果写回M;内层是p个子块的计算,每次首先完成各自独立的计算,然后处理器间循环交换局部数据b。算法运行期间,矩阵M的数据作为全局数据由处理器0维护。
根据以上思想,,使用了p个处理器,其时间复杂度为O(N3/p㏒N)。其中myid是处理器编号,下同。
算法
输入:图G的布尔邻接矩阵A
输出:A的传递闭包M
procedure closure-parallel
Begin
/* 由处理器0读入矩阵A到M中,并进行M=M+I运算
对应源程序中readmatri