参考文献 [1]陈国良编著.并行算法的设计与分析(修订版).高等教育出版社,2002.11 [2. Hirschberg D S Parallel Algorithms for Transitive Closure and the Connected Component Problem. Proc. 8th Annu. ACM STOC. New York. 1976.55-57 3]. Dijkstra E. A Note on Two Problems in Connetion with Graphs. Numerische Mathematic 19591269-271 [4]. Goodman S E and Hedetnimi S T ed. Introduction to the Design and Analysis of Algorithms(in An Algorithm Attributed to Sollin). McGraw-Hill, New York, 1977 附录连通分量并行算法的MP源程序 1.源程序 connectc /本算法中处理器数目须小于图的顶点数* #include <stdio h> for(F=0;<N;H++) #include <stdlib.h> printf("%d",PI) #include <malloc h> printi(n); #include <math. h> 产使用动态分配的内存储邻接矩阵,以下为宏定“读入邻接矩阵 void readAO #define A(D)A[N+j char· filename, 以下为 N:顶点数 各处理器分配的顶点数 printf("Input the vertex num: n"); p处理器数 anf("%d", &N) Int n if(N%p!=0)n++ int p, A=(int")malloc(sizeof(int) "(n*p)*N printf("Error when allocating memory n") I Status status: printf("Input the adjacent matrix n"); for(=0;K<N++) 输出必要信息* for(=: <N; j++) void print(int*P) scanf("%d", &A(Lj) Int I for(=0 <N: j++) if(myid==0) A(Lj)=0,参考文献 [1]. 陈国良 编著．并行算法的设计与分析（修订版）．高等教育出版社，2002.11 [2]. Hirschberg D S. Parallel Algorithms for Transitive Closure and the Connected Component Problem. Proc. 8th Annu. ACM STOC, New York, 1976,55-57 [3]. Dijkstra E. A Note on Two Problems in Connetion with Graphs. Numerische Mathematic, 1959,1:269-271 [4]. Goodman S E and Hedetnimi S T ed. Introduction to the Design and Analysis of Algorithms(in An Algorithm Attributed to Sollin). McGraw-Hill, New York, 1977 附录 连通分量并行算法的 MPI 源程序 1. 源程序 connect.c /*本算法中处理器数目须小于图的顶点数*/ #include <stdio.h> #include <stdlib.h> #include <malloc.h> #include <math.h> #include <mpi.h> /*使用动态分配的内存存储邻接矩阵，以下为宏定 义*/ #define A(i,j) A[i*N+j] /*以下为 N:顶点数 n:各处理器分配的顶点数 p:处理器数*/ int N; int n; int p; int *D,*C; int *A; int temp; int myid; MPI_Status status; /*输出必要信息*/ void print(int *P) { int i; if(myid==0) { for(i=0;i<N;i++) printf("%d ",P[i]); printf("\n"); } } /*读入邻接矩阵*/ void readA() { char *filename; int i,j; printf("\n"); printf("Input the vertex num:\n"); scanf("%d",&N); n=N/p; if(N%p!=0) n++; A=(int*)malloc(sizeof(int)*(n*p)*N); if(A==NULL){ printf("Error when allocating memory\n"); exit(0); } printf("Input the adjacent matrix:\n"); for(i=0;i<N;i++) for(j=0;j<N;j++) scanf("%d",&A(i,j)); for(i=N;i<n*p;i++) for(j=0;j<N;j++) A(i,j)=0;