实验八 图的最小生成树

课程名称 数据结构与算法 实验项目名称 实验八 图的最小生成树 实验成绩 指导老师（签名 ） 日期

一. 实验目的和要求

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中。 测试数据如下：

0 5 8 3

1 3 15 12

2 7 10 6

6 2

4 5 9

4、 填写实验报告，实验报告文件取名为report8.doc。

1

5、上传实验报告文件report8.doc与源程序文件test8.cpp及Graph1.h到Ftp服务器上自己的文件夹下。

三. 函数的功能说明及算法思路

函数：void InitMatrix(adjmatrix GA)

功能：初始化邻接矩阵表示的无向带权图

函数：void CreateMatrix(adjmatrix GA,int n) 功能：建立邻接矩阵表示的无向带权图

函数：void PrintMatrix(adjmatrix GA,int n) 功能：输出邻接矩阵表示的无向带权图

函数：void Prim(adjmatrix GA,edgeset CT,int n) 功能：生成最小生成树

思路：设从连通带权图G = { V, E }中的某一顶点 u0 出发；选择与它关联的具有最小权值的边，将其顶点加入到生成树的顶点集合U中；以后每一步从一个顶点在U中，而另一个顶点在V-U中的各条边中选择权值最小的边,把该顶点加入到集合U中；如此继续下去，直到图中的所有顶点都加入到生成树顶点集合U中为止。

函数：void PrintEdge(edgeset CT,int n) 功能：输出边集数组

四. 实验结果与分析

2

五. 心得体会

【附录----源程序】 test8.cpp

#include #include #include #include\"Graph1.h\"

void main() {

adjmatrix GA; edgeset CT; int n;

InitMatrix(GA);

cout<<\"输入图的顶点数目：\"<>n;

cout<<\"输入图的边：\"<cout<<\"\\n输出邻接矩阵表示的无向带权图\"<cout<<\"\\n用Prim算法生成最小生成树\"<3

PrintEdge(CT,n); }

Graph1.h

const int MaxVertexNum=10; const int MaxEdgeNum=100; const int MaxValue=1000;

typedef int WeightType;

typedef char verlist[MaxVertexNum];

typedef int adjmatrix[MaxVertexNum][MaxVertexNum];

typedef struct{ int fromvex; int endvex;

WeightType weight; }edge;

typedef edge edgeset[MaxEdgeNum];

//初始化邻接矩阵表示的无向带权图 void InitMatrix(adjmatrix GA) {

int i,j;

for(i=0;iGA[i][j]=0; else

GA[i][j]=MaxValue; }

//建立邻接矩阵表示的无向带权图 void CreateMatrix(adjmatrix GA,int n) {

char c1,c2,c3; int i,j;

WeightType w; cin>>c1; do{

cin>>c1>>i>>c2>>j>>c3>>w; GA[i][j]=GA[j][i]=w; cin>>c1; if(c1=='}')

4

break; }while(c1==','); }

//输出邻接矩阵表示的无向带权图 void PrintMatrix(adjmatrix GA,int n) {

int i,j;

for(i=0;iif(GA[i][j]==MaxValue) cout<<\" ∞|\"; else

cout<cout<//生成最小生成树

void Prim(adjmatrix GA,edgeset CT,int n) {

//利用普利姆算法从顶点v0出发求出用邻接矩阵GA表示的图的 //最小生成树，最小生成树得到边集存于数组CT中 int i,j,k,min,t,m,w;

//给CT赋初值，对应第0次的LW值 for(i=0;iCT[i].weight=GA[0][i+1]; }

//进行n-1次循坏，每次求出最小生成树中的第k条边 for(k=1;k//从CT[k-1]~CT[n-2](即LW)中查找最短边CT[m] min=MaxValue; m=k-1;

for(j=k-1;jif(CT[j].weight//把最短边对调到第k-1下标位置 edge temp=CT[k-1];

5

CT[k-1]=CT[m]; CT[m]=temp;

//把心并入最小生成树T中的顶点序号赋给j j=CT[k-1].endvex;

//修改LW中的有关边，使T中到T外的每一个顶点各保持 //一条目前为止最短的边 for(i=k;iif(w}//内 for end }//外 for end }

//输出边集数组

void PrintEdge(edgeset CT,int n) {

int i;

for(i=0;icout<<'<'<'; cout<6