prim算法

#include <stdio.h>
#define N 20
#define TRUE 1
#define INF 32766
#define INFIN 32767

typedef struct {
	int vexnum, arcnum;
	char vexs[N];
	int arcs[N][N];
}
MGraph;

void createMGraph_w(MGraph *g);
void prim(MGraph *g, int u);

//创建带权无向图的邻接矩阵
void createMGraph_w(MGraph *g) {
	char v;
	int i = 0, j, w;
	int arc = 0, vex = 0;
	for (int a = 0; a < N; a++)
		for (int b = 0; b < N; b++)
			g->arcs[a][b] = INFIN;
	for (int c = 0; c < N; c++)
		g->arcs[c][c] = 0;
	v = getchar();
	while (v != '#') {
		g->vexs[i] = v;
		v = getchar();
		i++;
		vex++;
	}
	getchar(); // 跳过换行符

	g->vexnum = vex;

	scanf("%d,%d,%d", &i, &j, &w);
	while (i != -1 && j != -1 && w != -1) {
		g->arcs[i][j] = w;
		arc++;
		scanf("%d,%d,%d", &i, &j, &w);
	}
	g->arcnum = arc;
}


//最小生成树Prime算法
void prim(MGraph *g, int u) {
	int lowcost[N], closest[N], i, j, k, min;
	for (i = 0; i < g->vexnum; i++) {
		closest[i] = u;
		lowcost[i] = g->arcs[u][i];
	}
	lowcost[u] = 0;
	for (i = 1; i < g->vexnum; i++) {
		min = INFIN;
		for (j = 0; j < g->vexnum; j++) {
			if (lowcost[j] != 0 && lowcost[j] < min) {
				min = lowcost[j];
				k = j;
			}
		}
		printf("(%c,%c)--%d\n", g->vexs[closest[k]], g->vexs[k], lowcost[k]);
		lowcost[k] = 0;
		for (j = 0; j < g->vexnum; j++) {
			if (g->arcs[k][j] < lowcost[j] && g->arcs[k][j] != 0) {
				lowcost[j] = g->arcs[k][j];
				closest[j] = k;
			}
		}
	}
}

int main() {
	MGraph ga;
	int i;
	createMGraph_w(&ga);
	scanf("%d", &i);
	prim(&ga, i);
	return 0;
}