点属于且仅属于一个超顶点,超顶点中标号最小者称为该超顶点的根 该算法的流程由一系列循环组成。每次循环分为三步:①发现每个顶点的最小标号邻接 超顶点:②把每个超顶点的根连到最小标号邻接超顶点的根上:③所有在第2步连接在一起 的超顶点倒塌合并成为一个较大的超顶点 图G的顶点总数为N,因为超顶点的个数每次循环后至少减少一半,所以把每个连通 分量倒塌成单个超顶点至多lgN次循环即可。顶点i所属的超顶点的根记为D(i),则一开 始时有D(i)=i,算法结束后,所有处于同一连通分量中的顶点具有相同的D(i)。 122连通分量并行算法 算法中为顶点设置数组变量D和C,其中D(i)为顶点i所在的超顶点号,C(i)为和顶点 i或超顶点ⅰ相连的最小超顶点号等,根据程序运行的阶段不同,意义也有变化。算法的主 循环由5个步骤组成:①各处理器并行为每个顶点找出对应的C();②各处理器并行为每个 超顶点找出最小邻接超顶点,编号放入C(i)中;③修改所有D(i)=C(i);④修改所有 C(i)=C(C(i),运行lgN次:⑤修改所有D)为C(和D(C(i)中较小者。其中最后3步对应 意义为超顶点的合并。 顶点倒塌算法是专为并行程序设计的,多个顶点的处理具有很强的独立性,很适合分配 给多个处理器并行处理。这里让p个处理器分管N个顶点。则顶点倒塌算法的具体描述见 算法15.3,使用了p个处理器,其时间复杂度为ON/gN,其中步骤(2)为主循环,内含 5个子步骤对应上面的描述 算法153顶点倒塌算法 输入:图G的邻接矩阵A 输出:向量D(0:N-1),其中D(i)表示顶点i的标识 procedure collapse-vertices /*初始化*/ (1)for每个顶点 i par d D()=1 (2)for k=l to log n do /*以下并行为每个顶点找邻接超顶点中最小的 对应源程序中DtoC函数*/ (2.1)for每个i,j:0≤i,j≤N- I par do C(i)=min( DO I a(i,j=I and D(i)DO j if没有满足要求的Dj)then C()=D(1) endif endfor /*以下并行求每个超顶点的最小邻接超顶点 对应源程序中 C to CO函数* (2.2)for每个i,j:0≤i,j≤N- I par do C(i=min CO DO=i and CO*i) if没有满足要求的C()the C()=D()点属于且仅属于一个超顶点，超顶点中标号最小者称为该超顶点的根。 该算法的流程由一系列循环组成。每次循环分为三步：①发现每个顶点的最小标号邻接 超顶点；②把每个超顶点的根连到最小标号邻接超顶点的根上；③所有在第 2 步连接在一起 的超顶点倒塌合并成为一个较大的超顶点。 图 G 的顶点总数为 N，因为超顶点的个数每次循环后至少减少一半，所以把每个连通 分量倒塌成单个超顶点至多㏒ N 次循环即可。顶点 i 所属的超顶点的根记为 D(i)，则一开 始时有 D(i)=i，算法结束后，所有处于同一连通分量中的顶点具有相同的 D(i)。 1.2.2 连通分量并行算法 算法中为顶点设置数组变量 D 和 C，其中 D(i)为顶点 i 所在的超顶点号，C(i)为和顶点 i 或超顶点 i 相连的最小超顶点号等，根据程序运行的阶段不同，意义也有变化。算法的主 循环由 5 个步骤组成：①各处理器并行为每个顶点找出对应的 C(i)；②各处理器并行为每个 超顶点找出最小邻接超顶点，编号放入 C(i)中；③修改所有 D(i)=C(i)；④修改所有 C(i)=C(C(i))，运行㏒ N 次；⑤修改所有 D(i)为 C(i)和 D(C(i))中较小者。其中最后 3 步对应 意义为超顶点的合并。 顶点倒塌算法是专为并行程序设计的，多个顶点的处理具有很强的独立性，很适合分配 给多个处理器并行处理。这里让 p 个处理器分管 N 个顶点。则顶点倒塌算法的具体描述见 算法 15.3，使用了 p 个处理器，其时间复杂度为 O(N2 /p ㏒ N)，其中步骤(2)为主循环，内含 5 个子步骤对应上面的描述。 算法 15.3 顶点倒塌算法 输入：图 G 的邻接矩阵 A 输出：向量 D( 0 ：N-1 )，其中 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