实验五：采用普里姆算法求最小生成树
C代码
1 #include<stdio.h> 2 #define MAXV 20 3 #define INF 32767 4 typedef struct 5 { 6 int edges[MAXV][MAXV]; 7 int n; 8 int e; 9 } MatGraph; 10 11 void CreateMat(MatGraph &g, int A[MAXV][MAXV], int n, int e) 12 { 13 for (int i = 0; i < n; ++i) 14 for (int j = 0; j < n; ++j) 15 g.edges[i][j] = A[i][j]; 16 g.n = n; 17 g.e = e; 18 } 19 20 void Prim(MatGraph g, int v) 21 { 22 int lowcost[MAXV], closest[MAXV], k; 23 int min; 24 for (int i = 0; i < g.n; ++i) 25 { 26 lowcost[i] = g.edges[v][i]; 27 closest[i] = v; 28 } 29 for (int i = 0; i < g.n - 1; ++i) 30 { 31 min = INF; 32 for (int j = 0; j < g.n; ++j) 33 if (lowcost[j] != 0 && lowcost[j] < min) 34 { 35 min = lowcost[j]; 36 k = j; 37 } 38 printf("(%d, %d)的权为：%d \n", closest[k], k, min); 39 lowcost[k] = 0; 40 for (int j = 0; j < g.n; ++j) 41 if (g.edges[k][j] < lowcost[j]) 42 { 43 lowcost[j] = g.edges[k][j]; 44 closest[j] = k; 45 } 46 } 47 } 48 49 int main() 50 { 51 MatGraph g; 52 int A[MAXV][MAXV] = { { 0, 5, 8, 7, INF, 3 }, 53 { 5, 0, 4, INF, INF, INF }, 54 { 8, 4, 0, 5, INF, 9 }, 55 { 7, INF, 5, 0, 5, 6 }, 56 { INF, INF, INF, 5, 0, 1 }, 57 { 3, INF, 9 ,6, 1, 0 } }; 58 int n = 6, e = 10; 59 CreateMat(g, A, n, e); 60 Prim(g, 0); 61 return 0; 62 }