数据结构-实验报告最小生成树.doc

（封面） 学 生 实 验 报 告 学 院： 国际经贸学院 课程名称： 数据结构 专业班级： 09电子商务 姓 名： 学 号： 学生实验报告 （经管类专业用） 学生姓名 学号 同组人 实验项目 最小生成树 ■必修 □选修 □演示性实验 □验证性实验 ■操作性实验 □综合性实验 实验地点 实验仪器台号 指导教师 实验日期及节次 1、2节 一、实验目的及要求： 1、目的 学习普里姆算法，并练习编写相关程序。 2、内容及要求 学习并掌握有关生成树的相关知识，了解构造最小生成树的三条基本准则： 必须只使用此流通图中的边来构造最小生成树； 必须使用且仅使用（n-1)条边来连接图中的n个顶点； 不能使用产生回路的边； 二、仪器用具： 仪器名称 规格/型号 数量 备注 计算机 1 有网络环境 C语言 1 三、实验方法与步骤: 编写一个程序，对于下面所示的无向带权图G，采用普里姆算法输出从顶点0出发的最小生成树。 无向带权图G 2）编写MAIN函数； 3）运行并判断结果； 4）整理并完成实验报告； 5）总结实验，提出建议。 四、实验结果与数据处理： ⑴实验代码 #include stdio.h #include graph.h #define INF 32767 extern void DispMat(MGraph); void prim(MGraph g,int v) { int lowcost[MAXV],min,n=g.vexnum; int closest[MAXV],i,j,k; for (i=0;in;i++) { lowcost[i]=g.edges[v][i]; closest[i]=v; } for (i=1;in;i++) { min=INF; for (j=0;jn;j++) if (lowcost[j]!=0 lowcost[j]min) { min=lowcost[j];k=j; } printf( 边(%d,%d)权为:%d\n,closest[k],k,min); lowcost[k]=0; for (j=0;jn;j++) if (g.edges[k][j]!=0 g.edges[k][j]lowcost[j]) { lowcost[j]=g.edges[k][j];closest[j]=k; } } } void main() { int i,j,u=3; MGraph g; int A[MAXV][11]; g.vexnum=6;g.arcnum=10; for (i=0;ig.vexnum;i++) for (j=0;jg.vexnum;j++) A[i][j]=INF; A[0][1]=5;A[0][2]=8;A[0][3]=7;A[0][5]=3; A[1][2]=4; A[2][3]=5;A[2][5]=9; A[3][4]=5; A[4][5]=1; for (i=0;ig.vexnum;i++) for (j=0;jg.vexnum;j++) A[j][i]=A[i][j]; for (i=0;ig.vexnum;i++) for (j=0;jg.vexnum;j++) g.edges[i][j]=A[i][j]; printf(\n); printf(图G的邻接矩阵:\n); DispMat(g); printf(\n); printf(普里姆算法求解结果:\n); prim(g,0); printf(\n); } ⑵运行结果 五、讨论与结论 六、指导教师评语及成绩： 评语：指导教师依据学生的实际报告内容，用简练语言给出本次实验报告的评价和价值 成绩： 指导教师签名： 批阅日期： 0 1 2 3 5 4 3 8 3 7 6 1 5 5 5 9