文档介绍：word文档
word文档
1 / 22
word文档
摘 要
设计了一个用C/C++编写程序实现克鲁斯卡尔最小生成树算法，该程序操作简单，界面清晰，易于为用户所承受。
关键词：克鲁斯卡尔，邻接矩阵，最小生成树，vc++。
word文档
word文档
1 / 22
word文档
目 录
1 课题描述1
2 问题分析和任务定义2
3 逻辑设计3
4 详细设计4
5 程序编码10
6 程序调试与测试16
7 结果分析18
8 总结19
参考文献20
word文档
word文档
20 / 22
word文档
1课题描述
用C/C++编写程序实现克鲁斯卡尔最小生成树算法。假设要在n个城市之间建立通讯联络网，如此连通n个城市只需要n-1条线路。这是我们设计一个最小生成树的程序用来算出最节省经费的前提下建立这个通信站。
word文档
word文档
1 / 22
word文档
2问题分析和任务定义
假设连通网N=〔V,{E}〕,如此令最小生成树的初始状态为只有n个顶点而无边的非连通图T=(V,{})，图中每个顶点自成一个连通分量。在E中选择代价最小的边，假如该边依附的顶点落在T中不同的连通分量上，如此将此边参加到T中，否如此舍去此边而选择下一条代价最小的边。依次类推，直到T中所有顶点都在同一连通分量上为止。
word文档
word文档
2 / 22
word文档
3逻辑设计
设计思想： 采用邻接矩阵来存储图，然后采用克鲁斯卡尔算法求出最小生成树。
结构体定义
函数模块二
〔求最小生成树〕
克鲁斯卡尔算法
函数模块一
〔图的创建〕
采用邻接矩阵做存储结构
主函数引用函数模块一、二，实现算法设计
1〕．定义结构体。
2〕．采用邻接矩阵做存储结构创建图〔函数模块一〕。
3〕．采用克鲁斯卡尔算法求出该图的最小生成树〔函数模块二〕。
4〕．在主函数里面分别调用以上各个函数，最终实现设计目的。
word文档
word文档
3 / 22
word文档
4详细设计
．程序结构
·函数CreateMGraph
用来实现图的创建，以与图的相关信息的存储。图的存储采用邻接矩阵存储结构。
·函数minitree_KRUSKAL
用来求图的最小生成树。图的最小生成树有普利姆算法和克鲁斯卡尔算法可以实现，本段代码使用的是克鲁斯卡尔算法，这也是此题所要求使用的。
·各个函数间的联系
先调用函数CreateMGraph实现图的创建，然后调用函数minitree_KRUSKAL求出该图的最小生成树
．设计说明
·在开始的时候添加一些限制条件方便函数的功能实现例如：
#define MaxVertexNum 100 //最大顶点个数
#define QueueSize 30
#define M 30
·模块一：图的创建
·结构体定义为：
typedef struct
{
VertexType vexs[MaxVertexNum];//顶点表
Link edges[MaxVertexNum][MaxVertexNum]; //图中当前的相连接的两个顶点
int n,e;//图中当前的顶点数和边数
}MGraph;
·函数定义为：
MGraph CreateMGraph()
{
word文档
word文档
4 / 22
word文档
MGraph G;
int i,j,k,ch3;
char ch1,ch2;
printf("请输入该图的顶点数和边数:\n");
scanf("%d,%d",&(),&());
printf("请输入该图的顶点信息:\n");
for(i=1;i<=;i++)
{
getchar();
scanf("%c",&([i]));
}
for(i=1;i<=;i++)
for(j=1;j<=;j++)
[i][j].w=0;
printf("请输入该图每条边对应的两个顶点的名称:\n");
for(k=1;k<=;k++)
{
scanf("%c",&ch1);
printf("请输入第%d条边的顶点序号：",k);