图论-最小生成树在城市交通建设中应用.doc

最小生成树在城市交通建设中的应用
姓名 XX
学号 S100203029
专业计算机应用技术
2010年12月4
目录
摘要 I
绪论 1
2 有关最小生成树的概念 2
3 prim算法介绍 3
4 系统设计及其应用 5
一、系统设计 5
二、最小生成树应用 6
5 总结 9
参考文献 10
附件: 11
最小生成树在城市交通建设中的应用
摘要
连通图广泛应用于交通建设,求连通图的最小生成树是最主要的应用。比如要在n个城市间建立通信联络网,要考虑的是如何保证n点连通的前提下最节省经费,就应用到了最小生成树。
求图的最小生成树有两种算法,一种是Prim(普里姆)算法,另一种是Kruskal(克鲁斯卡尔)算法。
本文通过将城市各地点转换成连通图,再将连通图转换成邻接矩阵。在Microsoft Visual C++上,通过输入结点和权值,用普里姆算法获得权值最小边来得到最小生成树,从而在保证各个地点之间能连通的情况下节省所需费用。
本文从分析课题的题目背景、题目意义、题目要求等出发,分别从需求分析、总体设计、详细设计、测试等各个方面详细介绍了系统的设计与实现过程,最后对系统的完成情况进行了总结。
关键字:PRIM算法、最小生成树、邻接矩阵、交通建设
绪论
中国国际工程咨询公司交通业务部主任周晓勤指出,“以前的各专业规划主要是按照本行业交通发展的需求进行研究和规划的,在交通设施总量不足、基本网不完善的时候,互相之间的矛盾并不突出。但随着多种运输方式设施建设的快速发展,各行业交通网络的逐步完善,多种运输方式网络之间的叠加,难免显现出各种运输方式在通道和枢纽衔接上的不协调。其结果是,资源浪费,效率低下,使用不便利。而综合交通网发展规划的颁布有利于运输整体结构的调整,资源节约和集约利用,对于交通运输业的可持续发展具有重要和深远的意义。”
在社会主义建设时期,各个城市建设问题尤其是交通建设尤为重要。在保证各个城市能互相连通的情况下,怎么保证建设公路,怎么建设最省钱是建设工程公司所需考虑的重大情况。从而能节省更多的钱来投资其他地方建设,如农村交通建设。
各个农村交通建设好之后,则可再根据将农村作为一个结点和其它农村再次运用最小生成树。
最小生成树则能有效的解决此问题。例如,以尽可能低的总价建设若干条高速公路,把n个城市联系在一起。
普里姆算法通过寻找无向图中权值最小的边,并且将其组合成最小生成树,同时将最小生成树以点集的形式输出,便于观察。
根据课程设计任务书要求,本系统开发主要完成以下功能和性能。
(1) 输入无向图的方式要尽量简单方便。
(2) 要能够形象方便的观察无向图的结构。
(3) 要能够形象地演示PRIM算法求最小生成树的过程。
本文第二章主要介绍图和最小生成树、邻接矩阵等概念。第三章主要介绍prim算法。第四章进行系统设计与调试及其在交通建设中的应用。
2 有关最小生成树的概念
最小生成树:连通加权图里权和最小的生成树称为最小生成树。
从最小生成树定义看主要先了解图、树及生成树。本文中最小生成树在计算机中存储方法是应用邻接矩阵的形式存储。故也应了解邻接矩阵的定义。
定义一(图):图是有一个非空的顶点集合和一个描述顶点之间的关系即边的集合组成。它可以形式化的定义为:
G=(V,E)
V={ | VertexType}
E={<,>|,∈V∧P(,) }
其中,G表示一个图,V是图G中顶点的集合,E是V中顶点偶对的有限集,这些顶点偶对称为边,VertexType是用于描述顶点类型,集合E中P(,)的含义是:对有向图来说用“<>”表示,对无向图来说用“()”表示,即从到两个顶点之间存在边。
定义二(树):树包含n(n>=0)个节点。当n=0时表示为空树。其定义如下:
T=(D,R)
其中,D为树中节点的有限集合,关系R满足一下条件:
有且仅有一个节点k0属于D,它对于关系R来说没有前趋节点,结点k0称作树的根结点。
除根结点k0之外,D中的每个结点仅有一个前趋结点,但可以有过个后继结点。
D中可以有多个终端结点。
即除根结点无父结点,其余各结点都有一个父结点和n(n>=0)个子结点。
图的矩阵表示,本文中只用到了邻接矩阵,故在这只提出邻接矩阵的定义,及其图在邻接矩阵中的表示。
设图 A = (V, E)是一个有 n 个顶点的图, 图的邻接矩阵是一个二维数组 [n][n], 用来存放顶点的信息和边或弧的信息。
定义三(邻接矩阵(Adjacency Matrix)):是表示顶点之间相邻关系的矩阵。设G=(V,E)是一个图,其中V={v1,v2,…,vn}。G的邻接矩阵是一个具有下列性质的n阶方阵:(本文主要为无向图的邻接矩阵