MST.rar_OpenMP多线程_mst_openmp_并行计算_最小生成树

#include "omp.h" #include <time.h> #include <iostream> using namespace std; #define INFINITY 10000 // 定义的最大值 #define MAX_VNUM 100 // 最大顶点数 // 图结构 typedef struct{ int arcs[MAX_VNUM-1][MAX_VNUM-1]; // 边（arcs[v1][v2]的值表示顶点v1与顶点v2之间边的代价） int vexnum, arcnum; } Graph; Graph G[INFINITY]; typedef struct { int fromvex, endvex; int length; } edge; int arcs[MAX_VNUM-1][MAX_VNUM-1]; edge TE[MAX_VNUM-1]; // 创建无向图 int CreateUDN(Graph G[]) { int i, j, v1, v2, w, r; cout<<"请输入顶点数和边数（格式：vnum,enum）："; scanf("%d,%d", &(G->vexnum), &(G->arcnum)); getchar(); for(i=0; i < G->vexnum; i++) { for(j=0; j < G->vexnum; j++) { if(i == j) { G->arcs[i][j] = 0; } else { G->arcs[i][j] = INFINITY; } } } for (i=0; i < G->vexnum; i++) { for(j=0; j < G->vexnum; j++) { G->arcs[i][j] = INFINITY; } } cout<<"请输入两端点的序号(从1开始)和相应的权值(共"<<G->arcnum<<"条边)(格式：(v1,v2,e))"<<endl; for (i=0; i < G->arcnum; i++) { cout<<"第"<<i+1<<"条边："; scanf("%d,%d,%d",&v1,&v2,&w); getchar(); G->arcs[v1-1][v2-1] = w; G->arcs[v2-1][v1-1] = w; } r = G->arcnum; return r; } // 运用Prim算法计算最小生成树 void Prim(Graph G[]) { int j, k, p, d, v, min; clock_t timeBegin, timeEnd; edge temp; for(j=1; j <= G->vexnum-1; j++) { TE[j-1].fromvex = 1; TE[j-1].endvex = j+1; TE[j-1].length = G->arcs[0][j]; } timeBegin = clock(); #pragma omp parallel { #pragma omp for { for(k=0; k < G->vexnum-1; k++) { // 找到代价最小 min = 10000; #pragma omp parallel { #pragma omp for { for(j=k; j < G->vexnum-1; j++) { if(TE[j].length < min) { min = TE[j].length; p = j; } } } } // 交换位置 temp = TE[p]; TE[p] = TE[k]; TE[k] = temp; v = TE[k].endvex; // 更新 #pragma omp parallel { #pragma omp for { for(j=k+1; j < G->vexnum-1; j++) { d = G->arcs[v-1][TE[j].endvex-1]; if(d < TE[j].length) { TE[j].fromvex = v; TE[j].length = d; } } } } } } } timeEnd = clock(); printf("The cost of the time is: %ldms\n", timeEnd-timeBegin); } void Output(Graph G[]) { int i; cout<<"最小生成树表示如下："<<endl; cout<<"\t顶点1\t顶点2\t代价"<<endl; for(i=0; i < G->vexnum-1; i++) { printf("\t%d\t%d\t%d\n", TE[i].fromvex, TE[i].endvex, TE[i].length); } } int main() { CreateUDN(G); Prim(G); Output(G); getchar(); return 0; }