最小耗费生成树Prim算法实验报告.doc

学生实验报告
学院: 软件与通信工程学院
课程名称: 算法设计与分析
专业班级: 软件工程142班
姓名: 周平
学号: 0143987
学生实验报告
学生姓名
周平
学号
0143987
同组人:无
实验项目
最小耗费生成树Prim算法
□必修☑选修
□演示性实验□验证性实验☑操作性实验□综合性实验
实验地点
W101
实验仪器台号
K03
指导教师
尹爱华
实验日期及节次
5-234
一、实验综述
实现贪心法的下列六个算法之一:
1、可切割背包问题
2、单源点最短路径求解算法——Dijkstra算法
3、Dijkstra算法的改进版
4、最小耗费生成树Kruskal算法
5、最小耗费生成树Prim算法
6、最小耗费生成树Prim算法的改进版
要求与说明:
1、各人独立完成,
2、实验报告要求有:算法说明与描述、代码、数据集合(各算法1 要求达到百、千级)。
3、实验报告要有2-3个截图,包括导入数据、重要中间过程、最后结果等;
4、额外完成所实现的算法,每完成一个加 1 分;
5、程序要求用 C 语言完成,每个实验报告的代码都会被测试,对运行环境有特别要求的需要专门说明,否则,程序测试不通过责任自负;
6、实验报告都有步骤分,但是,程序测试结果与实验报告结果不相符的,将被加重扣分;
7、严禁抄袭——代码重复度超过90%者视作抄袭,抄袭者以 0 分记,可以对评审提出质疑。疑。
2、实验仪器、设备或软件
1、个人电脑
2、Microsoft Visual Studio 2015
二、实验过程(实验步骤、记录、数据、分析)
实验代码如下:
#include <>
#include <>
#define MAX 100
#define MAXCOST 0x7fffffff
int graph[MAX][MAX];
int Prim(int graph[][MAX], int n)
{
/* lowcost[i]记录以i为终点的边的最小权值,当lowcost[i]=0时表示终点i加入生成树*/
int lowcost[MAX];
/* mst[i]记录对应lowcost[i]的起点,当mst[i]=0时表示起点i加入生成树*/
int mst[MAX];
int i, j, min, minid, sum = 0;
/* 默认选择1号节点加入生成树,从2号节点开始初始化*/
for (i = 2; i <= n; i++)
{
/* 最短距离初始化为其他节点到1号节点的距离*/
lowcost[i] = graph[1][i];
/* 标记所有节点的起点皆为默认的1号节点*/
mst[i] = 1;
}
/* 标记1号节点加入生成树*/
mst[1] = 0;
/* n个节点至少需要n-1条边构成最小生成树*/
for (i = 2; i <= n; i++)
{
min = MAXCOST;
minid = 0;
/* 找满足条件的最小权值边的节点minid */
for (j = 2; j <= n; j++)
{
/* 边权