最小生成树问题

实习六

一，实验题目：最小生成树问题

二，实验目的：掌握图的基本概念，利用原理解决设计问题的能力，根据具体问题选取存储结构的能力。

若要在n 个城市之间建设通信网络, 只需架设n-1条线路即可。以最低的经济代价建设这个通信网，求最小生成树，利用Prim 或Kruskal 算法, 输出生成树中各条边以及其权值, 设顶点不超过30个。

三，程序功能层次图：

四，运行结果

五，小结

在做这个程序的时候，虽然遇到一些问题，但最后都被我解决， 自信心上得到比较大的提升，这也是这次实践最大的收获。同时，知识上的收获也是不可忽视的，亲手解决问题的过程也是很好的学习过程，并且积累了一些经验，相信会为以后的学习发展带来非常积极的帮助。 源代码：

#include

#include

#define MaxVertexNum 12

#define MaxEdgeNum 20

#define MaxValue 1000

typedef int Vertextype;

typedef int adjmatrix[MaxVertexNum][MaxVertexNum];

typedef Vertextype vexlist[MaxVertexNum];

int visited[MaxVertexNum]={0};

struct edgeElem

{int fromvex;

int endvex;

int weight;

};

typedef struct edgeElem edgeset[MaxVertexNum];

void Creat_adjmatrix(vexlist GV,adjmatrix GA,int n,int e)

{int i,j,k,w;

printf("输入%d个顶点数据",n);

for(i=0;i

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

for(i=0;i

for(j=0;j

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

else GA[i][j]=MaxValue;

printf("输入%d条无向带权边",e);

for(k=0;k

{

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

GA[i][j]=GA[j][i]=w;

}

}

void output_edgeset(edgeset GE,int e)

{int k;

for(k=0;k

printf("From %d To %d: %d\n",GE[k].fromvex,GE[k].endvex,GE[k].weight); printf("\n");

}

void prim(adjmatrix GA,edgeset CT,int a,int n)

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

struct edgeElem x;

for(i=0;i

if(i

{CT[i].fromvex=a;

CT[i].endvex=i;

CT[i].weight=GA[a][i];

}

else if(i>a)

{CT[i-1].fromvex=a;

CT[i-1].endvex=i;

CT[i-1].weight=GA[a][i];

}

for(k=1;k

{

min=MaxValue;

m=k-1;

for(j=k-1;j

if(CT[j].weight

x=CT[k-1];CT[k-1]=CT[m];CT[m]=x;

j=CT[k-1].endvex;

for(i=k;i

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

if(w

{CT[i].weight=w;

CT[i].fromvex=j;

}

}

}

}

void main()

{int n,e;

vexlist GV;

adjmatrix GA;

edgeset GE;

printf("输入图的顶点数和边数：");

scanf("%d%d",&n,&e);

Creat_adjmatrix( GV, GA, n, e);

printf("利用prim 算法从0点出发求图的最小生成树：\n");

prim(GA,GE,0,n);

output_edgeset( GE, n-1);

getch();

}

#include

#include

#define MaxVertexNum 12

#define MaxEdgeNum 20

#define MaxValue 1000

typedef int Vertextype;

typedef int adjmatrix[MaxVertexNum][MaxVertexNum];

typedef Vertextype vexlist[MaxVertexNum];

int visited[MaxVertexNum]={0};

struct edgeElem

{int fromvex;

int endvex;

int weight;

};

typedef struct edgeElem edgeset[MaxVertexNum];

void Creat_adjmatrix(vexlist GV,adjmatrix GA,int n,int e)

{int i,j,k,w;

printf("ÊäÈë%d·ö¶¤µãÊù¾Ý",n);

for(i=0;i

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

for(i=0;i

for(j=0;j

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

else GA[i][j]=MaxValue;

printf("ÊäÈë%dÌõÎÞÏò´÷Ȩ±ß",e);

for(k=0;k

{

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

GA[i][j]=GA[j][i]=w;

}

}

void output_edgeset(edgeset GE,int e)

{int k;

for(k=0;k

printf("From %d To %d: %d\n",GE[k].fromvex,GE[k].endvex,GE[k].weight); printf("\n");

}

void prim(adjmatrix GA,edgeset CT,int a,int n)

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

struct edgeElem x;

for(i=0;i

if(i

{CT[i].fromvex=a;

CT[i].endvex=i;

CT[i].weight=GA[a][i];

}

else if(i>a)

{CT[i-1].fromvex=a;

CT[i-1].endvex=i;

CT[i-1].weight=GA[a][i];

}

for(k=1;k

{

min=MaxValue;

m=k-1;

for(j=k-1;j

if(CT[j].weight

j=CT[k-1].endvex;

for(i=k;i

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

if(w

{CT[i].weight=w;

CT[i].fromvex=j;

}

}

}

}

void main()

{int n,e;

vexlist GV;

adjmatrix GA;

edgeset GE;

printf("ÊäÈëͼµÄ¶¤µãÊùºÍ±ßÊù£º");

scanf("%d,%d",&n,&e);

Creat_adjmatrix( GV, GA, n, e);

printf("ÀøÓÃprimËã·¨´Ó0µã³ö·¢ÇóͼµÄ×îСÉú³ÉÊô£º\n"); prim(GA,GE,0,n);

output_edgeset( GE, n-1);

getch();

}

实习六

一，实验题目：最小生成树问题

二，实验目的：掌握图的基本概念，利用原理解决设计问题的能力，根据具体问题选取存储结构的能力。

若要在n 个城市之间建设通信网络, 只需架设n-1条线路即可。以最低的经济代价建设这个通信网，求最小生成树，利用Prim 或Kruskal 算法, 输出生成树中各条边以及其权值, 设顶点不超过30个。

三，程序功能层次图：

四，运行结果

五，小结

在做这个程序的时候，虽然遇到一些问题，但最后都被我解决， 自信心上得到比较大的提升，这也是这次实践最大的收获。同时，知识上的收获也是不可忽视的，亲手解决问题的过程也是很好的学习过程，并且积累了一些经验，相信会为以后的学习发展带来非常积极的帮助。 源代码：

#include

#include

#define MaxVertexNum 12

#define MaxEdgeNum 20

#define MaxValue 1000

typedef int Vertextype;

typedef int adjmatrix[MaxVertexNum][MaxVertexNum];

typedef Vertextype vexlist[MaxVertexNum];

int visited[MaxVertexNum]={0};

struct edgeElem

{int fromvex;

int endvex;

int weight;

};

typedef struct edgeElem edgeset[MaxVertexNum];

void Creat_adjmatrix(vexlist GV,adjmatrix GA,int n,int e)

{int i,j,k,w;

printf("输入%d个顶点数据",n);

for(i=0;i

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

for(i=0;i

for(j=0;j

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

else GA[i][j]=MaxValue;

printf("输入%d条无向带权边",e);

for(k=0;k

{

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

GA[i][j]=GA[j][i]=w;

}

}

void output_edgeset(edgeset GE,int e)

{int k;

for(k=0;k

printf("From %d To %d: %d\n",GE[k].fromvex,GE[k].endvex,GE[k].weight); printf("\n");

}

void prim(adjmatrix GA,edgeset CT,int a,int n)

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

struct edgeElem x;

for(i=0;i

if(i

{CT[i].fromvex=a;

CT[i].endvex=i;

CT[i].weight=GA[a][i];

}

else if(i>a)

{CT[i-1].fromvex=a;

CT[i-1].endvex=i;

CT[i-1].weight=GA[a][i];

}

for(k=1;k

{

min=MaxValue;

m=k-1;

for(j=k-1;j

if(CT[j].weight

x=CT[k-1];CT[k-1]=CT[m];CT[m]=x;

j=CT[k-1].endvex;

for(i=k;i

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

if(w

{CT[i].weight=w;

CT[i].fromvex=j;

}

}

}

}

void main()

{int n,e;

vexlist GV;

adjmatrix GA;

edgeset GE;

printf("输入图的顶点数和边数：");

scanf("%d%d",&n,&e);

Creat_adjmatrix( GV, GA, n, e);

printf("利用prim 算法从0点出发求图的最小生成树：\n");

prim(GA,GE,0,n);

output_edgeset( GE, n-1);

getch();

}

#include

#include

#define MaxVertexNum 12

#define MaxEdgeNum 20

#define MaxValue 1000

typedef int Vertextype;

typedef int adjmatrix[MaxVertexNum][MaxVertexNum];

typedef Vertextype vexlist[MaxVertexNum];

int visited[MaxVertexNum]={0};

struct edgeElem

{int fromvex;

int endvex;

int weight;

};

typedef struct edgeElem edgeset[MaxVertexNum];

void Creat_adjmatrix(vexlist GV,adjmatrix GA,int n,int e)

{int i,j,k,w;

printf("ÊäÈë%d·ö¶¤µãÊù¾Ý",n);

for(i=0;i

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

for(i=0;i

for(j=0;j

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

else GA[i][j]=MaxValue;

printf("ÊäÈë%dÌõÎÞÏò´÷Ȩ±ß",e);

for(k=0;k

{

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

GA[i][j]=GA[j][i]=w;

}

}

void output_edgeset(edgeset GE,int e)

{int k;

for(k=0;k

printf("From %d To %d: %d\n",GE[k].fromvex,GE[k].endvex,GE[k].weight); printf("\n");

}

void prim(adjmatrix GA,edgeset CT,int a,int n)

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

struct edgeElem x;

for(i=0;i

if(i

{CT[i].fromvex=a;

CT[i].endvex=i;

CT[i].weight=GA[a][i];

}

else if(i>a)

{CT[i-1].fromvex=a;

CT[i-1].endvex=i;

CT[i-1].weight=GA[a][i];

}

for(k=1;k

{

min=MaxValue;

m=k-1;

for(j=k-1;j

if(CT[j].weight

j=CT[k-1].endvex;

for(i=k;i

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

if(w

{CT[i].weight=w;

CT[i].fromvex=j;

}

}

}

}

void main()

{int n,e;

vexlist GV;

adjmatrix GA;

edgeset GE;

printf("ÊäÈëͼµÄ¶¤µãÊùºÍ±ßÊù£º");

scanf("%d,%d",&n,&e);

Creat_adjmatrix( GV, GA, n, e);

printf("ÀøÓÃprimËã·¨´Ó0µã³ö·¢ÇóͼµÄ×îСÉú³ÉÊô£º\n"); prim(GA,GE,0,n);

output_edgeset( GE, n-1);

getch();

}


相关内容

  • 最小生成树数据结构实验报告

    • 摘 要 最小生成树是数据结构中图的一种重要应用,在图中对于n个顶点的连通网 可以建立许多不同的生成树,最小生成树就是在所有生成树中总的权值最小的生成树. 本课程设计是以邻接矩阵作为图的存储结构,分别采用Prim和Kruskal算法 求最小生成树.Kruskal算法和Prim算法是求最小生成树的常用算 ...

  • 赋权有向图的最小生成树算法

    • 计 算 机 工 程 第 36 卷 第2期 Vol.36 No.2 Computer Engineering ·软件技术与数据库· 文章编号:1000-3428(2010)02-0061-03 文献标识码:A 2010年1月 January 2010 中图分类号:TP391 赋权有向图的最小生成树算法 ...

  • 贪心算法 最小生成树

    • 摘 要 网络的最小生成树在实际中有广泛的应用,例如,网络G表示n各城市之间的通信线路网线路(其中顶点表示城市,边表示两个城市之间的通信线路,边上的权值表示线路的长度或造价).可通过求该网络的最小生成树达到求解通信线路或总代价最小的最佳方案.本课程设计采用贪心算法中Prim算法解决最小生成树问题,贪心 ...

  • 解决TSP的遗传算法初始种群改进方法研究

    • 解决TSP 的遗传算法初始种群改进方法研究1 贾海鹏,郑丽英,何天斌,徐顼 兰州交通大学电子与信息工程学院,甘肃兰州(730070) E-mail : 摘 要:遗传算法受实际系统计算能力的限制,种群个体和迭代次数有限,因此初始种群的选择成为算法成败的一个至关重要的因素,直接影响到算法的寻优效率和效果 ...

  • 最小生成树and最短路径

    • 最小生成树and 最短路径 无独有偶,在两个学期的期末中两门不同的科目<离散数学>和<数据结构>中都谈到了图及其衍生的最小生成树.最短路径问题,并给出了相应的算法--克鲁斯卡尔.普林.迪杰斯特拉.沃舍尔算法.这无疑是释放了一个很大的信号--这些内容很重要.由于之前学<离 ...

  • 最短路径最少费用数学建模论文

    • 摘 要 现今社会网络越来越普及,网购已成为一种常见的消费方式,随之物流行业也渐渐兴盛,每个工厂为了自身的发展需要以最快的速度及时将产品送达所需单位,即高质量高速度的完成送货任务,针对本案例,我们采用了大量的科学分析方法,并进行了反复验证,得出如下结果: 问题1:根据所给问题与数据,我们将题目中给出的 ...

  • 最小生成树实验报告

    • 北京理工大学软件学院 一.实验目的 1. 通过上机程序,进一步加深对最小生成树的理解. 2. 掌握Kruskal算法. 3. 学会用程序解决离散数学中的问题. 4. 增强我们编写程序的能力. 二.实验内容 求带权无向联通平面图的最小生成树 三.实验环境 我的实验依旧是在VC6.0实验环境下完成的,而 ...

  • 一种矩形件优化排样综合算法

    • 第31卷第6期 2003年 6月 华 中 科 技 大 学 学 报(自然科学版) Vol.31 No.6 J.HuazhongUniv.ofSci.&Tech.(NatureScienceEdition) Jun. 2003 一种矩形件优化排样综合算法 王华昌 陶献伟 李志刚 (华中科技大学塑 ...

  • 北大算法分析与设计课件8

    • 第8 章近似算法 8.1 近似算法及其近似比 8.2 多机调度问题 8.2.1 贪心的近似算法 822改进的贪心近似算法8.2.2 8.3 货郎问题 8.3.1 最邻近法 8.3.2 最小生成树法 833最小权匹配法8.3.3 8.4 背包问题 8.4.1 841一个简单的贪心算法 8.4.2 多项 ...

  • 论文4 最佳灾区巡视路线

    • 灾情巡视线路最优规划模型 摘要 本文是把最佳巡视路线问题转化为图论[1]中求旅行商问题(TSP ), 用近似的算法来寻求近似的最优解.我们采用了分区求解的方法, 利用Kruskal 算法得到基于整个网络的最小生成树,并提出了基于最小生成树的分区原则.边界调整原则和均衡度函数, 保证了模型的合理性和解 ...

热门内容

标签

2010年思想汇报   以权谋私检举信范文   公司业绩报告范文   地接导游欢迎词范文   住房公积金申请书范文   淘宝美工计划书范文   机关会议请假条范文   高中生综合素质评价范文成长规划   国税情况说明范文   输液中心护士就业自传   药店不合格药品内容培训小结   协会会长党支部成立发言稿   政府平级单位发函范文   给纪委问题线索的回函