3图论.docVIP

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)矩阵的㏒NO(N3㏒N) 输出：A的传递闭包M procedure closure Begin 读入矩阵A /* 以下作A = A+I的运算 */ for i=0 to N-1 do a(i, i) = 1 endfor /* 以下是A矩阵的㏒N */ for k=1 to ㏒N do (3.1)for i=0 to N-1 do for j=0 to N-1 do s=0 while (sN) and (a(i,s)=0 or a(s,j)=0) do s = s+1 endwhile if sN then m(i,j)=1 else m(i,j)=0 endfor endfor/* 计算结果从M写回A */ (3.2)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的㏒NM的一次自乘，然后将结果写回M；内层是p个子块的计算，每次首先完成各自独立的计算，然后处理器间循环交换局部数据b。算法运行期间，矩阵M的数据作为全局数据由处理器0维护。 根据以上思想，并行算法描述见下面的算法15.2，使用了p个处理器，其时间复杂度为O(N3/p㏒N)。其中myid是处理器编号，下同。 算法 15.2传递闭包并行算法 输入：图G的布尔邻接矩阵A 输出：A的传递闭包M procedure closure-parallel Begin /* 由处理器0读入矩阵A到M中，并进行M=M+I运算 对应源程序中readmatrix()函数 */ if myid=0 then (1.1) 读入矩阵A，放入M中 (1.2) for i=0 to N-1 do m(i,i)=1 endfor endif 各处理器变量初始化 /* 以下是主循环，矩阵M的㏒N */ for i=1 to ㏒N par_do