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

学生实验报告
学院: 国际经贸学院
课程名称: 数据结构
专业班级: 09电子商务
姓名:
学号:
学生实验报告
(经管类专业用)
学生姓名

学号

同组人
实验项目
最小生成树
■必修□选修
□演示性实验□验证性实验■操作性实验□综合性实验
实验地点

实验仪器台号
指导教师

实验日期及节次
1、2节
一、实验目的及要求:
1、目的
学习普里姆算法,并练习编写相关程序。
2、内容及要求
学习并掌握有关生成树的相关知识,了解构造最小生成树的三条基本准则:
必须只使用此流通图中的边来构造最小生成树;
必须使用且仅使用(n-1)条边来连接图中的n个顶点;
不能使用产生回路的边;
二、仪器用具:
仪器名称
规格/型号
数量
备注
计算机
1
有网络环境
C语言
1
三、实验方法与步骤:
编写一个程序,对于下面所示的无向带权图G,采用普里姆算法输出从顶点0出发的最小生成树。
无向带权图G
0
1
2
3
5
4
3
8
3
7
6
1
5
5
5
9
2)编写MAIN函数;
3)运行并判断结果;
4)整理并完成实验报告;
5)总结实验,提出建议。
四、实验结果与数据处理:
⑴实验代码
#include <>
#include ""
#define INF 32767
extern void DispMat(MGraph);
void prim(MGraph g,int v)
{
int lowcost[MAXV],min,n=;
int closest[MAXV],i,j,k;
for (i=0;i<n;i++)
{
lowcost[i]=[v][i];
closest[i]=v;
}
for (i=1;i<n;i++)
{
min=INF;
for (j=0;j<n;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;j<n;j++)
if ([k][j]!=0 && [k][j]<lowcost[j])
{
lowcost[j]=[k][j];closest[j]=k;
}
}
}
void main()
{
int i,j,u=3;
MGraph g;
int A[MAXV][11];
=6;=10;
for (i