最小生成树的普里姆算法课设(4)

int i; int w,p; w=INFINITY; for(i=1;i<=vnum;i++)

if(cl[i].lowcost!=0&&cl[i].lowcost

void MiniSpanTree_PRIM(Graph *G,int u) {/* 从第u个顶点出发构造图G的最小生成树 */ ClosEdge closedge; int i,j,k,n=0,a=0;

printf(\最小代价生成树:\\n\

for(j=1;j<=G->vexnum;j++) /* 辅助数组初始化 */ if(j!=u)

{closedge[j].adjvex=u;

closedge[j].lowcost=G->arcs[u][j]; }

closedge[u].lowcost=0; /* 初始，U={u} */

for(i=1;ivexnum;i++) /* 选择其余的G->vexnum-1个顶点 */ {k=minimum(closedge,G->vexnum); /* 求出生成树的下一个顶点 */

printf(\ %d\\n\/* 输出生成树的边及其权值 */

n=n+closedge[k].lowcost;

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

for(j=1;j<=G->vexnum;j++) /* 新顶点并入U后，修改辅助数组*/ if(G->arcs[k][j]

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

void example() {

12

}a=a+n;printf(\最小权值为:%d\\n\

/* ------------------程序解说---------------------------- */ printf(\本程序将演示构造图的最小代价生成树。\\n\

printf(\首先输入图的顶点数和弧数\\n格式：顶点数，弧数；例如:4,4\\n\ printf(\接着输入各条弧(弧尾,弧头)和弧的权值。\\n\

printf(\格式:顶点1,顶点2,权值；例如\\n1,2,1\\n1,3,2\\n2,4,3\\n3,4,4\\n\ printf(\程序将会构造该图的最小代价生成树。\\n\

printf(\并显示该最小生成树。\\n<1--2> 1\\n<1--3> 2\\n<2--4> 3\\n最小权值为:6\\n\ printf(\请继续选择:\

/* ------------------------------------------------------ */ } void put()

{Graph G; /* 采用邻接矩阵结构的图 */ char j='y'; int u;

while(j!='N'&&j!='n') {

CreateGraph(&G); /* 生成邻接矩阵结构的图 */ while(j!='N'&&j!='n') {

printf(\从哪一顶点开始:\

scanf(\ /* 输入普里姆算法中的起始顶点 */ MiniSpanTree_PRIM(&G,u); /* 普里姆算法求最小生成树 */

printf(\要继续从别的点进行构造最小代价生成树吗?(Y/N)\ fflush(stdin); /*清除缓冲区*/

scanf(\

}

printf(\最小代价生成树构造完毕，继续进行吗?(Y/N)\ fflush(stdin); /*清除缓冲区*/ scanf(\

if(j=='N'||j=='n') printf(\请继续选择:\

} }

void main() {

13

int k,i=0;

printf(\普里姆算法实现最小生成树***************\\n\

printf(\ 1.构造最小代价生成树\\n\printf(\ 2.查看帮助示例\\n\printf(\ 3.退出系统\\n\

printf(\

printf(\请选择:\

for(;k!=-1;) {

switch(scanf(\ {

case 1:put();break;

case 2:example();break;

case 3:printf(\谢谢使用!\\n\

default:printf(\输入有误!\\n请继续选择:\ }

} }

14

5 程序测试

运行以上程序，得到程序主界面，选择1，输入相关数据，得到如图5. 1所示的运行界面：

图5. 1 最小生成树运行界面

15

选择查看帮助示例得到如图5. 2所示运行界面:

图5. 2 示例帮助

运行程序，当用户选择有误，提示异常，得到如图5. 3所示运行结果:

图5. 3 错误警告

16