MAX (i)for每个顶点jdo j)= i and C()≠ i and w() th C()=C() temp=wO) dif (iv) if temp<N and J(temp)<n then 通知处理器0将边 temp, J(temp)加入MST数组 (2. 3)for i=0 to N-1 (2. 4)for i=l to log N /*以下对应源程序中 CC to CO函数* for j=0 to N-l par do C()=C(C() /*以下对应源程序中 Cd to DO函数*/ (2. 5)for i=0 to N-l par do D()=min{C(1),D(C(U)} endwhile MPI源程序请参见所附光盘。 1.5小结 本章针对传递闭包、连通分量、单源最短路径、最小生成树等4个经典图论问题,分 别介绍了它们的一种典型算法,以及在MPI并行环境下的算法实现。其中除连通分量外, 其它3个问题的并行算法实现均由串行算法并行化而得到;通过这3个问题,较为详细的介 绍了图论问题串行解法并行化的一般思路:均匀数据划分,独立计算。如何划分才能尽量做 到计算的独立,是划分的关键。在最小生成树 Sollin算法的并行化中,甚至在程序运行中按 照不同的对象对数据进行了划分 除了常见的串行算法并行化之外,本章还通过连通分量问题的解法,接触了根据并行机 特点,直接为并行环境设计的图论问题解法。这种情况在非数值算法问题中并非特例 本章的编写主要参考了文献。其中,并行传递闭包和连通分量算法也可以参见文献21, 单源最短路径 Dijkstra算法也可以参见文献,而最小生成树Soli算法也可以参见文献凵。(ⅱ) tempw = MAX (ⅲ) for 每个顶点 j do if D(j)=i and C(j)≠i and W(j)<tempw then C(i) = C(j) tempw = W(j) tempj = j endif endfor (ⅳ) if tempj<N and J(tempj)<N then 通知处理器 0 将边(tempj, J(tempj))加入 MST 数组 endif endfor (2.3)for i=0 to N-1 par_do D(i) = C(i) endfor (2.4)for i=1 to ㏒ N do /* 以下对应源程序中 CC_to_C()函数 */ for j=0 to N-1 par_do C(j) = C(C(j)) endfor endfor /* 以下对应源程序中 CD_to_D()函数 */ (2.5)for i=0 to N-1 par_do D(i) = min{ C(i), D(C(i)) } endfor endwhile End MPI 源程序请参见所附光盘。 1.5 小结 本章针对传递闭包、连通分量、单源最短路径、最小生成树等 4 个经典图论问题，分 别介绍了它们的一种典型算法，以及在 MPI 并行环境下的算法实现。其中除连通分量外， 其它 3 个问题的并行算法实现均由串行算法并行化而得到；通过这 3 个问题，较为详细的介 绍了图论问题串行解法并行化的一般思路：均匀数据划分，独立计算。如何划分才能尽量做 到计算的独立，是划分的关键。在最小生成树 Sollin 算法的并行化中，甚至在程序运行中按 照不同的对象对数据进行了划分。 除了常见的串行算法并行化之外，本章还通过连通分量问题的解法，接触了根据并行机 特点，直接为并行环境设计的图论问题解法。这种情况在非数值算法问题中并非特例。 本章的编写主要参考了文献[1]。其中，并行传递闭包和连通分量算法也可以参见文献[2]， 单源最短路径 Dijkstra 算法也可以参见文献[3]，而最小生成树 Sollin 算法也可以参见文献[4]