数据结构课程设计最小生成树_数据结构课程设计树
数据结构课程设计最小生成树由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“数据结构课程设计树”。
数据结构 课程设计报告
设计题目：最小生成树
专业：xxxxxx 院系：计算机学院 姓名：xxxxxxxxx 学号：xxxxxx
时间：2013年10月7日
数据结构课程设计报告 最小生成树
目 录
一、设计目的……………………………………………………………….-2-
二、算法思想分析………………………………………………………-2-1.算法思想………………………………………………………………..-3-1）普里姆（Prim）算法思想……………………………………………………….-3-2）克鲁斯卡尔（Kruskal）算法思想..........................................-3-2.系统采用的数据结构和算法………………………………-3-
三、算法的描述与实现……………………………………………….-4-
四、用户手册………………………………………………………………-7-
五、总结…………………………………………………………………….-10-
六、参考文献…………………………………………………………….-10-
七、附录（源代码）………………………………………………...-10-
数据结构课程设计报告 最小生成树
1.算法思想
1)普里姆（Prim）算法思想
a)选择从0节点开始，并选择0节点相关联的最小权值边，将与这条边相关联的另一顶点出列；
b)在出列的节点中相关联的所有边中选择一条不与另一个已出列的节点相关联的权值最小的边，并将该边相关联的节点出列；
c)重复b)直到所有的节点出列。2)克鲁斯卡尔（Kruskal）算法思想
为了使生成树上总的权值之和最小，应该使每一条边上的权值尽可能的小，所以应从权值最小的边选起，直至选出n-1条不能构成回路的权值最小的边位置。
具体做法如下：首先构造一个含n个顶点的森林，然后按权值从小到大从连通图中选择不使森林中产生回路的边加入到森林中去，直至该森林变成一棵树为止，这棵树便是连通图的最小生成树。
由于生成树上不允许有回路，因此并非每一条居当前最小的边都可选。从生成树的构造过程可见，初始态为n个顶点分属n棵树，互不连通，每加入一条边，就将两棵树合并为一棵树，在同一棵树上的两个顶点之间自然相连通，由此判别当前权值最小边是否可取只要判别它的两个顶点是否在同一棵树上即可。
2.系统采用的数据结构和算法 1)数据结构
Typedef int Vertextype;Typedef int adimatrix[MaxVertexNum][MaxVertexNum];Typedef int Vertextype vexlist[MaxVertexNum];Typedef int VexType;
数据结构课程设计报告 最小生成树
1.Great_adjmatrix()和Great_adjmatrix2()是两种建立图的方法；
2.克鲁斯卡尔算法（Kruskal）：
Void kruskal(GraphMatrix * pgraph,Edge mst[]){int i,j,min,vx,vy;int weight,minweight;Edge edge;for(i=0;i
n-1;i++){mst[i].start_vex = 0;Mst[i].stop_vex = i+1;Mst[i].weight = pgraph->arcs[0][i+1];} for(i=0;i
n-1;i++)//共n-1条边 {minweight = MAX;min = i;for(j=i;j
n-1;j++)//从所有（vx,vy）（vx∈U,vy∈V-U）中选出最短的边 if(mst[j].weight
for(j=i+1;j
n-1;j++)
数据结构课程设计报告 最小生成树
j=MST[k-1].endvex;//定位于权值最小边的尾顶点 for(i=k;i
4.out_edgeset()功能为显示最小生成树。
四、用户手册
1.运行程序，得到如下窗口：
2.输入顶点数，选择算法：
1）当输入的顶点数小于10时，选择Kruskal算法，如下图
数据结构课程设计报告 最小生成树
五、总结
该程序实现了在n个城市之间建设网络，既保证了连通性，也成为了最经济的架设方法。程序中应用了普里姆算法和克鲁斯卡尔算法，实现了矩阵的输出以及最小生成树的输出。不过，该程序仍有不足之处，图的输入数据过大，易出错，不易返回，仍需完善。
六、参考文献
[1]《数据结构程序设计题典》 李春葆编 清华大学出版社 [2]《数据结构（C语言版）》 严蔚敏 吴伟民编 清华大学出版社 [3]《数据结构课程设计》 苏仕华编 机械工业出版社
七、附录：（源代码）
#include #include #define MaxVertexNum 12 #define MaxEdgeNum 20 #define MaxValue 1000 #define MAXVEX 6 #define MAX 1e+8 typedef int Vertextype;typedef int adjmatrix[MaxVertexNum][MaxVertexNum];typedef Vertextype vexlist[MaxVertexNum];typedef int VexType;typedef int AdjType;typedef struct edgeElem edgeset[MaxVertexNum];
数据结构课程设计报告 最小生成树
{ scanf(“%d%d%d”,&i,&j,&w);GA[i][j]=GA[j][i]=w;//对称 } }
void Creat_adjmatrix2(vexlist GV,adjmatrix GA,int m,int e,GraphMatrix &graph){ int i,j,k,w,x,y;
printf(“输入%d个顶点序号(0-m-1)，序号从0开始。”,m);for(i=0;i=m){ printf(“您输入的序号有误，请输入0到%d-1之间的数，请重新输入。n”,m);scanf(“%d”,&GV[i]);} } for(i=0;i
GA[i][j]=MaxValue;printf(“请输入有多少条边。n”);scanf(“%d”,&e);printf(“输入%d条无向带权边（序号 序号 权值）：n”,e);for(k=0;k
数据结构课程设计报告 最小生成树
/* mst[min]是最短的边(vx,vy)(vx∈U, vy∈V-U)，将mst[min]加入最小生成树 */ edge = mst[min];mst[min] = mst[i];mst[i] = edge;vx = mst[i].stop_vex;/* vx为刚加入最小生成树的顶点的下标 */
for(j = i+1;j n-1;j++){ /* 调整mst[i+1]到mst[n-1] */ vy=mst[j].stop_vex;weight = pgraph->arcs[vx][vy];if(weight
void out_edgeset(edgeset MST,int e)//显示最小生成树 { int k;printf(“最小的消耗路线为n”);for(k=0;k
printf(“(%d %d %d)n”,MST[k].fromvex,MST[k].endvex,MST[k].weight);}
void prim(adjmatrix GA,edgeset MST,int n)//利用prim算法从0点出发求图的最小生成树数据结构课程设计报告 最小生成树
int a;system(“color 71”);//改变屏幕颜色
printf(“ ┏━━━━━━━━━━━━━━━━━━━━━━━━━┓n”);printf(“ ┃㊣ 必做题：最小生成树 ㊣┃n”);printf(“ ┃ 姓名：xxxx ┃n”);printf(“ ┃ 学号：xxxxxxxxx ┃n”);printf(“ ┗━━━━━━━━━━━━━━━━━━━━━━━━━┛n”);vexlist GV;//顶点表 adjmatrix GA;//边表 edgeset MST;//最小生成树 do{ printf(“输入图的顶点数n，我们将根据您输入的数据大小选择合适的算法。n”);scanf(“%d”,&n);if(n>=10)//大于10用prim算法来实现，否则kruskal算法来实现 { printf(“用prim算法从0点出发求图的最小生成树为：n”);printf(“请输入图的边数。n”);canf(“%d”,&e);Creat_adjmatrix(GV, GA, n, e);//创建图 prim(GA,MST,n);//生成最小生成树
out_edgeset(MST, n-1);//输出最小生成树 } else{ printf(“用kcuskal算法的最小生成树为：n”);GraphMatrix graph;//定义一个结构体来表示存储结构 Creat_adjmatrix2(GV,GA,n,e,graph);//创建图 kruskal(&graph,mst);//生成最小生成树 rintf(“最小的消耗路线为n”);for(i = 0;i
