题目:最小生成树在城市交通建设中的应用姓名:学号:指导老师:专业:机械工程2014年3月16目录摘要..................................................................................... 错误!未定义书签。
1 绪论 (1)2 有关最小生成树的概念 (2)3 prim算法介绍 (3)4 系统设计及其应用 (5)一、系统设计 (5)二、最小生成树应用 (8)5 总结 (11)参考文献 (12)附件: (13)最小生成树在城市交通建设中的应用摘要:连通图广泛应用于交通建设,求连通图的最小生成树是最主要的应用。
比如要在n个城市间建立通信联络网,要考虑的是如何保证n点连通的前提下最节省经费,就应用到了最小生成树。
求图的最小生成树有两种算法,一种是Prim(普里姆)算法,另一种是Kruskal(克鲁斯卡尔)算法。
本文通过将城市各地点转换成连通图,再将连通图转换成邻接矩阵。
在Microsoft Visual C++上,通过输入结点和权值,用普里姆算法获得权值最小边来得到最小生成树,从而在保证各个地点之间能连通的情况下节省所需费用。
本文从分析课题的题目背景、题目意义、题目要求等出发,分别从需求分析、总体设计、详细设计、测试等各个方面详细介绍了系统的设计与实现过程,最后对系统的完成情况进行了总结。
关键字:PRIM算法、最小生成树、邻接矩阵、交通建设AbstractConnected graph is widely applied in traffic construction, connected graph of minimum spanning tree is the main application.Such as to establish a communication network between the n city, want to consider is how to ensure n points connected under the premise of the most save money, apply to the minimum spanning tree.O figure there are two kinds of minimum spanning tree algorithm, one kind is Prim (she) algorithm, the other is a Kruskal algorithm (Kruskal).In this article, through the city around point into a connected graph, then connected graph is transformed into adjacency matrix.On Microsoft Visual c + +, through the input nodes and the weights, gain weight minimum edge using she algorithm to get minimum spanning tree, which in the case of guarantee every location between connected to save costs.Based on the analysis topic subject background, significance, subject requirements, etc, from requirements analysis, general design, detailed design, testing, and other aspects detailed introduces the system design and implementation process, finally the completion of the system are summarized.Key words: PRIM algorithm, minimum spanning tree, adjacency matrix, traffic construction1绪论中国国际工程咨询公司交通业务部主任周晓勤指出,“以前的各专业规划主要是按照本行业交通发展的需求进行研究和规划的,在交通设施总量不足、基本网不完善的时候,互相之间的矛盾并不突出。
但随着多种运输方式设施建设的快速发展,各行业交通网络的逐步完善,多种运输方式网络之间的叠加,难免显现出各种运输方式在通道和枢纽衔接上的不协调。
其结果是,资源浪费,效率低下,使用不便利。
而综合交通网发展规划的颁布有利于运输整体结构的调整,资源节约和集约利用,对于交通运输业的可持续发展具有重要和深远的意义。
”在社会主义建设时期,各个城市建设问题尤其是交通建设尤为重要。
在保证各个城市能互相连通的情况下,怎么保证建设公路,怎么建设最省钱是建设工程公司所需考虑的重大情况。
从而能节省更多的钱来投资其他地方建设,如农村交通建设。
各个农村交通建设好之后,则可再根据将农村作为一个结点和其它农村再次运用最小生成树。
最小生成树则能有效的解决此问题。
例如,以尽可能低的总价建设若干条高速公路,把n个城市联系在一起。
普里姆算法通过寻找无向图中权值最小的边,并且将其组合成最小生成树,同时将最小生成树以点集的形式输出,便于观察。
根据课程设计任务书要求,本系统开发主要完成以下功能和性能。
(1) 输入无向图的方式要尽量简单方便。
(2) 要能够形象方便的观察无向图的结构。
(3) 要能够形象地演示PRIM 算法求最小生成树的过程。
本文第二章主要介绍图和最小生成树、邻接矩阵等概念。
第三章主要介绍prim 算法。
第四章进行系统设计与调试及其在交通建设中的应用。
2 有关最小生成树的概念最小生成树:连通加权图里权和最小的生成树称为最小生成树。
从最小生成树定义看主要先了解图、树及生成树。
本文中最小生成树在计算机中存储方法是应用邻接矩阵的形式存储。
故也应了解邻接矩阵的定义。
定义一(图):图是有一个非空的顶点集合和一个描述顶点之间的关系即边的集合组成。
它可以形式化的定义为: G=(V ,E)V={ i V | j V VertexType}E={<i V ,j V >|i V ,j V ∈V ∧P (i V ,j V ) }其中,G 表示一个图,V 是图G 中顶点的集合,E 是V 中顶点偶对的有限集,这些顶点偶对称为边,VertexType 是用于描述顶点类型,集合E 中P (i V ,j V )的含义是:对有向图来说用“<>”表示,对无向图来说用“()”表示,即从i V 到 j V 两个顶点之间存在边。
定义二(树):树包含n (n>=0)个节点。
当n=0时表示为空树。
其定义如下: T=(D,R)其中,D 为树中节点的有限集合,关系R 满足一下条件:1) 有且仅有一个节点k0属于D ,它对于关系R 来说没有前趋节点,结点k0称作树的根结点。
2)除根结点k0之外,D中的每个结点仅有一个前趋结点,但可以有过个后继结点。
3)D中可以有多个终端结点。
即除根结点无父结点,其余各结点都有一个父结点和n(n>=0)个子结点。
图的矩阵表示,本文中只用到了邻接矩阵,故在这只提出邻接矩阵的定义,及其图在邻接矩阵中的表示。
设图A = (V, E)是一个有n 个顶点的图, 图的邻接矩阵是一个二维数组A.edge[n][n],用来存放顶点的信息和边或弧的信息。
定义三(邻接矩阵(Adjacency Matrix)):是表示顶点之间相邻关系的矩阵。
设G=(V,E)是一个图,其中V={v1,v2,…,vn}。
G的邻接矩阵是一个具有下列性质的n阶方阵:(本文主要为无向图的邻接矩阵)(1)无向图的邻接矩阵是对称的;有向图的邻接矩阵可能是不对称的。
(1)无向图的邻接矩阵中第i行第j列表示i结点到j结点的度即权值,可以表示为某一具体应用的数据。
也表示i结点是否与j结点连通。
定义四(生成树):如果T是G的一个生成子图又是一棵树,则称T是图G的一棵生成树。
3 prim算法介绍最小生成树的两个著名算法:prim算法[和克鲁斯卡尔算法[2] ,本文应用的是prim算法。
则克鲁斯卡尔算法则不进行描述了。
Prim算法的基本思想:首先,选择带最小的边,把它放进生成树里,相继添加带权最小的边,这些边与已在树立的顶点相关联,并且不与已在数理的边形成圈,当已经添加了n-1条边为止。
PRIM算法介绍:设图中顶点的全集为V, U中存放已选中过的点,用数据结构closedge[]存放选择需要的数据,先把下标0对应点放入U中, closedge[i].uxiabiao=0,(因为U中只有下标0这一个点), closedge[i].lowcost中存放其他点到下标为0的点的权,closedge[0].lowcost=0;表示下标为0的点已在U中了。
在closedge按顺序找到最先不在U中,且与U中点直接相连的点,把此边的权赋给min,用擂台式比较法选出closedge[j].lowcost中最小的,此时min中存放的是最小值所在下标,也就是下一个要放入U中的点的下标。
输出选中的这条边,它是最小生成树中的一条边。
因为U中又加入了一个点,所以要修改closedge[i].lowcost的值,比较新选中点与V-U中点的权和原来的closedge[i].lowcost,取小的那个存入。
然后继续如上的选择,循环vexnum-1次,就选出了最小生成树中的vexnum-1条边。
本程序采用数组存储结构进行存储,把第一个点所到的边记录下来,然后把权值最小的边存入数组,同时将刚才所存边的的终点作为起点再次记录该点所到的边,并记录权值最小的边存入数组,这个过程中,已经被访问的点不再访问。
知道最后所有的权值最小的边全部输出。
这就是PRIM算法求最小生成树。
Prim算法有两种形式,其伪代码如下:算法一:procedure Prim;beginT:=Φ;U:={1};while U<>V dobegin(u,v):= u∈U且v∈V-U的最小权边;T:=T∪{(u,v)};U:=U∪{v};end;end;改进的prim算法2如下:procedure Prim(var G:adj_matrix;size:integer);{G为图,size为图的节点数目;注意:假设输入的图是连通图}varlowcost:array [1..maxsize] of integer;used:array [1..maxsize] of boolean;closeset:array[1..maxsize] of integer;i,j,k,min:integer;beginfor i:=2 to size do {初始化,此时U只含有顶点1}beginlowcost[i]:= G[1,i];closeset[i]:=1;used[i]:=false;end;used[1]:=true;for i:=2 to size dobeginmin:=maxint;j:=i;for k:=2 to size do {用选择法寻找顶点分别在V-U与U中权最小的边}if (not used[k])and(lowcost[k] beginmin:=lowcost[k];j:=k;end;writeln(fout,'(',closeset[j],',',j,')'); {输出找到的最小生成树的一条边,此处可根据情况修改}used[j]:=true; {将j填加到U}for k:=2 to size do {调整lowcost和closeset}if (not used[k])and(G[j,k] beginlowcost[k]:=G[j,k];closeset[k]:=j;end;end;end;4 系统设计及其应用一、系统设计数据信息以结构体【3】【4】和数组形式储存,结点的信息结构体定义如下:struct graph{char tnode;char hnode;double quanzhi;}gr[100];char node[50]=" ";图的存储结构为:#define INFINITY INT_MAX //最大值#define MAX_VERTEX_NUM 20 //最多的顶点个数typedef enum{DG,DN,UDG,UDN} GraphKind;//{有向图、有向网、无向图、无向网} typedef struct ArcCell{VRType adj; //顶点关系类型:图:0、1 网:权值InfoType *info;//该弧相关信息指针}ArcCell,AdjMaTrix[MAX_VERTEX_NUM] [MAX_VERTEX_NUM];typedef struct{VertexType vexs[MAX_VERTEX_NUM];//顶点向量AdjMaxtrix arcs; //邻接矩阵int vexnum,arcnum; //顶点数和弧或边数GraphKind kind; //图的种类标志}Mgraph;Prim算法:void prim(mgraph g,int k,int n) //核心算法Prim算法实现函数{int i,j,min,p; //定义整型变量i,j用于循环 min和p分别用于临时存放最小权值及其下标struct //定义型类型数据closedge[]用于临时存放下标和最小边{int adjvex;int lowcost;}closedge[100];for(i=1;i<=n;i++) //初始化辅助数组if(i!=k){closedge[i].adjvex=k;closedge[i].lowcost=g.v[k][i];}closedge[k].lowcost=0; //将节点加入生成树中for(i=1;i<n;i++) //循环比较最小权值且将最小权值的点加入生成树中并打印输出{p=1; //初始化pmin=maxvalue; //初始化最小权值for(j=1;j<=n;j++) //循环n次比较最小权值if(closedge[j].lowcost!=0&&closedge[j].lowcost<min) //当前节点不在已生成树中且权值最下{min=closedge[j].lowcost; //替换最小权值为当前节点的权值p=j; //记录该节点下标}printf("%d_ _%d\n",closedge[p].adjvex,p,min); //打印最小的权值的下标和最小边closedge[p].lowcost=0; //将该节点加入生成树中for(j=1;j<=n;j++) //刷新临时存放空间if((g.v[p][j]) < (closedge[j].lowcost)){closedge[j].lowcost=g.v[p][j]; //赋值最小边closedge[j].adjvex=p; //赋值最小边对应下标}}二、最小生成树应用C编写的程序测试【5】数据:假设如图结果应该如下程序运行如图:5 总结该算法循序渐进,通过数组的灵活应用,构造无向连通图并最终轻松实现了生产最小生成树的目的。