3图论 图论在计算机科学、信息科学、人工智能、网络理论、系统工程、控制论、运筹学和经 济管理等领域有着广泛的应用。但很多图论问题虽易表达,却难以求解,其中有相当多的图 论问题均属NP完全问题。本章主要介绍工程实用简单图论问题的并行算法及其MPI编程 实现,包括传递闭包、连通分量、最短路径和最小生成树等。 1.1传递闭包 设A是一个含N个顶点的有向图G的布尔邻接矩阵( Boolean Adjacent Matrix),即元素 a1=1当且仅当从顶点i到j有一条有向边。所谓A的传递闭包( Transitive Closure),记为 A,是一个N×N的布尔矩阵,其元素b=1当且仅当:①j=j;或②从i出发存在有向路径 到j,又称为顶点i到j可达。从G的布尔邻接矩阵A求出G的传递闭包,就称为传递闭包 问题 传递闭包问题有很强的应用背景,在科学计算中广泛存在。传递闭包问题的经典解法之 就是利用布尔矩阵的乘法来求解。本节将把这一算法分别在串行和并行机上实现。 111传递闭包串行算法 利用布尔矩阵相乘求解传递闭包问题的原理为:对于布尔矩阵(A+)中的任一元素b b产=1表示从i到j存在长度小于等于k的可达路径,否则,b=0。显然对于k=1,(A+)中 b=1当且仅当从i到j路径长度为0(i=j)或为1(从i到j存在有向边);(A+D2中,b=1 当且仅当从i到j路径长度小于等于2;(A+)2)2中,b=1当且仅当从i到j路径长度小于等 于4,等等。因为任意两点间如果存在可达路径,长度最多为N-1,所以k≥N1时,(A+D)k 就是所求的传递闭包A+。于是(A+)矩阵的bN次自乘之后所得的矩阵就是所求的传递闭包 根据前面的叙述,很自然的有下面的传递闭包串行算法15.1,其时间复杂度为O(N3k 算法151传递闭包串行算法 输入:图G的布尔邻接矩阵A 输出:A的传递闭包M edure closure Begi (1)读入矩阵A /*以下作A=A+I的运算 (2)for 0 to N-1 do a(1,1)= endfor /*以下是A矩阵的lgN次自乘,结果放入M矩阵;每次乘后,结果写回A矩阵* (3)for k-l to log n do (3. 1)for i=0 to N-1 do for j=0 to N-l do1. 3 图论 图论在计算机科学、信息科学、人工智能、网络理论、系统工程、控制论、运筹学和经 济管理等领域有着广泛的应用。但很多图论问题虽易表达，却难以求解，其中有相当多的图 论问题均属 NP 完全问题。本章主要介绍工程实用简单图论问题的并行算法及其 MPI 编程 实现，包括传递闭包、连通分量、最短路径和最小生成树等。 1.1 传递闭包 设 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 的传递闭包，就称为传递闭包 问题。 传递闭包问题有很强的应用背景，在科学计算中广泛存在。传递闭包问题的经典解法之 一就是利用布尔矩阵的乘法来求解。本节将把这一算法分别在串行和并行机上实现。 1.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+。于是(A+I)矩阵的㏒N次自乘之后所得的矩阵就是所求的传递闭包。 根据前面的叙述，很自然的有下面的传递闭包串行算法 15.1，其时间复杂度为 O(N3 ㏒ N)。 算法 15.1 传递闭包串行算法 输入：图 G 的布尔邻接矩阵 A 输出：A 的传递闭包 M procedure closure Begin (1) 读入矩阵 A /* 以下作 A = A+I 的运算 */ (2) for i=0 to N-1 do a(i, i) = 1 endfor /* 以下是 A 矩阵的㏒ N 次自乘，结果放入 M 矩阵；每次乘后，结果写回 A 矩阵 */ (3) for k=1 to ㏒ N do (3.1)for i=0 to N-1 do for j=0 to N-1 do s=0