实验3-2-最小生成树问题.doc

课程题目： 数据结构实验 学院：理学院 班级：信计1102 姓名：王策 学号 ●实验题目：图的应用 ●实验内容：最小生成树 ●实验目的：掌握图的概念及工作原理，运用其原理完成上述实验题目中的内容。 ●实验要求：为了使学生更好的掌握与理解课堂上老师所讲的概念与原理，实验前每个学生要认真预习所做的实验内容及编写源程序伪码（写在纸上及盘中均可）以便在实验课中完成老师所布置的实验内容。 ●实验学时：2学时 ●实验原理 若要在n个城市之间建设通信网络,只需架设n-1条线路即可。以最低的经济代价建设这个通信网，求最小生成树，利用Prim或Kruskal算法,输出生成树中各条边以及其权值,设顶点不超过30个。 源程序代码 #includestdio.h #define MAXVEX 30 #define MAXCOST 1000 void prim(int c[MAXVEX][MAXVEX],int n) /*己知图的顶点为{1,2,...,n},c[i][j]和c[j][i]为边(i,j)的权,打印最小生成树 的每条边*/ { int i,j,k,min,lowcost[MAXVEX],closest[MAXVEX]; for (i=2;i=n;i++) /*从顶点1开始*/ { lowcost[i]=c[1][i]; closest[i]=1; } closest[1]=0; for (i=2;i=n;i++) /*从U之外求离U中某一顶点最近的顶点*/ { min=MAXCOST; j=1;k=i; while (j=n) { if (lowcost[j]min closest[j]!=0) { min=lowcost[j]; k=j; } j++; } printf((%d,%d)\n,closest[k],k); /*打印边*/ closest[k]=0; /*k加入到U中*/ for (j=2;j=n;j++) if (closest[j]!=0 c[k][j]lowcost[j]) { lowcost[j]=c[k][j]; closest[j]=k; } } } /*void get_in(int mx[MAXVEX][MAXVEX]) { int i,A,B,C; for(i=1;i=10;i++) { scanf(%d,C); scanf((%d %d),A B); mx[A][B]=mx[A][B]; mx[A][B]=C; } printf(mx[%d][%d]=%d,A B C); } */ main() { int n=7,i,j,mx[MAXVEX][MAXVEX]; for (i=0;i=n;i++) for (j=0;j=n;j++) mx[i][j]=MAXCOST; mx[1][2]=50; mx[1][3]=60; mx[2][4]=65; mx[2][5]=40; mx[3][4]=52; mx[3][7]=45; mx[4][5]=50; mx[5][6]=70; mx[4][6]=30; mx[4][7]=42; printf(最小生成树边集:\n ); prim(mx,n); } 五 运行结果