-
1.
3
图论
图论在计算机科学、信息科学、
人工智能、网络理论、系统工程、控制论、运筹学和经
济管理等领域有着广泛的应用。<
/p>
但很多图论问题虽易表达，
却难以求解，
其中有相当多的图
论问题均属
NP
完全
问题。本章主要介绍工程实用简单图论问题的并行算法及其
MPI
编程
实现，包括传递闭包、连通分量、最短路径和最小生成树等。
1.1
传递闭包
设
A
是一个含
N
个顶点的有向图
G
的
布
尔邻接矩阵
(Boolean Adjacent Matrix)
，即元素
a
ij
=1
当且仅当从顶点
i
到
j
有一条有向边。所谓
A
的
< br>传递闭包
（
Transitive
Closure
）
，记为
A
+
，是一个
N
×
N
的布尔矩阵，其元素
b
< br>ij
=1
当且仅当：①
i=j<
/p>
；或②从
i
出发存在有向路径
到
j
，又称为顶点
i
到
j
可达。从
G<
/p>
的布尔邻接矩阵
A
求出
< br>G
的传递闭包，就称为
传递闭包
问题
。
传递闭包问题有很强的应用背
景，
在科学计算中广泛存在。
传递闭包问题的经典解法之
一就是利用布尔矩阵的乘法来求解。本节将把这一算法分别在串行和并行机上实现。
1.1.1
传递闭包串行算法
利用布尔矩阵相乘
求解传递闭包问题的原理为：对于布尔矩阵
(A+I)
k
中的任一元素
b
ij
，
b
ij
=1
表示从
i
到
j
存在长度小于等于
k
的可达路径，否则，
b
ij
=0
。显然对于
k=1
，
(A+I)
1
中
b
ij
=1
当且仅当从
i
到
j
路径长度为
0
（
i=j
）或为
1
（从
i
到
j
存在有向边）
；
(A+I)
2
中，<
/p>
b
ij
=1
当且
仅当从
i
到
j
路径长度小于等于
2
；
((A+I)<
/p>
2
)
2
中，<
/p>
b
ij
=1
当且
仅当从
i
到
j
路径长度小于等
于
4
，等等。因为任意
两点间如果存在可达路径，长度最多为
N-1
，所以
k
≥
N-1
时，
(A+I)
k
就是所求的传递闭包
A
+
。
于是
(A+I)
矩阵的㏒
N
次自乘
之后所得的矩阵就是所求的传递闭包。
根据前面的叙述，很自
然的有下面的传递闭包串行算法
15.1
，其时间复杂度为
O(N
3
㏒
N)<
/p>
。
算法
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
while
<
br>进行划分，分别交给
，就可以进行下一个子块的计算了。 的传递闭包 N
<
br>和 paramul() <
br>图
(s
and
(a(i,s)=0
or
a(s,j)=0)
do
s = s+1
endwhile
if
s
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
1.1.2
传递闭包并行算法
本小节将把上一小
节里的算法并行化。在图论问题的并行化求解中，经常使用将
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
于是，总体算法由<
/p>
2
层循环构成，外层是矩阵
M=A+I<
/p>
的㏒
N
次自乘，每次首先完成矩
阵
M
的一次自乘，然后将结果写回
M
；内层是
p
个子块的计算
，每次首先完成各自独立的
计算，然后处理器间循环交换局部数据
b
。算法运行期间，矩阵
M
的数据作
为全局数据由
处理器
0
维护。
根据以上思想，
并行算法描述见下面的算法<
/p>
15.2
，
使用了
p
个处理器，
其时间复杂度为
O(N
3
/p
㏒
N)
。其中
myid
是处理器编号，下同。
算法
15.2
传递闭包并行算法
输入：
图
G
的布尔邻接
矩阵
A
输出：
A
M
procedure closure-
parallel
Begin
/*
由处理器
0
读入矩阵
A
到
M
中，并进行
M=M+I
运算
对应
源程序中
readmatrix()
函数
*/
(1)
if
myid=0
then
(1.1)
读入矩阵
A
，放入
M
中
(1.2)
for
i=0
to
N-1
do
m(i,i)=1
endfor
endif
(2)
各处理器变量初始化
/*
以下是主循环，矩阵
M
的㏒
次自乘
*/
(3)
for
i=1
to
㏒
N
par_do
/*
以下向各处理器发送对应子块行和列数据
对应源程序中
sendmatrix
()
函数
*/
(3.1)
for
j=1
to
p-1
do
(
ⅰ
)
处理
器
0
发送第
j
个子块行的数据给处理器
j
，成为
j<
/p>
的局部数据
a
(
ⅱ
) <
/p>
处理器
0
发送第
j
个子块列的数据给处理器
j
，成为<
/p>
j
的局部数据
b
endfor
/*
以下是各处理器接收接收和初
始化局部数据
a
和
b
对应源程序中
getmatrix()
函数
*/
(3.2)
处理器
0
更新自己的局部数据
a
和
b
(3.3)
处理器
1
到
p-1
从处理器
0
接受数据，作为局部数据
a
b
/*
以下是乘法运算过程，对应源程序中
函数
*/
(3.4)
for
j=0
to
p-1
do
(
ⅰ
)
处理
器
k
计算结果矩阵的子块
(k,
((k+j) mod p))
(
ⅱ
)
各处
理器将数据
b
发送给前一个处理器
(
ⅲ
)
各处理器从后一个处理器接收数据
b
endfor
/*
以
下是各处理器将局部计算结果写回
M
数组
对应源程序中
writeback(
)
函数
*/
(3.5)
if
myid=0
then
(
ⅰ
)
计算结果直接写入矩阵
M
(
ⅱ
)
接受其它处理器发送来的计算结果并写入
M
else
发送计
算结果的
myid
子块行数据给处理器
0
endif
endfor
End
MPI
源程序请参见所附光盘。
1.2
连通分量
G
的一个
连通分量
(Connected
Component)
是
G
的一个最大连通子图，该子图中每对
顶点间均有一条路径。
根据图
G
，
如何找出其所有连通分量的问题称为
连通分量问题
< br>。
解决
该问题常用的方法有
3<
/p>
种：
①使用某种形式的图的搜索技术；
②
通过图的布尔邻接矩阵计算
传递闭包
；③顶点倒塌算法。本节将
介绍如何在并行环境下实现顶点倒塌算法。
1.2.1
顶点倒塌法算法原理描述
顶点倒塌
（
Vertex Colla
pse
）
算法
中，
一开始图中的
N
个顶点看作
N
个孤立的
超顶点
(Super
Vertex)
，算法运行中，有边连通的超顶点相继合并，直到形成最后
的整个连通分量。每个顶
点属于且仅属于一个超顶点，超顶点中标号最小者称为该超顶点
的
根
。
该算
法的流程由一系列循环组成。
每次循环分为三步：
①发现每个顶
点的最小标号邻接
超顶点；
②把每个超顶点的根连到最小标号邻
接超顶点的根上；
③所有在第
2
步连接
在一起
的超顶点倒塌合并成为一个较大的超顶点。
图
G
的顶点总数为
N
，因为超顶点的个数每次循环后至少减少一半，所以把每个连通
分量
倒塌成单个超顶点至多㏒
N
次循环即可。顶点
< br>i
所属的超顶点的根记为
D(i)
，则一开
始时有
D(i)=i
，算法
结束后，所有处于同一连通分量中的顶点具有相同的
D(i)
。
1.2.2
连通分量并行算法
算法中为顶点设置
数组变量
D
和
C
，其中
D(i)
为顶点
i
所在的超顶点号，
C(i)
为和顶点
i
或超顶点
i
相连的最小超
顶点号等，根据程序运行的阶段不同，意义也有变化。算法的主
循环由
< br>5
个步骤组成：
①各处理器并行为每个顶点找出对应的<
/p>
C(i)
；
②各处理器并行为每个
超顶点找出最小邻接超顶点，编号放入
C(i)
中；③修改所有
D(i)=C(i)
；④修改所有
C(i)=C(C(i))
，运行㏒
N
次；⑤修改所有
D(i)
为
C(i)
和
D(C(i))
中较小者
。其中最后
3
步对应
意义为超顶点的合
并。
顶点倒塌算法是专为并行程序设计的，
< br>多个顶点的处理具有很强的独立性，
很适合分配
给多个处
理器并行处理。这里让
p
个处理器分管
N
个顶点。则顶点倒塌算法的具体描述见
算法
< br>15.3
，使用了
p
个处理器，
其时间复杂度为
O(N
2
/p
㏒
N)
，其中步骤
(2
)
为主循环，内含
5
个子步骤对应上面
的描述。
算法
15.3
顶点倒塌算法
输入：
图
G
的邻接矩阵<
/p>
A
输出：
向量
D
(
0
：
N-1 )
，其中
< br>D(i)
表示顶点
i
的标识
procedure collapse-vertices
Begin
/*
初始化
*/
(1)
for
每个顶点
i
par_do
D(i) = i
endfor
(2)
for
k=1
to
㏒
N
do
/*
以下并行为每个顶点找邻接超顶点中最小的
对
应源程序中
D_to_C()
函数
*/
(2.1)
for
每个
i, j : 0
≤
i, j
≤
N-1
par_do
C(i) = min{ D(j) | a(i,j)=1
and
D(i)
≠
D(j) }
if
没有满足要求的
D(j)
then
C(i) = D(i)
endif
endfor
/*
以下并行求每个超顶点的最小邻接超顶点
对应源程序中
C_to_C()
函数
*/
(2.2)
for
每个
i, j : 0
≤
i, j
≤
N-1
par_do
C(i) = min{
C(j) | D(j)=i
and
C(j)
≠
i }
if
没有满足要求的
C(j)
then
C(i) = D(i)
endif
endfor
(2.3)
for
每个
i : 0
≤
i
≤
N-1
par_do
D(i) = C(i)
endfor
(2.4)
for
i=1
to
㏒
N
do
/*
以下对应源程序中
CC_to_C()
函数
*/
for
每个
j : 0
≤
j
≤
N-1
par_do
C(j) = C(C(j))
endfor
endfor
/*
以下对应源程序中
CD_to_D()
函数
*/
(2.5)
for
每个
i : 0
≤
i
≤
N-1
par_do
D(i) = min{
C(i), D(C(i)) }
endfor
endfor
End
MPI
源程序请参见章末附录。
1.3
单源最短路径
单源最短路径
(Single Source
Shortest Path)
问题
是指求从一个指定顶点
s
到其它所有顶点
i
之间的距离，因为是单一顶点到其它顶点的距离，所以称为单源。设图
G(V
,E)
是一个有向
加权网络，其中
V
和
E
分别为顶点集合和边
集合，其边权邻接矩阵为
W
，边上权值
w(i,j) >
0
，
i,j
∈
V
，
V={0,1
,
…
,N-1}
。
设
dist( i )
为最短的
路径长度，即距离，其中
s
∈
V
且
i
≠
s
。这里采用著名的
Dijkstra
算
法，并将其并行化。
1.3.1
最短路径串行算法
Dijkstra
算法
(Dijkstra
Algor
ithm)
是单源最短路径问题的经典解法之一，基本思想如
下
。
假定有一个待搜索的顶点表
VL<
/p>
，
初始化时做：
dist(s)
←
0
，
dist(i)=
∞
(i
≠
s)
，
VL=V
。
每次从
VL
（非空集）中选取这样
的一个顶点
u
，它的
dist(u)<
/p>
最小。将选出的
u
点作为搜索
顶点，
对于其它还在
VL
内的顶点
v
，
若
∈
E,
而且
dist(u)+w(u,v)
，
则更新
dist(v)
为
dist(u
)+w(u,v)
，同时从
VL
中将<
/p>
u
删除，直到
VL
成为空集时算法终止。
算法
15.4
中给出了最短路径问题的
Dijkst
ra
串行算法，其时间复杂度为
O(N
2
)
。
算法
15.4Dijkstra
串行算法
输入：
边权邻接矩阵
W
（约定顶点
i
，
j
之间无边连接时
w(i,j)=
∞，且
w(i,i) = 0
）
、
待计算顶点的标号
s
输出：
dist(0 : N-1)
，
其中
dist(i)
表示顶点
s
到顶点
i
的最短路径
(1
≤
i
≤
N
)
procedure Dijkstra
Begin
(1)
dist(s) = 0
(2)
for
i=0
to
N-1
do
if
i
≠
s
then
dist(i) =
∞
endfor
(3)
VL = V
(4)
for
i=0
to
N-1
do
(4.1)
从
VL
中找一个顶点
u
，使得
dist(u)
最小
(4.2)
for
(
每个顶点
v
∈
VL)
and
(
∈
E)
do
if
dist(u)+w(u,v)
then
dist(v) =
dist(u)+w(u,v)
endif
endfor
(5)
VL = VL-{u}
endfor
End
1.3.2
最短路径并行算法
在上一小节串行算法的基础上，这里将其并行化。思路如下：
⑴
上述算法的
(1)(2)
两步中，每个处理器分派
n=N/p
个节点进行初始化。
⑵
第
(4.1)
步可以并行化为：首先每
个处理器分派
n
个节点分别求局部最小值，然后
再
p
个处理器合作求全局最小值，
< br>最后再将这一最小值广播出去。
p
个处理器合作方法如下
：
当
p
为偶数时，后
< br>p/2
个处理器将自己的局部最小值分别发送到对应的前
p/2
个处理器中，
由前
p/2
个处理器比较出
2
个局部最小值中相对较小者
并保留。当
p
为奇数时，设
p=2h+
1,
则后
h
个处理器的值分别发送到前
h
个处理器中，比较并保留小值。一次这样的循环过后，
p
个最小值减少了一半，两次后，变为
1/4
，如此一层一层的比较，㏒
P
次循环后
，就可以
得出唯一的全局最小值。
⑶
第
(4.
2)
步可以每个处理器分配
n
个顶点，
然后独立进行更新
dist
的操作。
根据以上思路，最短路径的并行算法见算法
15.5
，使用了
p
个处理器，其时间复杂度
为
O(N
2
/p+N
㏒
p)
。这里的实现算法和对应的源程序中，
处理器
0
只进行输入输出工作，不
参与
任何其它计算；因此实际参加运算的处理器为
p-1
个，所以有
n=N/(p-1)
；另外，布尔
数组
bdist
用来标记各顶点是否已从
V
L
中取出。
算法
15.5
Dijkstra
并行算法
输入：<
/p>
边权邻接矩阵
W
（约定顶点
i
，
j
之间无边连接时
w(i,j)=
∞，且
w(i,i) =
0
）
、
待计算顶点的标号
s
输出：
dist(0 : N-1)
，
其中
dist(i)
表示顶点
s
到顶点
i
的最短路径
(1
≤
i
≤
N
)
procedure Dijkstra-parallel
Begin
/*
以下对应源程序中
ReadMatrix()
函数
*/
(1)
处理器
0
读入边权邻接矩阵
W
/*
以下初始化
d
ist
和
bdist
数组，对应源程序
中
Init()
函数
*/
(2)
for
每个顶点
i
par_do
if
i=s
then
dist(i) = 0
bdist(i) = TRUE
else
dist(i) = w(i,s)
bdist(i) =
FALSE
endif
endfor
/*
以下是算法主循环，对应源程序中
FindMinWay()
< br>函数
*/
(3)
for
i=1
to
N-1
do
/*
各处理器找出自己负责范围内未搜索节点中最小的
dist
*/
(3.1)
for
每个顶点
j
par_do
index = min{ j
| bdist(j)=FALSE }
num = dist(index)
endfor
/*
以下各处理器协作对
p-1
个
index
求
最小
*/
(3.2)
calnum = p-1
for
j=1
to
㏒
(p-1)
par_do
if
calnum mod 2=0 then
//
本次循环参加比较的数据个数为偶数
(
ⅰ
) calnum =
calnum/2
(
ⅱ
)
序号
大于
calnum
的处理器将
inde
x
和
num
发送给序号比自己小
calnum
的处理器
(
ⅲ
)
序号
小于
calnum
的处理器（不包含
0
号）在自己原有的和收到
的两个
num
之间，比较并保留较小者，同时记录对应的
< br>index
else
//<
/p>
本次循环参加比较的数据个数为奇数
(
ⅰ
) calnum =
(calnum+1)/2
(
ⅱ
)
序号
大于
calnum
的处理器将
inde
x
和
num
发送给序号比自己小
calnum
的处理器
(
ⅲ
)
序号
小于
calnum
的处理器（不包含
0
号）在自己原有的和收到
的两个
num
之间，比较并保留较小者，同时记录对应的
< br>index
endif
endfor
(3.3)
处理器
1
广播通知其它处理器自己的
num
和
< br>index
/*
以下并行更新
*/
(3.4)
for
每个顶点
j
par_do
if
bdist(j)=FALSE
then
dist(j) = min{ dist(j),
num+w(j,index) }
endif
endfor
(3.5)
顶点
index
对应处理器将对应的
bdist(index)
更改为
TRUE
endfor
End
MPI
源程序请参见所附光盘。
1.4
最小生成树
一个无向连通图
G
的生成树是指满足如下条件的
G
的子图
T
：①
T
和
G
顶点数相同
；
②
T
有足够的边使得所有顶点连通，
同时不出现回路。如果对
G
的每条边指定一个权值，
那么，边权总和最小的生成树称为
最小代价生成树
，记为
MCST
（
Minimum
Cost
Spanning
-
-
-
-
-
-
-
-
-
上一篇：houdini菜单.翻译
下一篇：在敌人面前享受筵席!