文档介绍：-
. z.
**工业大学2021级学生论文：最小生成树在城市交通建立中的应用
题目：最小生成树在城市交通建立中的应用
姓 名：
学 号：
指导教师：
fic construction
**工业大学2021级学生论文：最小生成树在城市交通建立中的应用
-
. z.
1绪论
中国国际工程咨询公司交通业务部主任周晓勤指出，"以前的各专业规划主要是按照本行业交通开展的需求进展研究和规划的，在交通设施总量缺乏、根本网不完善的时候，互相之间的矛盾并不突出。但随着多种运输方式设施建立的快速开展，各行业交通网络的逐步完善，多种运输方式网络之间的叠加，难免显现出各种运输方式在通道和枢纽衔接上的不协调。其结果是，资源浪费，效率低下，使用不便利。而综合交通网开展规划的公布有利于运输整体构造的调整，资源节约和集约利用，对于交通运输业的可持续开展具有重要和深远的意义。〞
在社会主义建立时期，各个城市建立问题尤其是交通建立尤为重要。在保证各个城市能互相连通的情况下，怎么保证建立公路，怎么建立最省钱是建立工程公司所需考虑的重大情况。从而能节省更多的钱来投资其他地方建立，如农村交通建立。
各个农村交通建立好之后，则可再根据将农村作为一个结点和其它农村再次运用最小生成树。
最小生成树则能有效的解决此问题。例如，以尽可能低的总价建立假设干条高速公路，把n个城市联系在一起。
普里姆算法通过寻找无向图中权值最小的边，并且将其组合成最小生成树，同时将最小生成树以点集的形式输出，便于观察。
根据课程设计任务书要求，本系统开发主要完成以下功能和性能。
**工业大学2021级学生论文：最小生成树在城市交通建立中的应用
-
. z.
(1) 输入无向图的方式要尽量简单方便。
(2) 要能够形象方便的观察无向图的构造。
(3) 要能够形象地演示PRIM算法求最小生成树的过程。
本文第二章主要介绍图和最小生成树、邻接矩阵等概念。第三章主要介绍prim算法。第四章进展系统设计与调试及其在交通建立中的应用。
2 有关最小生成树的概念
最小生成树：连通加权图里权和最小的生成树称为最小生成树。
从最小生成树定义看主要先了解图、树及生成树。本文中最小生成树在计算机中存储方法是应用邻接矩阵的形式存储。故也应了解邻接矩阵的定义。
定义一〔图〕：图是有一个非空的顶点集合和一个描述顶点之间的关系即边的集合组成。它可以形式化的定义为：
G=(V,E)
V={|Verte*Type}
E={<,>|,∈V∧P(,)}
其中，G表示一个图，V是图G中顶点的集合，E是V中顶点偶对的有限集，这些顶点偶对称为边，Verte*Type是用于描述顶点类型，集合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 Matri*〕〕：是表示顶点之间相邻关系的矩阵。设G=(V,E)是一个图，其中V={v1,v2,…,vn}。G的邻接矩阵是一个具有以下性质的n阶方阵：〔本文主要为无向图的邻接矩阵〕
**工业大学2021级学生论文：最小生成树在城市交通建立中的应用
-
. z.
〔1〕 无向图的邻接矩阵是对称的;有向图的邻接矩阵可能是不对称的。
〔1〕无向图的邻接矩阵中第i行第j列表示i结点到j结点的度即权值，可以表示为*一具体应用的数据。也表示i结点是否与j结点连通。
定义四〔生成树〕：如果T是G的一个生成子图又是一棵树，则称T是图G的一棵生成树。
3 prim算法介绍
最小生成树的两个著名算法：prim算法[和克鲁斯卡尔算法[2]