您好,欢迎来到爱够旅游网。
搜索
您的当前位置:首页prim算法程序

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); }

因篇幅问题不能全部显示,请点此查看更多更全内容

Copyright © 2019- igbc.cn 版权所有 湘ICP备2023023988号-5

违法及侵权请联系:TEL:199 1889 7713 E-MAIL:2724546146@qq.com

本站由北京市万商天勤律师事务所王兴未律师提供法律服务