最小生成树问题课程
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
在n个城市之间架设通信网络，只需保证连通即可，求出最经济的架设方法：
通信网络必定是双向的。因此，构造最小生成树的网一定是无向网。图中的顶点
数不超过30个，网中边的权值设成小于100的整数，可利用C语言提供的随即数产生。
图的存储结构的选取应和所选操作相适应。
1．利用克鲁斯卡尔算法求网的最小生成树。
2．输出生成树中各条边以及他们的权值。
3．学习掌握并熟练运用数据结构与C语言进行程序设计；
4．程序要求：操作方便灵活、界面友好。
5．文档要求：按要求撰写课程设计
报告
软件系统测试报告下载sgs报告如何下载关于路面塌陷情况报告535n,sgs报告怎么下载竣工报告下载
和设计总结。
1．《C程序设计（第二版）》，谭浩强，北京，清华大学出版社，1999. 2．《数据结构算法——Visual C++6.0程序集》，侯识忠 等著，中国水利水电
出版社，2005
3．《数据结构》（C语言版），严蔚敏，吴伟民 编著，清华大学出版社，2002 4．《C++程序设计教程》（第二版），钱能 著，清华大学出版社，2005
1 需求
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
a.建立一个图，其存储方式可以采用邻接矩阵形式，需要定义两个数组，一个存
储顶点，一个存储边，存储边的数组表明节点间的连通关系和边的权值；。
b.利用普里姆算法和克鲁斯卡尔算法求网的最小生成树。 c.按顺序输出生成树中各条边以及它们的权值。
2 概要设计
抽象数据类型(ADT)如下：
ADT Graph{
数据对象V：v是具有相同特性的数据元素的集合，称为顶点集。 数据关系R：R={VR}
VR={
|v,w属于v且p(v,w),(v,w)表示从v到w的弧，谓词p(v,w)定义了
弧的意义或信息}
基本操作：CreatGraph(&G,V,VR)；
初始条件：V是图的顶点集，VR是图中弧的集合。
操作结果：按V和VR的定义构造图G。
LocateVex(G, u)；
初始条件：图G存在,u和G中顶点有相同的特征。 操作结果：若G中存在顶点u，则返回该顶点在图中的位置；否则返回其他信息。
DestoryGraph(&u)；
初始条件：图G存在。
操作结果：销毁图G。
GetVex(G, v)；
初始条件：图G存在，v是图中某个顶点。
操作结果：返回v的值。
NextAdjVex(G, v, w)；
初始条件：图G存在，v是图中某个顶点，w是v的邻接顶点。 操作结果：返回v的（相对于w的）下一个邻接顶点。若w是v的最后一个邻接
点，则返回“空”。
BFSTraverse(G, Visit( ))；
初始条件：图G存在，Visit是顶点的应用函数。
操作结果：对图进行广度优先遍历。在遍历过程中对每个顶点调用函数Visit
一次且仅一次。一旦visit( )失败，则操作失败。}
存储结构
Typedef struct
{ int adj; int weight;
}AdjMatrix[MAX][MAX];
Typedef struct
{
djMatrix arc;
int vexnum, arcnum;
} MGraph;
流程
快递问题件怎么处理流程河南自建厂房流程下载关于规范招聘需求审批流程制作流程表下载邮件下载流程设计
图:
开 始
功能选择
1、建2、用3、用
立邻primkruska
接矩算法l算法
阵 求解最最
最小小生
生成成树
树
结 束
3 运行环境
硬件环境:Windows XP 软件环境：Microsoft Visual C++ 6.0
4 开发工具和编程语言
开发工具:Microsoft Visual C++ 6.0 编程语言: c语言 5详细设计
在该函数中主要有五段代码块，分别是主函数代码块、邻接矩阵定义模块代
码、创建链接矩阵模块代码、最小生成树Prim算法及代价模块代码与最小生成树kruskal算法及代价模块代码，五段代码块分别有着不同的作用，共同满足了
课题所需要实现的功能。
主函数模块代码
algraph gra; MGraph_L G; int i,d,g[20][20];
char a='a'; d=creatMGraph_L(G); vnode v;
cout<>s;
switch(s){
case 0: cout<<"邻接矩阵显示如下："<>y; if(y=='n') break; }
}
该主函数用一个循环语句，来执行其它的函数的功能。从键盘输入顶点数和
边数上限，再调用定义连接矩阵的函数，后输出创建连接矩阵的信息，再调用
creatMGraph（）函数，接着进入菜单，然后再选择输入一个数确定是要输出连
接矩阵还是最小生成树及代价，最后选择输入确定字母y或N确定是否继续。
邻接矩阵定义模块代码
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。
创建链接矩阵模块代码
int creatMGraph_L(MGraph_L &G)
{char v1,v2; int i,j,w;
cout<<"„„„„创建无向图（城市分布图）„„„„"<>G.vexnum>>G.arcnum;
for(i=0;i!=G.vexnum;++i)
{cout<<"输入顶点（城市）"<>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; }
for(int k=0;k!=G.arcnum;++k)
{cout<<"输入一条边依附的顶点（城市）和权（距离）:(a b 3)不包括
“()”"<>v1>>v2>>w; i=localvex(G,v1); j=localvex(G,v2);
G.arcs[i][j].adj=w; G.arcs[j][i].adj=w;}
cout<<"图G邻接矩阵创建成功！"<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<
#include
using namespace std;
#define int_max 10000
#define inf 9999
#define max 20
#define MAX 20
#define M 20
typedef struct ArcCell
{
int adj;
char *info;
}ArcCell,AdjMatrix[20][20];
typedef struct
{
char vexs[20];
AdjMatrix arcs;
int vexnum,arcnum;
}MGraph;
int localvex(MGraph G,char v) {
int i=0;
while(G.vexs[i]!=v)
{++i;}
return i;
}
void ljjzprint(MGraph G)
{ int i,j,n=0; printf("建立的邻接矩阵如下：\n"); printf("\n");
printf(" _____________________________________________\n");
for(i=0;i!=G.vexnum;i++)
{ for(j=0;j!=G.vexnum;j++)
{ if(j==0)printf(" ");
printf("%d",G.arcs[i][j].adj);printf(" ");n++;
if(n==G.vexnum){ printf("\n");n=0;} }
}
printf(" ______________________________________________\n");}
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.vexs[i]; }
for(i=0;i>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;} int visited[max]; int we;
typedef struct arcnode
{ int adjvex; struct arcnode *nextarc; char *info; }arcnode;
typedef struct vnode
{ char data; arcnode *firstarc; }vnode,adjlist;
typedef struct//图的定义 { adjlist vertices[max]; int vexnum, arcnum; int
kind; }algraph;
int prim(int g[][max],int n) //最小生成树PRIM算法
{
int lowcost[max], prevex[max];
int i,j,k,min;
int sum=0;
for(i=2;i<=n;i++)
{
lowcost[i]=g[1][i];
prevex[i]=1;
}
lowcost[1]=0;
for(i=2;i<=n;i++)
{
min=inf;
k=0;
for(j=2;j<=n;j++)
if((lowcost[j]arcnum,&D->vexnum);
for(i=1;i<=D->vexnum;i++)//初始化图
{
for(j=1;j<=D->vexnum; j++)
{
D->arc[i][j].adj=D->arc[j][i].adj=0;
}
}
for(i=1;i<=D->arcnum;i++)//输入边和权值
{
printf("\n请输入有边的2个顶点");
scanf("%d %d",&n,&m);
while(n<0||n>D->vexnum||m<0||n>D->vexnum)
{
printf("输入的数字不符合要求 请重新输入:");
scanf("%d%d",&n,&m);
}
D->arc[n][m].adj=D->arc[m][n].adj=1;
getchar();
printf("\n请输入%d与%d之间的权值:",n,m);
scanf("%d",&D->arc[n][m].weight);
}
printf("邻接矩阵为:\n");
for(i=1;i<=D->vexnum;i++)
{
for(j=1;j<=D->vexnum;j++)
{
printf("%d ",D->arc[i][j].adj);
}
printf("\n");
}
}
void sort(edge edges[],MGraphA *D)//对权值进行排序
{
int i, j;
for(i=1;iarcnum;i++)
{
for(j=i+1;j<=D->arcnum;j++)
{
if(edges[i].weight>edges[j].weight)
{
Swapn(edges, i, j);
}
}
}
printf("权排序之后的为:\n");
for(i=1;iarcnum;i++)
{
printf("<< %d, %d >> %d\n", edges[i].begin, edges[i].end,
edges[i].weight);
}
}
void Swapn(edge *edges,int i, int j)//交换权值 以及头和尾
{
int temp;
temp=edges[i].begin;
edges[i].begin=edges[j].begin;
edges[j].begin=temp;
temp=edges[i].end;
edges[i].end=edges[j].end;
edges[j].end=temp;
temp=edges[i].weight;
edges[i].weight=edges[j].weight;
edges[j].weight=temp; }
void MiniSpanTree(MGraphA *D)//生成最小生成树
{
int i,j,n,m,SUM=0;
int k=1;
int parent[M];
edge edges[M];
for(i=1;ivexnum;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<0)
{
f=parent[f];
}
return f;
}
void main()
{
algraph gra;
MGraph G;
MGraphA *D;
int i,d,m,g[20][20];
char a='a';
int s;
char y='y';
while(y='y')
{
printf(" „„„„最小生成树的求法„„„„
\n");
printf("
____________________________________________\n");
printf(" | 1.建立邻接矩阵(无向图)
|\n");
printf(" | 2.用prim算法求最小生成树(无向图)
|\n");
printf(" | 3.用kruskal算法求最小生成树
|\n");
printf(" |___________________________________________
|\n");
printf(" 请选择相应的菜单(1-3) :");
cin>>s;
switch(s)
{
case 1:
d=creatMGraph(G);
vnode v;
cout<>y;
if(y=='n')
break;
}
}
6 调试分析
1、问题一：求出图中的最小值
现象：求出的最小值是0
原因：图中没有连通的两个顶点之间的权值赋值为0
2、问题二：求最小生成树时，else语句需再调用一个函数
现象：对某些二叉树能求出最小生成树，但不能普遍适应
原因：对于找最小生成树边的各种可能没有考虑全面，代码才没有广泛的
适应性
3、问题三：两个顶点之间的边是否是最小生成树的边
现象：代码的功能不能分辨出是否是最小生成树的边 7 测试结果 原因：把简单的代码写的很复杂，从而杂乱无章出现错误。
将程序员录入后,让其运行。将会出现一个菜单的界面，执行各种操作均有
其对应的代码。要执行何种操作只需输入对应的指令即可进行，在每步操作后均
会有相应的提示。操作简单方便实用，下面即为一些操作的示意图。
运行程序后出界面，运行结果如图1所示。
图1 初界面
图中有1-3三个选项，可选取其中的一个选项进行操作。
选取选项1进行操作，运行结果如图2所示。
图2 建立邻接矩阵
依据提示，分别输入无向图的顶点个数与弧的个数，然后依次输入各个顶点
所对应的符号及与各个顶点相关联的弧与权值，存在邻接矩阵中。
若选取选项3，运行结果如图4所示。
图3 求的最小生成树
图中显示了求得的最小生成树所对应的边、权值与最小生成树的代价。
参考文献
[1] 边肇祺，模式识别（第二版），北京：清华大学出版社,1988，25～35 [2] 李永忠，几种小波变换的图像处理技术，西北民族学院学报（自然科学版），
2001.6,22（3），15～18
[3]《C程序设计（第三版）》，谭浩强，北京，清华大学出版社，2005. [4]《数据结构（C语言版）》，严蔚敏，吴伟民，清华大学出版。 [5]《C++实用教程（第一版）》，杨明军、董亚卓、汪黎，人民邮电出版社，2002.
心得
信息技术培训心得 下载关于七一讲话心得体会关于国企改革心得体会关于使用希沃白板的心得体会国培计划培训心得体会
体会
在朋友帮助和我的努力下，课程设计终于完成，由于我对数据结构和c语言不是很了解，有时忽略了一些关键的细节，使得在编写程序的过程中出现了一些
问题。对于打字有时粗心导致出现一些难以发现的小错误，在我的耐心，细致的
调试下最终使得程序能够运行，课程设计完满完工。
浙公网安备 33021202002483