最小生成树算法

上传Word文档，包含代码、运行结果截图

Prim算法 运行

的

结

果

如

下

图

代码如下

#include #include

#define MAXCOST 0x7fffffff #define MAX 100

int cpppa[MAX][MAX];

int Prim(int cpppa[][MAX], int n) { int i, j, min, minid, sum = 0; int nb[MAX]; int zuidi[MAX];

for (i = 2; i <= n; i++) {

zuidi[i] = cpppa[1][i]; nb[i] = 1;

}

nb[1] = 0;

for (i = 2; i <= n; i++) { minid = 0;

min = MAXCOST;

for (j = 2; j <= n; j++) {

if (zuidi[j] < min && zuidi[j] != 0) {

min = zuidi[j]; minid = j; } }

printf(\"%c - %c : %d\\n\ sum += min; zuidi[minid] = 0; for (j = 2; j <= n; j++) {

if (cpppa[minid][j] < zuidi[j]) {

zuidi[j] = cpppa[minid][j]; nb[j] = minid; } } }

return sum; }

int main()

{ char chx, chy; int x, y, cost; int i, j, k, m, n;

scanf(\"%d%d\ getchar();

for (i = 1; i <= m; i++) {

for (j = 1; j <= m; j++) {

cpppa[i][j] = MAXCOST; } }

}

for (k = 0; k < n; k++) {

scanf(\"%c %c %d\ getchar();

i = chx - 'A' + 1; j = chy - 'A' + 1; cpppa[i][j] = cost; cpppa[j][i] = cost; }

cost = Prim(cpppa, m); printf(\"Total:%d\\n\return 0;