浙江大学城市学院实验报告
课程名称 数据结构与算法
实验项目名称 实验八 图的最小生成树
学生姓名 专业班级 学号
实验成绩 指导老师（签名） 日期
一. 实验目的和要求
1. 掌握图的最小生成树的概念。
2. 掌握生成最小生成树的Prim算法（用邻接矩阵表示图）。
二. 实验内容
1、 编写用邻接矩阵表示无向带权图时图的基本操作的实现函数，主要包括：①初始化邻接矩阵表示的无向带权图 void InitMatrix(adjmatrix G); ②建立邻接矩阵表示的无向带权图 void CreateMatrix(adjmatrix G, int n) （即通过输入图的每条边建立图的邻接矩阵）; ③输出邻接矩阵表示的无向带权图void PrintMatrix(adjmatrix G, int n) （即输出图的每条边）。把邻接矩阵的结构定义以及这些基本操作实现函数存放在头文件Graph1.h中。
2、 编写生成最小生成树的Prim算法函数 void Prim(adjmatrix G, edgset CT, int n) 以及输出边集数组的函数 void PrintEdge(edgeset CT, int n)。
3、 编写测试程序（即主函数），通过调用上述函数首先建立并输出无向带权图，然后生成最小生成树并输出（即输出边集）。
要求：把边集数组的结构定义、Prim算法函数、输出边集数组的函数PrintEdge以及主函数存放在文件test8.cpp中。
测试数据如下：
4、 填写实验报告，实验报告文件取名为report8.doc。
5、上传实验报告文件report8.doc与源程序文件test8.cpp及Graph1.h到Ftp服务器上自己的文件夹下。
三. 函数的功能说明及算法思路
包括每个函数的功能说明，及一些重要函数的算法实现思路
void InitMatrix(adjmatrix GA,int k) //初始化图的邻接矩阵
void CreateMaxrix(adjmatrix GA,int n,char* s,int k1,int k2){ //根据一个图的边集生成图的邻接矩阵k1==0 为无向图否则为有向图，k2==0则为无权图否则为有权图s字符串用来保存一个图的边集，n为图的顶点数
void PrintMaxtrix(adjmatrix GA,int n,int k1,int k2){ //输出图的二元组表示
//输出用邻接矩阵表示一个图的顶点集和边集
void Prim(adjmatrix GA,edgeset CT,int n) //最小生成树的Prim算法
void PrintEdge(edgeset CT, int n) //输出边集数组的函数
四. 实验结果与分析
包括运行结果截图等
五. 心得体会
记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等。
【附录----源程序】
Test9.h
#include<iostream.h>
#include<stdio.h>
#include<strstrea.h>
#include<string.h>
const int MaxVertexNum = 20; //大于图的最大顶点数
const int MaxEdgeNum = 400; //大于图的最大边数
typedef int WeightType; //大于边的权值类型
const WeightType MaxValue = 10000;//大于图的所有权值之和
typedef int adjmatrix[MaxVertexNum][MaxVertexNum];//定义存储邻接矩阵的数组类型
typedef struct {
int fromvex;
int endvex;
WeightType weight;
}edge;
typedef edge edgeset[MaxEdgeNum];
#include"Graph1.h"
void Prim(adjmatrix GA,edgeset CT,int n){
int i,j,k,min,t,m,w;
for(i = 0;i < n-1;i++){
CT[i].fromvex = 0;
CT[i].endvex = i+1;
CT[i].weight = GA[0][i+1];
}
for(k = 1;k<n;k++){
min = MaxValue;
m = k-1;
for(j = k-1;j<n-1;j++)
if(CT[j].weight < min){
min = CT[j].weight;
m = j;
}
edge temp = CT[k-1];
CT[k-1] = CT[m];
CT[m] = temp;
j = CT[k-1].endvex;
for(i = k;i<n-1;i++){
t = CT[i].endvex;
w = GA[j][t];
if(w<CT[i].weight){
CT[i].weight = w;
CT[i].fromvex = j;
}
}
}
}
void PrintEdge(edgeset CT, int n){
int i;
cout<<"V={";
for(i = 0;i < n-2;i++)
cout<<i<<',';
cout<<i+1<<'}'<<endl;
cout<<"E={";
for(i = 0;i < n-2;i++){
cout<<'('<<CT[i].fromvex<<','<<CT[i].endvex;
cout<<')'<<CT[i].weight<<',';
}
cout<<'('<<CT[i].fromvex<<','<<CT[i].endvex;
cout<<')';
cout<<'}'<<endl;
}
void main(){
int n;
adjmatrix GA;
InitMatrix(GA,1);
cout<<"输入顶点数n:"<<endl;
cin>>n;
char *a = new char[100];
strcpy(a,"{<0,1>8,<0,3>5,<1,3>3,<1,4>10,<1,2>12,<2,4>6,<2,5>2,<4,5>9,");
strcat(a,"<3,5>7,<3,6>15)");
CreateMaxrix(GA,n,a,0,1);
cout<<"输出图"<<endl;
PrintMaxtrix(GA,n,0,1);
edgeset ct;
Prim(GA,ct,n);
cout<<"输出边集"<<endl;
PrintEdge(ct,n);
}
Graph1.h
void InitMatrix(adjmatrix GA,int k){ //初始化图的邻接矩阵
//k==0 为无权图 k!=0 为有权图
int i,j;
for(i = 0;i < MaxVertexNum;i++)
for(j = 0;j < MaxVertexNum;j++)
if(i == j)
GA[i][j] = 0;
else if(k)
GA[i][j] = MaxValue;
else
GA[i][j] = 0;
}
void CreateMaxrix(adjmatrix GA,int n,char* s,int k1,int k2){ //根据一个图的边集生成图的邻接矩阵
//k1==0 为无向图否则为有向图，k2==0则为无权图否则为有权图
//s字符串用来保存一个图的边集，n为图的顶点数
istrstream sin(s);
char c1,c2,c3;
int i,j;
WeightType w; //用于保存一条边的权值
sin>>c1;
if(k1 == 0 && k2 == 0) //建立无向无权图
do{
sin>>c1>>i>>c2>>j>>c3;
GA[i][j] = GA[j][i] = 1;
sin>>c1;
if(c1 == ')')
break;
}while(1);
else if(k1 == 0 && k2 != 0) //建立无向有权图
do{
sin>>c1>>i>>c2>>j>>c3>>w;
GA[i][j] = GA[j][i] = w;
sin>>c1;
if(c1 == ')')
break;
}while(1);
else if(k1 != 0 && k2 == 0) //建立有向无权图
do{
sin>>c1>>i>>c2>>j>>c3;
GA[i][j] = 1;
sin>>c1;
if(c1 == ')')
break;
}while(1);
}
void PrintMaxtrix(adjmatrix GA,int n,int k1,int k2){ //输出图的二元组表示
//输出用邻接矩阵表示一个图的顶点集和边集
int i,j;
cout<<"V={";
for(i = 0;i < n-1;i++)
cout<<i<<',';
cout<<n-1<<'}'<<endl;
cout<<"E={";
if(k2 == 0){
for(i = 0;i < n;i++)
for(j = 0;j < n;j++)
if(GA[i][j] == 1)
if(k1 == 0){
if(i < j)
cout<<'('<<i<<','<<j<<')'<<',';
}
else
cout<<'<'<<i<<','<<j<<'>'<<',';
}
else{
for(i = 0;i < n;i++)
for(j = 0;j < n;j++)
if(GA[i][j] != 0 && GA[i][j] != MaxValue)
if(k1 == 0){
if(i < j)
cout<<'('<<i<<','<<j<<')'<<GA[i][j]<<',';
}
else
cout<<'<'<<i<<','<<j<<'>'<<GA[i][j]<<',';
}
cout<<"}"<<endl;
}
第二篇：实验8 最小生成树
电子信息学院
实验报告书
课程名： 数据结构
题 目： 最小生成树
实验类别 设计
班 级： BX1008
学 号： 101003150809
姓 名： 胡欢
20##年 11 月 28 日
1、实验题目
（1) 复习图的存储方法和图的遍历方法；
（2) 进一步掌握图的非线性特点、递归特点和动态特点；
（3) 掌握最小生成树的求解算法。
2、实验内容
（1） 用Prim算法求最小生成树。
（2） 输入网的二维矩阵，输出最小生成树。
3、实验要求
（1） 利用C（C++）语言完成算法设计和程序设计。
（2） 上机调试通过实验程序，并检验程序运行的正确性。
（3） 输入数据，并求最小生成树。
（4） 给出具体算法分析，包括时间复杂度和空间复杂度等。
（5） 撰写实验报告（把输入实验数据及运行结果用抓图的形式粘贴到实验报告上）。
4、实验步骤与源程序
⑴ 实验步骤
1） 首先，为了使程序更为通俗易懂，我们在程序开头，初始化形成n-1条边的生成树。
2） 初始化矩阵，编写满足条件的无向图的邻接矩阵。要注意的是，在初始化矩阵的时候全部元素设为无穷大。
3） 根据题意，编写程序。用Prim算法求最小生成树。
⑵ 源代码
#include <stdio.h>
#define inf 9999
#define max 40
void prim(int g[][max],int n) // prim的函数
{
int lowcost[max],closest[max];
int i,j,k,min;
for(i=2;i<=n;i++) // n个顶点，n-1条边
{ lowcost[i]=g[1][i]; // 初始化
closest[i]=1; // 顶点未加入到最小生成树中
}
lowcost[1]=0; // 标志顶点1加入U集合
for(i=2;i<=n;i++) // 形成n-1条边的生成树
{
min=inf;
k=0;
for(j=2;j<=n;j++) // 寻找满足边的一个顶点在U,另一个顶点在V的最小边
if((lowcost[j]<min)&&(lowcost[j]!=0))
{
min=lowcost[j];
k=j;
}
printf("(%d,%d)%d\t",closest[k],k,min);
lowcost[k]=0; // 顶点k加入U
for(j=2;j<=n;j++) // 修改由顶点k到其他顶点边的权值
if(g[k][j]<lowcost[j])
{ lowcost[j]=g[k][j];
closest[j]=k;
}
printf("\n");
}
}
int adjg(int g[][max]) // 建立无向图
{
int n,e,i,j,k,v1,v2,weight;
printf("输入顶点个数，边的条数：");
scanf("%d,%d",&n,&e);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
g[i][j]=inf; // 初始化矩阵，全部元素设为无穷大
for(k=1;k<=e;k++)
{
printf("输入第%d条边的起点，终点，权值:",k);
scanf("%d,%d,%d",&v1,&v2,&weight);
g[v1][v2]=weight;
g[v2][v1]=weight;
}
return(n);
}
void prg(int g[][max],int n) // 输出无向图的邻接矩阵
{
int i,j;
for(i=0;i<=n;i++)
printf("%d\t",i);
for(i=1;i<=n;i++)
{
printf("\n%d\t",i);
for(j=1;j<=n;j++)
printf((g[i][j]==inf)?"\t":"%d\t",g[i][j]);
}
printf("\n");
}
void main()
{
int g[max][max],n;
n=adjg(g);
printf("输入无向图的邻接矩阵:\n");
prg(g,n);
printf("最小生成树的构造:\n");
prim(g,n);
}
5、测试数据与实验结果
图5 测试数据及实验结果
6、结果分析与实验体会
由截图可知用Prim算法求最小生成树和输入网的二维矩阵，输出最小生成树功能基本实现。通过该实验，本人对求最小生成树的prim算法有了更深刻的理解，对用数组存放边的权值和基于数组的指针操作有了更深的认识，在刚开始调试的时候总输出乱码，经过上网查阅才了解到字符数组与C 风格的 字符串是有区别的,后者是以NULL结尾的，前者必须将最后一个单元赋值NULL即0才能更正确地用C的字符函数.
通过此次实验，对于编写最小生成树算法的选择明白了很多。不同的算法有各自的优势，但对于题目的要求则应选择合适的算法。