prim算法程序

#include \"stdio.h\" #include \"stdlib.h\" #define M 100 #define MAX 10000 #define TRUE 1 #define FALSE 0 typedef struct graph{ int arcs[M][M]; int vexnum; }Graph;

typedef int VertexType;

struct treeedge{VertexType adjvex; // U集中的顶点序号 int lowcost; // 边的权值

};

int mininum(struct treeedge closedge[],int n) { int min=MAX; int k=-1,i; for (i=0;iif (closedge[i].lowcost!=0&& closedge[i].lowcostk=i; } return k; }

void prim(Graph G,VertexType k) { int i,j; struct treeedge closedge[M];

for ( j=0; jif (j!=k) {closedge[j].adjvex=k;

closedge[j].lowcost=G.arcs[k][j]; };

closedge[k].lowcost = 0; // 初始，U＝{k} for (i=0; i{k=mininum(closedge,G.vexnum); // 求出加入生成树的下一个顶点 if (k!=-1){

printf(\"edge:(%d,%d)\\n\",closedge[k].adjvex, k); // 输出生成树上一条边

closedge[k].lowcost = 0; // k顶点并入U集

for (j=0; jif (G.arcs[k][j] < closedge[j].lowcost&& closedge[j].lowcost!=0)

{closedge[j].adjvex=k;

closedge[j].lowcost=G.arcs[k][j]; }

}

} }

void main() { Graph G; int i,j;

printf(\"input number of node\\n\"); scanf(\"%d\",&G.vexnum); printf(\"input data of Graph\\n\"); for (i=0;ifor (j=0;jscanf(\"%d\",&G.arcs[i][j]);

printf(\"output the prim tree\\n\"); prim(G,0); }