《图论 最小生成树在城市交通建设中的应用》由会员分享，可在线阅读，更多相关《图论 最小生成树在城市交通建设中的应用（17页珍藏版）》请在金锄头文库上搜索。
1、最小生成树在城市交通建设中的应用姓 名 XX 学 号 S100203029 专 业 计算机应用技术 2010 年 12 月 4A目录摘 要 .I绪论 .12 有关最小生成树的概念 .23 prim 算法介绍 .34 系统设计及其应用 .5一、系统设计 .5二、最小生成树应用 .65 总结 .9参考文献 .10附件： .11I最小生成树在城市交通建设中的应用摘 要连通图广泛应用于交通建设，求连通图的最小生成树是最主要的应用。比如要在 n 个城市间建立通信联络网，要考虑的是如何保证 n 点连通的前提下最节省经费，就应用到了最小生成树。求图的最小生成树有两种算法，一种是 Prim（普里姆）算法，另一
2、种是 Kruskal（克鲁斯卡尔）算法。本文通过将城市各地点转换成连通图，再将连通图转换成邻接矩阵。在 Microsoft Visual C+上，通过输入结点和权值，用普里姆算法获得权值最小边来得到最小生成树，从而在保证各个地点之间能连通的情况下节省所需费用。本文从分析课题的题目背景、题目意义、题目要求等出发，分别从需求分析、总体设计、详细设计、测试等各个方面详细介绍了系统的设计与实现过程，最后对系统的完成情况进行了总结。关键字：PRIM 算法、最小生成树、邻接矩阵、交通建设1绪论中国国际工程咨询公司交通业务部主任周晓勤指出， “以前的各专业规划主要是按照本行业交通发展的需求进行研究和规划的，
3、在交通设施总量不足、基本网不完善的时候，互相之间的矛盾并不突出。但随着多种运输方式设施建设的快速发展，各行业交通网络的逐步完善，多种运输方式网络之间的叠加，难免显现出各种运输方式在通道和枢纽衔接上的不协调。其结果是，资源浪费，效率低下，使用不便利。而综合交通网发展规划的颁布有利于运输整体结构的调整，资源节约和集约利用，对于交通运输业的可持续发展具有重要和深远的意义。 ”在社会主义建设时期，各个城市建设问题尤其是交通建设尤为重要。在保证各个城市能互相连通的情况下，怎么保证建设公路，怎么建设最省钱是建设工程公司所需考虑的重大情况。从而能节省更多的钱来投资其他地方建设，如农村交通建设。各个农村交通建
4、设好之后，则可再根据将农村作为一个结点和其它农村再次运用最小生成树。最小生成树则能有效的解决此问题。例如，以尽可能低的总价建设若干条高速公路，把 n 个城市联系在一起。普里姆算法通过寻找无向图中权值最小的边，并且将其组合成最小生成树，同时将最小生成树以点集的形式输出，便于观察。根据课程设计任务书要求，本系统开发主要完成以下功能和性能。(1) 输入无向图的方式要尽量简单方便。(2) 要能够形象方便的观察无向图的结构。(3) 要能够形象地演示 PRIM 算法求最小生成树的过程。本文第二章主要介绍图和最小生成树、邻接矩阵等概念。第三章主要介绍 prim 算法。第四章进行系统设计与调试及其在交通建设中
5、的应用。22 有关最小生成树的概念最小生成树：连通加权图里权和最小的生成树称为最小生成树。从最小生成树定义看主要先了解图、树及生成树。本文中最小生成树在计算机中存储方法是应用邻接矩阵的形式存储。故也应了解邻接矩阵的定义。定义一（图）：图是有一个非空的顶点集合和一个描述顶点之间的关系即边的集合组成。它可以形式化的定义为：G=(V,E)V= | VertexTypeiVjE=| , VP( , ) ijijij其中，G 表示一个图，V 是图 G 中顶点的集合，E 是 V 中顶点偶对的有限集，这些顶点偶对称为边，VertexType 是用于描述顶点类型，集合 E 中 P( , )的含义是：对有向图来
6、说ij用“ ”表示，对无向图来说用“（） ”表示，即从 到 两个顶点之间存在边。ij定义二（树）：树包含 n（n=0）个节点。当 n=0 时表示为空树。其定义如下：T=(D,R)其中，D 为树中节点的有限集合，关系 R 满足一下条件：1） 有且仅有一个节点 k0 属于 D，它对于关系 R 来说没有前趋节点，结点 k0 称作树的根结点。2） 除根结点 k0 之外，D 中的每个结点仅有一个前趋结点，但可以有过个后继结点。3） D 中可以有多个终端结点。即除根结点无父结点，其余各结点都有一个父结点和 n（n=0）个子结点。图的矩阵表示，本文中只用到了邻接矩阵，故在这只提出邻接矩阵的定义，及其图在邻接
7、矩阵中的表示。设图 A = (V, E)是一个有 n 个顶点的图, 图的邻接矩阵是一个二维数组 A.edgenn，用来存放顶点的信息和边或弧的信息。定义三（邻接矩阵（Adjacency Matrix） ）：是表示顶点之间相邻关系的矩阵。设G=(V,E)是一个图，其中 V=v1,v2,vn。G 的邻接矩阵是一个具有下列性质的 n 阶方阵：（本文主要为无向图的邻接矩阵）（1） 无向图的邻接矩阵是对称的;有向图的邻接矩阵可能是不对称的。（1）无向图的邻接矩阵中第 i 行第 j 列表示 i 结点到 j 结点的度即权值，可以表示为某一具体应用的数据。也表示 i 结点是否与 j 结点连通。定义四（生成树）
8、：如果 T 是 G 的一个生成子图又是一棵树，则称 T 是图 G 的一棵生成树。33 prim 算法介绍最小生成树的两个著名算法：prim 算法 和克鲁斯卡尔算法 2 ,本文应用的是 prim 算法。则克鲁斯卡尔算法则不进行描述了。Prim 算法的基本思想：首先，选择带最小的边，把它放进生成树里，相继添加带权最小的边，这些边与已在树立的顶点相关联，并且不与已在数理的边形成圈，当已经添加了n-1 条边为止。PRIM 算法介绍：设图中顶点的全集为 V, U 中存放已选中过的点,用数据结构closedge存放选择需要的数据,先把下标 0 对应点放入 U 中, closedgei.uxiabiao=0
9、,(因为 U 中只有下标 0 这一个点), closedgei.lowcost 中存放其他点到下标为 0 的点的权,closedge0.lowcost=0;表示下标为 0 的点已在 U 中了。在 closedge 按顺序找到最先不在 U 中,且与 U 中点直接相连的点,把此边的权赋给 min，用擂台式比较法选出 closedgej.lowcost 中最小的,此时 min 中存放的是最小值所在下标,也就是下一个要放入 U 中的点的下标。输出选中的这条边，它是最小生成树中的一条边。因为 U 中又加入了一个点，所以要修改 closedgei.lowcost 的值，比较新选中点与 V-U 中点的权和原
10、来的 closedgei.lowcost,取小的那个存入。然后继续如上的选择,循环 vexnum-1 次,就选出了最小生成树中的 vexnum-1 条边。本程序采用数组存储结构进行存储，把第一个点所到的边记录下来，然后把权值最小的边存入数组，同时将刚才所存边的的终点作为起点再次记录该点所到的边，并记录权值最小的边存入数组，这个过程中，已经被访问的点不再访问。知道最后所有的权值最小的边全部输出。这就是 PRIM 算法求最小生成树。Prim 算法有两种形式，其伪代码如下：算法一：procedure Prim;beginT:=；U:=1;while UV dobegin(u,v):= uU 且 vV
11、-U 的最小权边;T:=T(u,v);U:=Uv;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:array1.maxsize of integer;i,j,k,min:integer;beginfor i:=2 to size do 初始化，此时 U 只含有顶点 14beginl
12、owcosti:= G1,i;closeseti:=1;usedi:=false;end;used1:=true;for i:=2 to size dobeginmin:=maxint;j:=i;for k:=2 to size do 用选择法寻找顶点分别在 V-U 与 U 中权最小的边if (not usedk)and(lowcostk beginmin:=lowcostk;j:=k;end;writeln(fout,(,closesetj,j,); 输出找到的最小生成树的一条边，此处可根据情况修改usedj:=true; 将 j 填加到 Ufor k:=2 to size do 调整 lowcost 和 closesetif (not usedk)and(Gj,k beginlowcostk:=Gj,k;closesetk:=j;end;end;end;54 系统设计及其应用一、系统设计数据信息以结构体 【3】 【4】 和数组形式储存，结点的信息结构体定义如下：struct graphchar tnode;char hnode;double quanzhi;gr10
