haihongyuan.com
海量文库 文档专家
全站搜索:
您现在的位置:首页 > 幼儿教育 > 幼儿读物幼儿读物

数据结构课程设计-最小生成树

发布时间:2013-10-20 10:01:44  

数据结构

课程设计报告

设计题目:最小生成树

专业:xxxxxx 院系:计算机学院

姓名:xxxxxxxxx

学号:xxxxxx

时间:2013年10月7日

数据结构课程设计报告 最小生成树

目 录

一、设计目的……………………………………………………………….-2-

二、算法思想分析………………………………………………………-2-

1.算法思想………………………………………………………………..-3- 1)普里姆(Prim)算法思想……………………………………………………….-3-

2)克鲁斯卡尔(Kruskal)算法思想..........................................-3-

2. 系统采用的数据结构和算法………………………………-3-

三、算法的描述与实现……………………………………………….-4-

四、用户手册………………………………………………………………-7-

五、总结…………………………………………………………………….-10-

六、参考文献…………………………………………………………….-10-

七、附录(源代码)………………………………………………...-10-

- 1 -

数据结构课程设计报告 最小生成树

[摘要]选择一颗生成树,使之总的消费最少,也就是要构造连通网的最小代价生成树(简称为最小生成树)的问题,一颗生成树的代价就是树上各边的代价之和,构造最小生成树可以有多种算法,其中多

数算法利用了MST的性质。

关键词:最小生成树 连通图 普里姆算法 克鲁斯卡尔算法 MST

一、 设计目的

1. 了解并掌握数据结构与算法的设计方法,具备初步的独立分析和设计能力;

2. 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能;

3. 提高综合运用所学的理论知识和方法独立分析和解决问题的能力;

4. 训练用系统的观点和软件开发一般规范进行软件开发,培养软件工作者所应具备的科学的工作方法和作风。

二、 算法思想分析

该设计的要求是在n个城市之间建设网络,不仅要保证连

通,还要求是最经济的架设方法。根据克鲁斯卡尔和普里姆算法的不同之处,该程序将城市个数大于十个时应用普里姆算法求最小生成树,而城市个数小于十个时则应用克鲁斯卡尔进行计算。

- 2 -

数据结构课程设计报告 最小生成树

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;

- 3 -

数据结构课程设计报告 最小生成树

Typedef int AdjType;

Typedef struct edgeElem edgeset[MaxVertexNum];

struct edgeElem

{int fromvex;//头顶点

int endvex;//尾顶点

int weight;//权

};

Typedef struct

{int n;//图的顶点个数

AdjType acrs[MAXVEX][MAXVEX];//边信息

}GraphMatrix;

Typedef struct

{int start_vex,stop_vex;//边的起点和终点 AdjType weight;//边的权

}Edge;

Edge mst[5];

2) 算法

Great_adjmatrix();

Great_adjmatrix2();

Kruskal();

out_edgeaet();

prim();

三、 算法的描述与实现

- 4 -

数据结构课程设计报告 最小生成树

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<pgraph->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<pgraph->n-1;i++)//共n-1条边

{minweight = MAX;

min = i;

for(j=i;j<pgraph->n-1;j++)

//从所有(vx,vy)(vx∈U,vy∈V-U)中选出最短的边 if(mst[j].weight<minweight)

{minweight = mst[j].weight;

min = j;

}

//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<pgraph->n-1;j++)

- 5 -

数据结构课程设计报告 最小生成树

{vy=mst[j].stop_vex;weight=pgraph->arcs[vx][vy]; if(weight<mst[j].weight)

{mst[j].weight=weight;

mst[j].start_vex = vx;

}

}

}

}

3. 普里姆算法(Prim):

void prim(adjmatrix GA,edgeset MST,int n) //利用prim算法从0点出发求图的最小生成树 {int i,j,t,k,w,min,m;

struct edgeElem x;

for(i=0;i<n;i++)

if(i>0) //从0点连接其余顶点

{MST[i-1].fromvex=0;

MST[i-1].endvex=i;

MST[i-1].weight=GA[0][i];

}

for(k=1;k<n;k++)

{min=MaxValue;

m=k-1;

for(j=k-1;j<n-1;j++)

if(MST[j].weight<min)

{min=MST[j].weight;

M=j;

}//选择从0点出发权值最小的边

x=MST[k-1];MST[k-1]=MST[m];MST[m]=x;//交换位置

- 6 -

数据结构课程设计报告 最小生成树

j=MST[k-1].endvex;//定位于权值最小边的尾顶点 for(i=k;i<n-1;i++)//选取轻边

{t=MST[i].endvex;

w=GA[j][t];

if(w<MST[i].weight)

{MST[i].weight=w;

MST[i].fromvex=j;

}

}

}

}

4. out_edgeset()功能为显示最小生成树。

四、 用户手册

1.运行程序,得到如下窗口:

2.输入顶点数,选择算法:

1)当输入的顶点数小于10时,选择Kruskal算法,如下图

- 7 -

数据结构课程设计报告 最小生成树

2)当输入的顶点数大于10时,选择Prim算法,如下图

- 8 -

数据结构课程设计报告 最小生成树

五、总结

该程序实现了在n个城市之间建设网络,既保证了连通性,也成为了最经济的架设方法。程序中应用了普里姆算法和克鲁斯卡尔算法,实现了矩阵的输出以及最小生成树的输出。不过,该程序仍有不足之处,图的输入数据过大,易出错,不易返回,仍需完善。

六、参考文献

[1]《数据结构程序设计题典》 李春葆编 清华大学出版社

[2]《数据结构(C语言版)》 严蔚敏 吴伟民编 清华大学出版社

[3]《数据结构课程设计》 苏仕华编 机械工业出版社

七、附录:(源代码)

#include<stdio.h>

#include<stdlib.h>

#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];

- 9 -

数据结构课程设计报告 最小生成树

struct edgeElem

{int fromvex;//头顶点

int endvex;//尾顶点

int weight;//权

};

typedef struct {

int n; /* 图的顶点个数 */ /*VexType vexs[MAXVEX]; 顶点信息 */ AdjType arcs[MAXVEX][MAXVEX]; /* 边信息 */ } GraphMatrix;

typedef struct{

int start_vex, stop_vex; /* 边的起点和终点 */ AdjType weight; /* 边的权 */ } Edge;Edge mst[5];

void Creat_adjmatrix(vexlist GV,adjmatrix GA,int n,int e) { int i,j,k,w;

printf("输入%d个顶点序号(0--n-1):",n);

for(i=0;i<n;i++) //建立顶点表

scanf("%d",&GV[i]);//读入顶点信息

for(i=0;i<n;i++)//建立边表

for(j=0;j<n;j++)//初始化边表

if(i==j) GA[i][j]=0;

else GA[i][j]=MaxValue;

printf("输入%d条无向带权边(序号 序号 权值):\n",e); for(k=0;k<e;k++)//设置边表

- 10 -

数据结构课程设计报告 最小生成树

{ 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;i++) //建立顶点表

{scanf("%d",&GV[i]);//读入顶点信息

if(GV[i]>=m)

{ printf("您输入的序号有误,请输入0到%d-1之间的数,请重新输入。\n",m);

scanf("%d",&GV[i]);}

}

for(i=0;i<m;i++)//建立边表

for(j=0;j<m;j++)//初始化边表

GA[i][j]=MaxValue;

printf("请输入有多少条边。\n");

scanf("%d",&e);

printf("输入%d条无向带权边(序号 序号 权值):\n",e); for(k=0;k<e;k++)//设置边表

{ scanf("%d%d%d",&i,&j,&w);

GA[i][j]=GA[j][i]=w;//对称

}

printf("您输入的图的存贮为下面表,如果不可达则用1000表示。\n");

- 11 -

数据结构课程设计报告 最小生成树

graph.n =m;

for(x=0;x<m;x++)

{for(y=0;y<m;y++) {

graph.arcs[x][y]=GA[x][y];

printf("%-4d ",graph.arcs[x][y]);}

printf("\n");

}

}

void kruskal(GraphMatrix * pgraph, Edge mst[]) {

int i, j, min, vx, vy;

int weight, minweight; Edge edge;

for (i = 0; i < pgraph->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 < pgraph->n-1; i++) { /* 共n-1条边 */ minweight = MAX; min = i;

for (j = i; j < pgraph->n-1; j++)/* 从所有边(vx,vy)(vx∈U,vy∈V-U)中选出最短的边 */

if(mst[j].weight < minweight) {

minweight = mst[j].weight;

min = j;

}

- 12 -

数据结构课程设计报告 最小生成树

/* 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 < pgraph->n-1; j++) { /* 调整mst[i+1]到mst[n-1] */

vy=mst[j].stop_vex; weight = pgraph->arcs[vx][vy]; if (weight < mst[j].weight) {

mst[j].weight = weight;

mst[j].start_vex = vx;

}

}

}

}

void out_edgeset(edgeset MST,int e)//显示最小生成树

{ int k;

printf("最小的消耗路线为\n");

for(k=0;k<e;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点出发求图的最小生成树

- 13 -

数据结构课程设计报告 最小生成树

{ int i,j,t,k,w,min,m;

struct edgeElem x;

for(i=0;i<n;i++)

if(i>0)//从0点连接其余顶点

{ MST[i-1].fromvex=0;

MST[i-1].endvex=i;

MST[i-1].weight=GA[0][i];

}

for(k=1;k<n;k++)

{ min=MaxValue;

m=k-1;

for(j=k-1;j<n-1;j++)

if(MST[j].weight<min) {min=MST[j].weight;m=j;}//选择从0点出发权值最小的边

x=MST[k-1];MST[k-1]=MST[m];MST[m]=x;//交换位置

j=MST[k-1].endvex;//定位于权值最小边的尾顶点

for(i=k;i<n-1;i++)//选取轻边

{ t=MST[i].endvex;w=GA[j][t];

if(w<MST[i].weight)

{ MST[i].weight=w;

MST[i].fromvex=j;

}

}

}

}

void main()

{

int n,e,i;

- 14 -

数据结构课程设计报告 最小生成树

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 < graph.n-1; i++)

- 15 -

数据结构课程设计报告 最小生成树

printf("(%d %d %d)\n", mst[i].start_vex,

mst[i].stop_vex, mst[i].weight);//输出最小生成树

}

printf("谢谢使用!\n");

printf("继续?输入1继续,输入0退出。\n");//方便用户重复使用 scanf("%d",&a);

getchar();

system("cls");//清屏语句

}while(a==1);

}

- 16 -

网站首页网站地图 站长统计
All rights reserved Powered by 海文库
copyright ©right 2010-2011。
文档资料库内容来自网络,如有侵犯请联系客服。zhit326@126.com