摘 要

最小生成树是数据结构中图的一种重要应用，在图中对于n个顶点的连通网可以建立许多不同的生成树，最小生成树就是在所有生成树中总的权值最小的生成树。

本课程设计是以邻接矩阵作为图的存储结构,分别采用Prim和Kruskal算法求最小生成树。Kruskal算法和Prim算法是求最小生成树的常用算法它们分别适用于稠密图和稀疏图。最小生成树的应用非常的广，如矿井通风设计和改造最优化方面以及如何搭建最短的网络线缆, 构建造价最低的通讯网络等等一系列的应用 。

关键词：最小生成树，邻接矩阵，Kruskal算法，Prim算法

一、 引 言

《数据结构》是计算机科学与技术专业和信息管理与信息系统专业的必修课之一，是一门综合性的专业基础课。本课程较系统地介绍了软件设计中常用的数据结构以及相应的实现算法，如线性表、栈、队列、树和二叉树，图、检索和排序等，并对性能进行分析和比较，内容非常丰富。

本课程设计我们要解决的问题是图最小生成树问题。要用到图的先相关数据结构和求最小生成树的两种数据结构算法普里姆算法和克鲁斯卡尔算法，以及储存图的边和点的邻接矩阵。

本课程设计要解决的问题构造连通网的最小生成树 ,我们首先要做的是创建一个邻接矩阵，用以来存储图，然后我们要想好怎样利用普里姆算法和克鲁斯卡尔算法来构造最小生成树。把这两种算法写入主函数，调试好程序。最后写好报告。

二、设计目的与任务

2.1课程设计目的

本课程设计的目的是了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；提高综合运用所学的理论知识和方法独立分析和解决问题的能力；训练用系统的观点和软件开发一般规范进行软件开发。

2.2课程设计的任务

问题描述: 已知一个无向连通网表示n个城市以及城市间可能设置的通信线路，其中网的顶点表示城市，边表示两个城市之间的线路，赋于边上的权值表示相应的代价。对于n个点的连通网能建立许多不同的生成树，每一棵生成树都可以是一个通信网。我们要选择一棵生成树，使总的耗费最小。

三、设计方案

3.1需求分析

（1）建立一个图，其存储方式可以采用邻接矩阵形式或者邻接表；

（2）利用普利姆算法或者克鲁斯卡尔算法求出网的最小生成树；

（3）输入各城市的数目以及各个城市之间的距离。将城市之间的距离当做网 中各点之间的权值。按顺序输出生成树中各条边以及它们的权值。

3.2数据结构分析

构造最小生成树的方法：最初生成树为空，即没有一个结点和一条边，首先选择一个顶点作为生成树的根，然后每次从不在生成树中的边中选择一条权值尽可能小的边，为了保证加入到生成树中的边不会造成回路，与该边邻接的两个顶点必须一个已经在生成树中，一个则不在生成树中，若网中有n个顶点（这里考虑的网是一个连通无向图），则按这种条件选择n-1边就可以得到这个网的最小生成树了。详细的过程可以描述为：设置2个集合，U集合中的元素是在生成树中的结点，V-U集合中的元素是不在生成树中的顶点。首先选择一个作为生成树根结点的顶点，并将它放入U集合，然后在那些一端顶点在U集合中，而另一端顶点在V-U集合中的边中找一条权最小的边，并把这条边和那个不在U集合中的顶点加入到生成树中，即输出这条边，然后将其顶点添加到U集合中，重复这个操作n-1次。

3.2.1抽象数据类型(ADT)如下

ADT Graph

{

数据对象V：v是具有相同特性的数据元素的集合，称为顶点集。

数据关系R：R={VR}

VR={＜v,w＞|v,w属于v且p(v,w),(v,w)表示从v到w的弧，谓词p(v,w)定义了弧＜v,w＞的意义或信息}

3.2.2基本操作

(1)CreatGraph(&G,V,VR)；

初始条件：V是图的顶点集，VR是图中弧的集合。

操作结果：按V和VR的定义构造图G。

(2)LocateVex(G, u)；

初始条件：图G存在,u和G中顶点有相同的特征。

操作结果：若G中存在顶点u，则返回该顶点在图中的位置；否则返回其他信息。

(3)DestoryGraph(&u)；

初始条件：图G存在。

操作结果：销毁图G。

(4)GetVex(G, v)；

初始条件：图G存在，v是图中某个顶点。

操作结果：返回v的值。

(5)NextAdjVex(G, v, w)；

初始条件：图G存在，v是图中某个顶点，w是v的邻接顶点。

操作结果：返回v的（相对于w的）下一个邻接顶点。若w是v的最后一个邻接点，则返回“空”。

(6)BFSTraverse(G, Visit( ))；

初始条件：图G存在，Visit是顶点的应用函数。

操作结果：对图进行广度优先遍历。在遍历过程中对每个顶点调用函数Visit一次且仅一次。一旦visit( )失败，则操作失败。}

3.2.3存储结构

Typedef struct

{

int adj;

int weight;

}

AdjMatrix[MAX][MAX];

Typedef struct

{

djMatrix arc;

int vexnum, arcnum;

}

MGraph;

流程图，如下图所示：

图1 模块流程图

图2 算法流程图

3.3最小生成树的算法分析

在该函数中主要有五段代码块，分别是主函数代码块、邻接矩阵定义模块代码、创建链接矩阵模块代码、最小生成树Prim算法及代价模块代码与最小生成树kruskal算法及代价模块代码，五段代码块分别有着不同的作用，共同满足了课题所需要实现的功能。

3.3.2邻接矩阵定义模块代码

typedef struct ArcCell{

int adj; char *info;

}ArcCell,AdjMatrix[20][20];

typedef struct {

char vexs[20]; AdjMatrix arcs;

int vexnum,arcnum;

}MGraph_L;

int localvex(MGraph_L G,char v)

{ int i=0; while(G.vexs[i]!=v) { ++i;} return i;}

用typedef struct定义邻接矩阵，通过二维数组来存储邻接矩阵，并设定参数的最大值为20。

3.3.3创建邻接矩阵模块代码

int creatMGraph

(

MGraph &G

)

{

char v1,v2;

int i,j,w;

printf("建立邻接矩阵:\n");

printf("请输入图G顶点（城市）和弧（边）的个数:");

scanf("%d",&G.vexnum);

scanf("%d",&G.arcnum);

printf("输入所有顶点:");

for(i=0;i＜G.vexnum;++i)

{

cin＞＞G.vexs[i];

}

for(i=0;i＜G.vexnum;i++)

for(j=0;j＜G.vexnum;j++)

{

G.arcs[i][j].adj=int_max;

G.arcs[i][j].info=NULL;

}

printf("输入所有边及依附的顶点（城市）和权（距离）:\n");

for(int k=0;k＜G.arcnum;k++)

{

cin＞＞v1＞＞v2＞＞w;

i=localvex(G,v1);

j=localvex(G,v2);

G.arcs[i][j].adj=w;

G.arcs[j][i].adj=w;

}

ljjzprint(G);

printf("图G邻接矩阵创建成功！\n");

return G.vexnum;

}

该语句是从键盘输入顶点数和边数，输入顶点和权值，通过循环语句的调用，最后调用creatMGraph_L（）创建连接矩阵 。

3.3.5最小生成树kruskal算法及代价模块代码

void MiniSpanTree(MGraphA *D)//生成最小生成树

{

int i, j, n, m, SUM=0; int k = 1;

int parent[M]; edge edges[M];

for ( i = 1; i ＜ D-＞vexnum; i++)

{

for (j = i + 1; j ＜= D-＞vexnum; j++){ if (D-＞arc[i][j].adj == 1)

{

edges[k].begin = i; edges[k].end = j;

edges[k].weight = D-＞arc[i][j].weight; k++;}

}

}

sort(edges, D);

for (i = 1; i ＜= D-＞arcnum; i++)

{

parent[i] = 0;

}

printf("最小生成树为:\n");

for (i = 1; i ＜= D-＞arcnum; i++)//核心部分

{

n = Find(parent, edges[i].begin);

m = Find(parent, edges[i].end);

if (n != m){ parent[n] = m;

printf("＜＜ %d, %d ＞＞ %d\n",)

edges[i].begin,

edges[i].end,

edges[i].weight);

SUM=SUM+edges[i].weight;

}

}

cout＜＜"最少生成树的代价:";

cout＜＜SUM.

该语句运用一系列的循环语句来实现的，利用前面的创建好的链接矩阵，通过各边权值的比较，最后调用MiniSpanTree ()函数，实现最小生成树的生成，同时运用sum把最小生成树各边权值相加得到最小生成树的代价。

四、调试分析与体会

在我组的集体努力下，课程设计终于完成，由于我们对数据结构和c语言不是很了解，有时忽略了一些关键的细节，使得在编写程序的过程中出现了一些问题。对于打字有时粗心导致出现一些难以发现的小错误，在我们的耐心，细致的调试下最终使得程序能够运行，课程设计完满完工。

1、问题一：初次运行时出行错误

现象：无法运行，出现error

原因：打程序时出现有些单词漏打字母

2、问题二：求出图中的最小值

现象：求出的最小值是0

原因：图中没有连通的两个顶点之间的权值赋值为0

3、问题三：程序中kruskal需要重新输入数据生成邻接矩阵

现象：对已有的矩阵无法运算必须重新作计算

原因：kruskal算法重新调用了函数，不是对已有的矩阵作运算。

五、运行结果

将程序录入后,让其运行。将会出现一个菜单的界面，执行各种操作均有其对应的代码。要执行何种操作只需输入对应的指令即可进行，在每步操作后均会有相应的提示。操作简单方便实用，下面即为一些操作的示意图。

运行程序后出界面，运行结果如下图所示：

图3 初界面图与邻接矩阵的生成

图中有1-3三个选项，可选取其中的一个选项进行操作。选取选项1进行操作，运行结果如上图所示

图5 kruskal 算法输入

图6 kruskal 算法邻接矩阵的生成与求解

由图4、5、6可以看出虽然在运算的过程中，kruskal算法要重新生成矩阵，但对于同一网络图的最小生成树的求解答案是一样的，可以用来验证你所求的最小生成树是否正确。

图中显示了求得的最小生成树所对应的边、权值与最小生成树的权值之和。

此外为了验证此程序的正确性我们一共用了三组数据来进行试运行，以下是另外两组数据的运行过程与结果：

图7

图 8

图 9

图10

另一组数据：

图11

图12

图13

图14

六、结 论

经过我不懈的努力我们终于完成了本次课程设计，通过这次课程设计，我感觉到要真正做出一个程序并不很容易，但只要用心去做，总会有收获，特别是当我遇到一个问题，想办法去解决，最后终于找到方法时，心里的那份喜悦之情真是难以形容。编写程序中遇到问题再所难免，我遇到了一些或大或小的问题，但是不论问题大小都会导致程序不能运行，这就要求我们要既有耐心又要细心，仔细推敲程序，从出现问题的地方起，并联系前后程序，逐个排查，直到最终搞清为止。我们本次做的是图的最小生成树问题。通过本次课程设计我们发现我们对于C语言和数据结构还有很多地方不知道，今后需要努力学习。

七、参考文献

[1].严蔚敏. 数据结构（C语言版）[M]. 北京：清华大学出版社,1997.

[2].谭浩强. C程序设计（第三版）[M]. 北京：清华大学出版社，2005.1.

[3].二霍红卫算法设计与分析〔」西安西安电子科技大学出版社，2005.113-127.

[4].高一凡. 数据结构算法实现及解析[M ]. 西安:西安电子科技大学出版社, 2002

[5].Pascal之父Niklaus Wirth 《算法 + 数据结构 = 程序》 科学出版社 2001

 

第二篇：数据结构实验报告最小生成树

HUNAN UNIVERSITY

课程实习报告

题 目： 最小生成树

学生姓名：

学生学号：

专业班级：

指导老师：

完成日期：

1、需求分析

若要在n个城市之间建设通信网络，只需要架设n-1条线路即可。如何以最低的经济代价建设这个通信网，是一个网的最小生成树问题

2、概要设计

抽象数据类型

用数组将边的距离及权值进行存储并排序。

算法的基本思想

构造生成树的网一定是无向网。并设顶点数不超过30个，边权值为小于100的整数。

根据克鲁斯卡尔算法的特点，为便于选择选择权值小的边，存储结构不选用邻接矩阵和邻接表，而是可以用存储边（带权）的数组表示图。

程序的流程

程序由三个模块构成：

（1）从文件中读入图的信息。

（2）利用克鲁斯卡尔算法求网的最小生成树。

（3）以文本形式生成树中各条边以及他们的权值。

3、

4、详细设计

算法的具体步骤

先将用户的输入的顶点和边的数量，根据这些信息构建出图的结构，最后对边的权值进行排序。

输入和输出的格式

输入：

输入顶点和边的个数及顶点之间的权值。

输出：

输出最小生成树的序列。

5、测试结果

六、实验心得

实验的时候不是这个结果啊，可能是哪个环节出了错误，但是思想没有问题的，通过本次实验学会了用C++实现最小生成树。