142最小生成树并行算法 在上一小节 Sollin算法的基础上,本节将其并行化。基本思路是由多个处理器同时负责 为多个树查找最短边。为了方便并行处理,各树寻找外连最短边的的任务分两步进行:①所 有处理器独立并行为每个顶点找连向其它树的最短边,并将这些数据保存:②各处理器独立 并行检索每棵树的各顶点,为整棵树找出外连最短边。注意在以上两步中,处理器间分别按 照顶点和树进行分配,对象有了变化 为了配合算法运行,设置了4个一维数组D、C、J、W:①Di)为顶点i所在的树的编 号,也就是该树中最初的顶点号,初始化为i②C(0为离顶点i最近的其它树的编号:③J(i) 为对应的顶点号:④W(i)为对应的边权,即距离。以上变量约定对MST并行算法的源程序 同样适用。运行期间每个处理器处理n=N/p个顶点或n个连通分量。 各树找出外连最短边后,接下来分3步进行树的合并:①让所有的DiC(i);②对所 有i,进行C(i=C(C(i)运算,并循环吧N次:③对所有i,更新D(为C(和DC()中较小 者。以上合并过程类似顶点倒塌算法中超顶点的合并 设MST为输出的最小生成树的邻接矩阵,运行期间由0号处理器维护,则并行算法的 描述见算法157,使用了p个处理器,其时间复杂度为O(N/plgN) 算法157并行 Sollin MSt算法 输入:原始图G的邻接矩阵A 输出:所求最小生成树的邻接矩阵MST procedure Sollin-MST-parallel /*以下初始化将图初始化为N棵树* (1)for每个顶点 i par do endfor (2)whle图G未连通do /*以下各处理器为所负责的顶点找出距离最近的树 对应源程序中 d to CO函数* (2.1for每个顶点ipar_do (i)W(=MAX (i)for每个顶点jdo if a(1,j>0 and DO*D(i and a(1,j<w(i) then C(1=DO) W()=a(1j) J()=J endif (ni)if w(i)=MAX then C()=D(1) endif endfor /*以下各处理器为所负责的树找出外连的最短边 对应源程序中 C to CO函数/ (2.2)for每棵树ipar_do1.4.2 最小生成树并行算法 在上一小节 Sollin 算法的基础上，本节将其并行化。基本思路是由多个处理器同时负责 为多个树查找最短边。为了方便并行处理，各树寻找外连最短边的的任务分两步进行：①所 有处理器独立并行为每个顶点找连向其它树的最短边，并将这些数据保存；②各处理器独立 并行检索每棵树的各顶点，为整棵树找出外连最短边。注意在以上两步中，处理器间分别按 照顶点和树进行分配，对象有了变化。 为了配合算法运行，设置了 4 个一维数组 D、C、J、W：① D(i)为顶点 i 所在的树的编 号，也就是该树中最初的顶点号，初始化为 i；② C(i)为离顶点 i 最近的其它树的编号；③ J(i) 为对应的顶点号；④ W(i)为对应的边权，即距离。以上变量约定对 MST 并行算法的源程序 同样适用。运行期间每个处理器处理 n=N/p 个顶点或 n 个连通分量。 各树找出外连最短边后，接下来分 3 步进行树的合并：①让所有的 D(i)=C(i)；②对所 有 i，进行 C(i)=C(C(i))运算，并循环㏒ N 次；③对所有 i，更新 D(i)为 C(i)和 D(C(i))中较小 者。以上合并过程类似顶点倒塌算法中超顶点的合并。 设 MST 为输出的最小生成树的邻接矩阵，运行期间由 0 号处理器维护，则并行算法的 描述见算法 15.7，使用了 p 个处理器，其时间复杂度为 O(N2 /p ㏒ N)。 算法 15.7 并行 Sollin MST 算法 输入：原始图 G 的邻接矩阵 A 输出：所求最小生成树的邻接矩阵 MST procedure Sollin-MST-parallel Begin /* 以下初始化将图初始化为 N 棵树 */ (1) for 每个顶点 i par_do D(i) = i endfor (2) while 图 G 未连通 do /* 以下各处理器为所负责的顶点找出距离最近的树 对应源程序中 D_to_C()函数 */ (2.1)for 每个顶点 i par_do (ⅰ) W(i) = MAX (ⅱ) for 每个顶点 j do if a(i, j)>0 and D(j)≠D(i) and a(i, j)<W(i) then C(i) = D(j) W(i) = a(i,j) J(i) = j endif endfor (ⅲ) if W(i)=MAX then C(i) = D(i) endif endfor /* 以下各处理器为所负责的树找出外连的最短边 对应源程序中 C_to_C()函数 */ (2.2)for 每棵树 i par_do (ⅰ) tempj = N+1