（岩土工程专业论文）基于图论学的露天开采境界优化算法研究及程序设计.pdf

摘要 露天境界优化是露天矿开采设计和生产过程控制的重要内容。露天矿 优化设计的数值方法按计算精度可以分为严密法和试探法两大类，前者求 解精确，后者运算简捷。传统手工法和浮动圆锥法属于试探法，设计计算 工作量大，无法全面考虑资源开采技术及经济条件指标等因素对境界优化 的影响，很难得到合理的最终开采境界。l g 图论法属于严密法，理论上 有严格的证明，是目前公认的接近真实境界的结果。 本文基于图论学的基本概念和定理，在对三维环境下露天境界优化技 术的研究现状、发展趋势和存在问题进行分析的基础上，重点对l g 算法 在计算机中执行的几个关键技术进行了研究，解决了程序中实行该算法的 核心问题。并采用矿山的实际数据和参数，用l g 算法在三维环境下进行 境界优化，用最终的境界进行经济效益分析。主要研究工作及成果如下： 1 、在查阅大量文献的基础上对露天境界优化技术现状、发展趋势及 存在的问题进行了系统分析研究。 2 、按照图论理论中“图的概念，确定了计算机中的数据结构和存 储方式，即采用树形结构，链接表存储方法。 3 、最终边坡角是境界优化的约束条件之一，本文分析了露天矿边坡 破坏的主要方式和最终边坡角稳定性分析方法。 4 、露天矿经济合理性是开采的主要依据，本文对比了以往手工方法 计算剥采比确定境界和计算机中建立数学经济模型方法，分析了各自的优 缺点。 5 、根据l g 理论写出了计算机可执行的算法。解决了算法中核心问 题：复杂边坡角的情况下形成初始图；有向图的遍历搜索方法；如何计算 项点的权值；如何判断弧的类型；如何形成正则树。 6 、用实际数据对应用l g 理论产生的境界进行经济效益分析。 通过本次研究，解决了执行算法过程中的实际问题。采用l g 图论法 能快速、准确的优化出某铜矿最佳露天开采境界，极大的提高了矿山工作 者的工作效率，是矿山数字化发展的技术保障。 关键词：露天开采境界；图论学；边坡稳定性；价值模型；l g 算法； 初始图；数据遍历 a bs t r a c t o p e n p l to p t i m i z a t i o n i s v e r yi m p o r t a n tt o o p e n p i td e s i g n a n d p r o d u c t i o nc o n t r 0 1 t h e r ea r et w om e t h o d so fo p e n p i to p t i m i z a t i o nd e s i g n c a t e g o r i z e da sc a l c u l a t i o na c c u r a c y ：r i g o r o u sm e t h o da n dt r i a l m e t h o d 1 1 1 e f o r m e rs o l v e dp r e c i s i o n ，t h el a t t e ro p e r a t e db r e i f l y t r a d i t i o n a lm a n u a l m e t h o d a n df l o a t i n gc l o n em e t h o db e l o n gt ot r i a lm e t h o da n dt h e 锄o u n to ft h e i r c a l c u l a t i o ni s h u g e t r i a lm e t h o d sc o u l dn o tt a k er e s o u r c e e x p l o i t a t i o n t e c h n o l o g y a n de c o n o m i c c o n d i t i o ni n d i c e si n t o a c c o u n to fo p e n p i t o p t i m i z a t i o n ，a n di ti sh a r dt og e tr a t i o n a lu l t i m a t eo p e np i t l gg r a p ht h e o r y a l g o r i t h m sh a v eb e e np r o v e dt h a ti tc a no b t a i na no p e n p i ta p p r o a c ht or e a l i t y , w h i c hb e l o n gt or i g o r o u sm e t h o d b a s e do nt h ea n a l y s i so ft h ep r e s e n ts i t u a t i o n ，d e v e l o p i n gt r e n d s t h e e x i s t i n gp r o b l e m so f3 dv i s u a l i z a t i o ns i m u l a t i o nt e c h n o l o g ya n dc 恼e np i t m i n i n go p t i m i z a t i o nt e c h n o l o g y ，t h i s p a p e rf o u c s o n s o l v i n g t h e k e y p r o b l e m sh o wt oe x e c u t et h ea l g o r i t h m si n c o m p u t e r , a d o p t i n gr e a ld a t aa n d p a r a m e t e rf r o mac o p p e rm i n ea n da n a l y s e dt h ee c o n o m i cp e r f o r m a n c e t h e m a i nc o n t e n to ft h i sp a p e ra r ea sf o l l o w s ： 1 t h i sp a p e ra n a l y s e do ft h e p r e s e n ts i t u a t i o n ，d e v e l o p i n gt r e n d sa n dt h e e x i s t i n gp r o b l e m so fo p e np i tm i n i n go p t i m i z a t i o nt e c h n o l o g yi n d e t a i l b a s e do na g r e a tl o to fl i t e r a t u r e 2 a c c o r d i n gt ot h ec o n c e p t i o no f “g r a p h i ng r a p ht h e o r y , c o n f i r m e dt h e d a t as t r u c t u r eo f “t r e es t r u c t u r e ”a n ds t o r a g em o d e o f “l i n k e dl i s t 3 t h ef i n a ls l o p ea n g l ei so n eo f o p e n p i tc o n s t r a i n t t h i sp a p e ra n a l y s e d d i s r u p t i v em o d eo fp i ts l o p ea n dw a y so ff i n a ls l o p ea n g l es t a b i l i t ya n a l y s i s 4 t h ee c o n o m i c a lr a t i o n a l i t yo f o p e np i ti st h em a i nb a s eo ne x p l o i t a t i o n t h l sp a p e rc o m p a r e dm a n u a lm e t h o d so fc o n f i r m i n go p e n - p i tb y c o u n t i n g s t r i p p i n gr a t i ow i t hf o u n d i n gm a t h e m a t i c se c o n o m i cm o d e lb yc o m p u t e r 5 t h i sp a p e rh a dw r i t t e no u te x e c u t a b l ec a l c u l a t o ra l g o r i t s e v e r a l c e n t r a lp r o b l e m sh a db e e ns o l v e d ：h o wt of o r mi n i t i a lg r a p ho nt h eo c c a s i o n s o fc o m p l e xs l o p ea n g l e ；h o wt ot r a v e r s ed i g r a p h ；h o wt oc o u n t t h ew e i g h to f 中南大学硕士学位论文 a b s t r a c t v e r t e x ；h o wt od e c i d et h es o r to fa r c ；h o wt of o r mr e g u l a rt r e e 6 t h i sp a p e rh a da n a l y s e dt h ee c o n o m i cp e r f o r m a n c eo fo p e n - p i tb a s e d o nl g g r a p ht h e o r yw i t hr e a ld a t a p r a c t i c a lp r o b l e mi nt h ep r o c e s so fe x e c u t i o na l g o r i t h mh a sb e e ns o l v e d i nt h i sp a p e r l ga l g o r i t h mc a ng e ta na c c u r a t eo p e np i tf a s t l ya n ds i m p l y , i m p r o v e dw o r ke f f i c i e n c y , i n s u r et h ed e v e l o p m e n to fd i g i t a lm i n e k e yw o r d s ：o p e n p i to p t i m i z a t i o n ，g r a p ht h e o r y , s l o p es t a b i l i t y , v a l u em o d e l ， l e r c h s g r o s s m a n na l g o r i t h m ，i n i t i a lg r a p h ，t r a v e r s ed i g r a p h 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究工作及 取得的研究成果。尽我所知，除了论文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得中南 大学或其它单位的学位或证书而使用过的材料。与我共同工作的同志对本 研究所作的贡献均已在论文中作了明确的说明。 作者签名：j 嶂日期： 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校有权保 留学位论文，允许学位论文被查阅和借阅；学校可以公布学位论文的全部 或部分内容，可以采用复印、缩印或其它手段保存学位论文；学校可根据 国家或湖南省有关部门规定送交学位论文。 作者签名：塑衅导师签名：趄墅日期：递年旦月鱼日 中南人学硕+ 学位论文 第一章绪论 1 1 课题的来源与背景 第一章绪论 露天采矿分为四个步骤：境界优化、开采设计、进度计划和品位控制f l 2 1 。确定 最优露天开采境界是露天矿设计的一个重要步骤，它的目标是实现矿山生产利润最大 化。传统的人工境界优化方法是通过逐渐增大境界尺寸来计算平均剥采比和境界剥采 比，当境界剥采比等于经济合理剥采比且平均剥采比小于经济合理剥采比时，即认为 该境界为最优境界。可以看出，这种方法确定一个境界需要耗费大量的人力和时间， 而且很难找到真正意义上最优境界。随着科学的发展和技术的进步，国内外大中型露 天矿已将边坡与开采境界由过去的传统手工方法变为借助计算机的动态优化方法。随 着采矿工程实际揭露的矿床地质、边坡工程地质与水文地质条件的变化，及时改变边 坡位置、边坡形状、边坡角度，挖掘边坡潜力，调整开采境界，达到多采矿、少剥岩 的目的，以提高经济效益。依靠人工方法达到实时动态优化境界和在多因素限制下得 到精确的结果的目的，是非常困难的。 随着计算机的飞速发展，实现了在计算机中实现复杂的数学问题和处理庞大的数 据量。目前的优化方法多基于矿体块段模型，基本原理是首先将矿体剖分成一定尺寸 的六面体，即块段，通过地质统计学方法推估出每一块段的矿石品位，计算出每一块 段的经济价值和生产成本，最终形成优化开采境界。确定露天矿开采境界的方法很多， 根据优化算法的不同，可以分为两大类，第一类方法称为模拟法，主要包括：断面法、 平面投影法和浮动圆锥法1 3 j 等。第二类方法称为数学优化法，主要基于离散数学中的 图论理论：包括l g 图论法【4 j 、网络最大流算法、网络虚拟流算法【5 1 、p u s h - r e l a b e l 算法、 最大和最小标签法等。 数学优化的方法是目前国内外学者公认的较为接近真实的精确解法，而且可以通 过数学证明，具有可靠的理论依据。虽然国外对基于图论学的境界优化的理论提出很 早，但早期只停留在理论阶段，近年来才在实际软件开发中得以广泛应用，而且优化 的理论也在不停发展。在国内，基于图论学的境界优化的理论和应用研究都相对不足。 中南火学硕卜学位论文 第一章绪论 1 2 研究的现状及发展趋势 1 2 1 图论学的发展及研究现状 图论学1 6 】( g r a p ht h e o r y ) 是数学的一个分支。它以图为研究对象。图论中的图 是指由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物 之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有的关 系。 图论本身是离散数学的一部份。关于图论的文字记载最早出现在欧拉1 7 3 6 年的 论著中，他所考虑的原始问题有很强的实际背景。图论起源于著名的柯尼斯堡七桥问 题。欧拉在1 7 3 6 年解决了这个问题，他用抽象分析法将这个问题化为第一个图论问 题。这项工作使欧拉成为图论( 及拓扑学) 的创始人。 1 8 5 9 年，英国数学家哈密顿发明了一种游戏：用一个规则的实心十二面体，它的 2 0 个顶点标出世界著名的2 0 个城市，要求游戏者找一条沿着各边通过每个顶点刚好 一次的闭回路。用图论的语言来说，游戏的目的是在十二面体的图中找出一个生成圈。 这个问题后来就叫做哈密顿问题。由於运筹学、计算机科学和编码理论中的很多问题 都可以化为哈密顿问题，从而引起广泛的注意和研究。 图论的广泛应用，促进了它自身的发展。2 0 世纪4 0 6 0 年代，拟阵理论、超图理 论、极图理论，以及代数图论、拓扑图论等都有很大的发展1 7 j 。 1 2 2 露天开采境界优化研究现状 从充分利用矿物的角度来看，最终开采境界应该包括尽可能多的地质储量。然而 由于集合约束的存在，开采某部分矿石必须在剥离该部分矿石上面一定范围内的岩石 后才能实现。剥离岩石本身只能带来资盒的消耗，不会带来经济收入。因此，从经济 角度来看，存在一个使矿山企业的总经济效益最佳的最终开采境界。而露天矿优化设 计的目的就是如何确定能够产生最大的经济效益的露天坑开采境界。因此，最终开采 境界的确定是露天矿设计与规划中的一项十分重要的工作，既是技术决策，又是经济 决策。最终开采境界的设计在方法与手段上经历了三个阶段【8 j ： 一、手工设计阶段：这一阶段的设计以经济合理剥采比为基本准则，在垂直剖面 图和分层平面图上进行手工设计和计算。手工方法在西方国家已经成为历史，在我国 矿山和设计院仍在用。 二、计算机辅助设计阶段：这一阶段在方法上与手工阶段基本相同，以计算机为 手段，设计过程在计算机屏幕或数字化仪上进行，设计结果在屏幕上显示或用绘图仪 生成图纸。在发达国家，计算机辅助境界设计在时间上大约对应于7 0 年代中期到8 0 年代中期，如今主要用于境界优化结果的后处理；计算机辅助境界设计在我国始于8 0 2 中南大学硕上学位论文 第一章绪论 年代中期，现已得到一定的应用。 三、优化设计阶段：最终境界优化设计的研究在国际上始于6 0 年代初，但在实 践中得到了较广泛的应用，则是在计算机的存储容量和速度达到一定水平以后，在时 间上大体始于8 0 年代中期。3 0 多年的研究使许多优化方法问世。如动态规划法和图 论法( z h a oa n dk i m ，1 9 9 1 ) 、浮动圆锥法( k o r o b o v l 9 7 4 ) 、三维动态规划法 ( w r i g h t l 9 8 7 ) 、网络最大流法( y e l g u l a l pe t a l1 9 9 3 ) 、正锥删除法( w a n ga n ds e v i m ， 1 9 9 5 ) 、最小标签算法( h o c h b a u r a ，2 0 0 1 ) 、最大标签算法( h o c h b a u m ，2 0 0 2 ) 等等。 境界优化算法致力于解决多因素制约下利润的最大化，并在庞大数据量的情况下快速 的得到真实境界。 1 2 3 存在的问题以及解决方法 目前，手工法在国内矿山应用的比较广泛，多数矿山或设计院还在沿用。用手工 法确定露天丌采境界，先要准备基础资料：诸如描述矿床产状和埋藏情况的地质剖面 图、水平分层平面图、矿岩量表以及由露天开采工艺确定的台阶高度、剖面角、平台 宽度、道路宽度、最终边坡角、最小露天底宽度等要素数据。然后按经济合理剥采比 来确定境界剥采比，西方称之为无盈亏剥采比【9 l ( b r e a ke v e ns t r i p p i n gr a t i o ) ，以境界 剥采比小于或等于经济合理剥采比做为判据来圈定露天开采境界，其概念是指露天开 采境界每增加一个单位深度引起的岩层增量与矿石增量之比。 手工法设计最终境界实质上是一种试错法1 10 1 。存在以下缺点： 一、在矿体形态复杂、品位变化大的矿床中，仅确定一个剖面上的境界常常需要 重复多次，工作量大，耗时费力，具有随机性。虽然也可以圈出一个趋近经济合理的 露天开采境界，但它在经济上不一定是最优的。 二、手工法是在二维的地质剖面图上完成三维的露天矿设计，其结果难以反映矿 体空间特征，而地质剖面图通常不一定垂直于露天矿边坡的走向，各个地质剖面与露 天矿边坡的交角也不一定完全相同，在这种情况下，产生的误差将会很大。 三、由于人工计算工作量的限制，人工方法无法合理地考虑矿石经济特征的空间 分布情况，对于单位体积的矿石而言，不论品位高低、埋藏深度如何，都笼统地取全 矿或某一矿段的平均值。 计算机优化的方法将矿体模型离散成块段模型，通过尺寸控制精度，用特定的算 法让计算机来形成最终边界。目前广为应用的是浮锥法和图论法。 浮动圆锥法形成的境界较为接近真实境界，但某些情况下无法求出最佳境界： 一、当倒锥的顶点位于某一正块时，锥体价值若为j 下数，是由于锥中正块的价值 足以抵消锥中负块的价值的结果。换言之，负块得以开采是由于正块的支持。当顶点 位于两个正块的锥体有重叠部分时，单独考察任一锥体时，锥体的价值可能为负；但 当考虑二锥的联合体时，联合体的总价值为正。结果，浮锥法遗漏了本可带来赢利的 中南大学硕 学位论文 第一章绪论 块的集合l j 。 二、开采非盈利块集合。顶点位于某一正块的锥体值为正，可能是由于锥体内其 他未被开采的正块的作用，而实际去除已开采的块后，剩下的块的价值的和可能为负。 l g 图论法是具有严格数学逻辑的最终境界优化方法，只要给定价值模型，在任 何情况下都可以求出总价值最大的最终开采境界。虽然该理论在国外发展多年，但国 内系统介绍该理论的论著还是空白，而且相关软件开发中的问题在国外至今仍是热点 问题。 1 3 论文的主要研究内容 文章主要是基于c + + 开发平台，系统研究了图论学在露天矿境界优化的应用， 针对复杂边坡角情况、如何建立价值模型、如何降低程序的复杂度等问题，用逻 辑代码的形式写出了具体的核心算法。 论文的章节安排如下： 第一章绪论 简要阐述了本课题的研究意义，介绍了研究现状和目前存在的问题，说明了本文 的主要内容； 第二章图的基本概念及应用 介绍图的几个基本概念，如何将境界优化离散化为图论问题，计算机中图的 运算和图的存储。 第三章树及其应用 树是用来表示数据之间的层次关系，本章介绍树的基本概念，二叉树的存储 和树的遍历搜索。 第四章露天矿优化的几何约束 露天矿开采的主要限制因素为开采边坡角，本章主要介绍影响露天矿开采边 坡角稳定性的主要因素及如何分析边坡稳定性。 第五章露天矿经济合理性分析 本章介绍矿业经济学中开采成本与利润的计算方法，在计算机中如何建立经 济价值模型。 第六章基于图论的l g 法的核心算法及程序设计 本章是文章的核心部分，根据l g 理论写出了计算机可执行的算法。解决了 算法中核心问题：复杂边坡角的情况下形成初始图；有向图的遍历搜索方法、如 何计算顶点的权值；如何判断弧的类型：如何形成正则树。 第七章露天境界优化实例分析 本章主要使用矿山的实际数据，对l g 法的结果进行经济效益分析。 4 中南大学硕士学位论文 第一章绪论 第八章结论与展望 对本文所做的工作进行总结，对进一步研究提出了设想。 1 4 本章小节 本章首先概述了露天开采境界的意义，介绍了国内外对该课题的研究现状和发展 趋势，提出了文章研究的目的和意义，最后对文章的章节内容安排进行了概述。 中南大学硕j ：学位论文 第二章图的皋本概念及应用 2 1 图的概念 第二章图的基本概念及应用 1 7 3 6 年，瑞士数学家欧拉( i e u i e r ) 在他的一篇论文中讨论哥尼斯堡( k o n i g s b e r g ) 七桥问题，由此诞生了一个全新的数学分支图论( g r a p ht h e o r y ) 。在经历了2 0 0 多年的发展之后，图论已经积累了大量的理论和结果，其应用领域也逐渐扩大。最初， 图论主要用来讨论游戏中遇到的问题；1 9 世纪末期，图论已经用来研究电网络方程组 和有机化学中的分子结构：2 0 世纪中叶以后，借助于计算机，图论又用来求解生产管 理、军事、交通运输、计算机以及通讯网络等领域中的许多离散性问题，同时图论中 的一些著名问题也借助于计算机得到了证明。如今，图论本身及其在物理学、化学、 运筹学、计算机科学、电子学、信息论、控制论、网络理论、社会科学和管理科学等 领域的应用越来越受到人们的重视。 图论中所讨论的“图，不是微积分、解析几何、几何学中讨论的图形，而是客 观世界中某些具体事物联系的一个数学抽象，如二元关系的关系图，在关系图中，不 考虑点的位置及连线的长短曲直，而只关心哪些点之间有线相连【1 2 】。 图论中的定义如下： 定义2 1 图( g r a g h )所谓图g 是一个三元组，记作g = ，其中 ( 1 ) v ( g ) = q ，呸，) ，v ( g ) ，称为图g 的结点集合( v e r t e xs e t ) ( 2 ) e ( g ) = e l ，e 2 ，) 是g 的边集合( e d g es e t ) ，其中q 为 d ，q ) 或 。 若e t 为 u ，d f ) 为以d ，和q 为端点( e n dv e r t i c e s ) 的无向边( u n d i r e c t e de d g e ) ；若巳为 ，称p ，为以u ，为起点( o r i g i n ) ，q 为终点( t e r m i n u s ) 的有向边( d i r e c t e de d g e ) 。 ( 3 ) 缈( g ) ：e v v 称为关联函数( i n c i d e n c ef u n c t i o n ) 。 例如已知图g = ，其中： v ( g ) = q ，呸，d 4 ，d 5 e ( g ) 2 e l ，e 2 ，e 3 ，e 4 ，魄，e s ，e 6 ，e 7 ，e s ) 缈( g ) ：e v v ，且 6 中南人学硕： 二学位论文 第二章图的基本概念及应用 f 0 ( e , ) = ，0 4 ，伊( p 2 ) = 0 3 ，d 4 ，伊( 巳) = 屿，d 4 ) ， 缈( e 4 产 ，缈( p 5 ) ， ，伊( e 6 ) ： ， 矿( p 7 ) = ，伊( e 8 ) 5 图g 的一个图形表示如图2 1 ，即用平面上的小圆圈表示图g 的顶点，用点与点 之间的连线表示图g 中的边。图的图形表示使得抽象定义的图具有直观性，有助于我 们进行思考和理解图的性质。 e l 图2 - 1“图”的例子 定义2 2 ： 邻接顶点( a d j a c e n tv e r t i c e s ) 关联于同一条边的两个结点称为邻接结点。 孤立结点( i s o l a t e dv e r t e x ) 不与任何结点相连接的结点称为孤立结点。 邻接边( a d j a c e n ts i d e s ) 关联同一个顶点的两条边称为邻接边。 环( 1 0 0 p ) 两端点相同的边称为环。 平行边( p a r a l l e le d g e s ) 两个结点间方向相同的若干条边称为平行边。 定义2 3 ： 无向图( u n d i r e c t e dg r a p h ) 每条边都是无向边的图称为无向图。 有向图( d i r e c t e dg r a p h ) 每条边都是有向边的图称为有向图。 简单图( s i m p l eg r a p h ) 无环并且无平行边的图称为简单图。 2 2 图的存储 图的结构比树型结构和线性结构更复杂，任意两个顶点之间都可能存在联系，无 法用数据元素在存储器中的物理位置表示数据之间的逻辑关系，因此图没有顺序存储 结构。图的存储结构比较多，对于图的存储结构的选择取决于具体的应用。常用的存 7 中南人学硕十学位论文 第二章图的摹本概念及鹰用 储结构有：邻接矩阵、邻接表、邻接多重表和十字链表1 3 1 。本节只介绍图的数组表示 法和邻接表表示法。 2 2 1 数组表示法 数组表示法是用一维数组存储图的顶点信息，用二维矩阵存储图的顶点之间的关 系( 边或弧) 。这个表示顶点之间关系的二维矩阵称为邻接矩阵，因此有时将数组表 示法称为邻接矩阵表示法。假设图g = ( v ，e ) 有n 个顶点，即v = v 。，1 ，：，) ，将其存 储在一个一维数组v 中，则g 的二维邻接矩阵表示为 即彻5 譬雾。影纛0 ：，荒茹船，啬嚣门 其中，i 和j 分别为顶点哆和在数组v e x 中的位置。 若g 是网，则邻接矩阵可定义为 f f若( ，。1 ，) 或 是e ( g 1 中的边，i r - l - j 、f ，j 刀 e 【i 】d 卜1o 蕞若( v ，歹或 不是e ( g ) 中的边，i f ，以 其中，i 和j 分别为顶点，和1 在数组v c x s 中的位置，为边( v i ，叶) 或 上的权值，为一个计算机允许的最大值。 例如无向图g 1 和有向图g 2 用数组表示法分别如图2 - 2 、2 - 3 。 图2 - 2 无向图g l 无向图g 1 和有向图g 2 用数组表示如下： v e x l = ，l 、v 2 、 v 3 、，4 、1 ，5 o11lo lol01 互2 l1o1o ) 1o10 o o1o o o 图2 - 3 有向图g 2 v e x 2 = v l 、1 ，2 、v 3 、v 4 ， 01 三： ， 10 o o 0 o 0 1 1 o ，i = 幺 中南大学硕士学位论文第二章图的基奉概念及应用 通过图的数组表示法，可以知道其特征如下。 ( 1 ) 用数组表示法表示图，需要存放n 个顶点信息和n2 个边( 或者弧) 信息 的储存量。 ( 2 ) 用邻接矩阵方法存储图，很容易确定图中任意两个顶点之间是否有边相连； 但是，要确定图中有多少条边，则必须按行、按列对每个元素进行检测，所花费的时 间代价很大。这是用邻接矩阵存储图的局限性。 根据以上数组表示法的描述，可以给出图的严格定义如下。 # d e f i n em a x1 0 产图的最多顶点数 t y p e d e f c h a rv e r t e x t y p e ；产图的顶点类型木 t y p e d e ff l o a ta d j t y p e ；+ 图的边( 弧) 类型木 t y p e d e fs t r u c t v e r t e x t y p ev e x s m a x ；严顶点的一维向量幸 a d j t y p ee d g e s m a x m a x ； 图的边( 弧) 的邻接矩阵，无权图用1 或0 表示顶点是否相邻；带权图则 为权值类型宰 i n tn ，e ；* n 为当前顶点数e 为当前的边数( 弧数) 幸 m g r a p h ； 根据以上定义，建立一无向网的数组表示如图2 - 4 ，其算法如下算法2 1 。 图2 - 4 无向网g 无向网g 及其数组表示如下： v e x s 2 a 、b 、c 、d 、e ) 66 926 5o o ) 5o o4 4 5 9 2 6 9 5 6 6 ，、 = e 中南大学硕士学位论文第二章图的基本概念及应用 【算法2 1 】： v o i dc r e a t g n ( m g r a p h * g ) 产构造无向网幸 i n ti j ，k ； a d j t y p ew ； s c a n f ( “d ，d ，& ( g n ) ，& ( g e ) ) ；产输入图的顶点和边数幸 f o “i = l ；i n ) ，i + + ) f o r ( j = 10 n ) j + + ) g e d g e i 】d 】_ o ；严邻接矩阵的初始化 f o r ( i = 1 ；i n ) ，i + + ) s c a n f ( “o c , & ( g v e x s i 】) ) ；p 构造顶点向量幸 f o r ( k = l ；k e ；h 斗) s c a n f ( “d ，d ，f ，& i ，& j ，& w ) ；簟i 和j 分别表示两个顶点在一维向量的位置，w 表示边 ( 或弧) 的值，如果两个顶点之间没有边，则权值w 为 一特定的预先给定的值 g 一 e d g e i j - - w ； g - e d g e d 】【i 】2 w ； ) 产构造邻接矩阵事 以上算法的执行时间是o ( n + 疗2 + p ) ，其中0 ( 刀2 ) 的时间消耗在邻接矩阵的初始 化操作上。 2 2 2 邻接表 邻接表是图的一种链式存储方法，对于图g 中的每个顶点1 ，将所有邻接于v ，的 顶点v ，连成一个单链表，该单链表就称为顶点v ，的邻接表，单链表中的结点称为表结 点。然后为对应于每个顶点的邻接表建立一个头结点，这些头结点通常以顺序结构的 形式存储( 也可以用链式结构的形式存储) 。为了便于随机访问任意顶点的邻接表， 可以将所有点的邻接表的头结点放到一个数组中，于是图就可以由这个头结点的数组 表示，这个头结点数组称为顶点表。因此，在图的邻接表表示中有两种结点结构。 1 0 中南大学硕上学位论文 第二章图的基本概念及应用 邻接表结点指针域 ii ia d j v e x n e x t l ll 表节点 顶点域指针域 l l v e r t e x f i r s t e d g e l 头结点 由上图可以知道，表结点表示一条链表，它由某个顶点的邻接顶点信息和指向下 一条邻接边的指针域( n e x t ) 构成。头结点由顶点域和指向第一条邻接边的指针域构 成。 下图分别给出了无向图g 和有向图g 2 对应的邻接表表示。 1 e 工 h 坷 ：e 工了 e h 佃 ，e 工了 h 二 旧 e 工了 卜 口 ，e 工了皿 图2 - 6 无向图g l 的邻接表表示 1 1 二 以上结构的严格定义如下： t y p e d e f s t r u c tn o d e 产表结点奉 i n tv e x p o s i t i o n ； 严邻接顶点在顶点表中的位序+ 2 3 4 中南大学硕上学位论文 第二章图的基奉概念及应用 s t r u c tn o d e * n e x t ； 严指向下一个邻接点的指针域+ e d g e n o d e ； t y p e d e f s t r u c tv n o d e严邻接表的头结点木 v e r t e x t y p ev e r t e x ； 顶点域 e d g e n o d e * f i r s t e d g e ； ，i 邻接表的头指针 ) v e r t e x n o d e ，a d j l i s t m a x ；* a d j l i s t 存储顶点邻接表的头结点幸 t y p e d e f s t r u c t a d j l i s ta d j l i s t ； 严邻接表幸 i mn ，e ；产顶点数和边数幸 ) a l g r a p h ；产a l g r a p h 是以邻接表方式存储的图类型 根据以上定义，建立一个无向网的邻接表表示的算法如下： 【算法2 2 】 v o i dc r e a t u d a l g r a p h ( a l g r a p h 宰g ) i n ti j ，k ； e d g e n o d e s ； s c a n f ( “d d ”，& ( g n ) ，& ( g e ) ) ；读入顶点数和边数 f o r ( 浮1 ；i n ；i + + ) 事建立有n 个顶点的顶点表奎 s c a n f ( “n d ”，& ( g - a d j l i s t i v e r t e x ) ) ；严读入顶点的值 g 一 a d j l i s t i f i r s t e d g e = n u l l ； 产顶点表中各点结点的指针域为空 ) f o r ( k = 1 ；k e ；k 抖) 产建立边表幸 s c a n f ( d ，d ”，& i ，& j ) ； 产读入顶点h 、在顶点表中对应的次序 s = ( e d g e n o d e 木) m a l l o c ( s i z e o f ( e d g e n o d e ) ) ；p 生成新邻接表结点s s 一 a d j v e x = j ； 严邻接顶点的位序为j 1 2 中南大学硕上学位论文第二章图的基奉概念及应用 s - n e x t = g 一 a d jl i s t i f i r s t e d g e ； g a d jl i s t i f i r s t e d g e = s ； ) 产将s 插入顶点的邻接表头部+ * g f fv 插入顶点v ，的邻接顶点幸 产将作为哆的邻接顶点 s = ( e d g e n o d e ) m a l l o c ( s i z e o f ( e d g e n o d e ) ) ；+ 生成新邻接表结点s s 一 a d j v e x = i ； 产邻接顶点的位序为j 幸 s - n e x t = g 一 a d j l i s t j f i r s t e d g e ； g - a d j l i s t i f i r s t e d g e = s ； ) ) ) 枣将s 插入顶点，的邻接表头部宰 产将v ，作为的邻接顶点幸 以上算法的时间复杂度为o ( n + e ) 。若无向图中有n 个顶点、e 条边，则它的邻接 表需n 个头结点和2 e 个表结点。而用数组表示法表示无向图则由需要存放n 个顶点 信息和行2 个边信息的存储量。显然，在边稀疏的( e 0 ) 个结点的有限集t 。其中， ( 1 ) 有且仅有一个特定的称为树根( r o o t ) 的结点； ( 2 ) 当n l 时，其余结点可分为m ( m 0 ) 个互不相交的有限集t 。、t 2 、t3 t 。， 而每一个集合本身又是棵树，称为树的子根( s u b t r e e ) 。 结点( n o d e ) 表示树中的元素，包含一个数据和若干指向其子树的分支( 即关系) 。 结点的度( d e g r e e ) 结点拥有的子树数 叶子结点( 1 e a f ) 度为零的结点 孩子结点( c h i l d ) 结点子树的根称为该结点的孩子 双亲结点( p a r e n t ) 若结点b 是结点a 的孩子，则结点a 称为结点b 的双亲。 兄弟结点( s i b l i n g ) 同一个双亲的孩子之间互称为兄弟 基本运算如下： i n i t i a t e ( t ) t 树的初始化，包括建树。 r o o t ( t ) 求t 树的根。 p a r e n t ( t , x ) 求t 树中结点x 的双亲结点。 c h i l d ( t , x ，i ) 求t 树中结点x 的第i 个孩子结点。 t r a v e r s e ( t ) 遍历t 树。按某个次序依次访问树中每一个结点，每个结点都被访 问且仅被访问一次。 1 4 中南人学硕士学位论文第三章树及其应用 c l e a r ( t ) 将t 树置空。 3 1 2 树的存储 3 1 2 1 双亲表示法 定义一个结构体数组存放树的结点，数组中的每个元素包含两个域，一个是数据 域，用来存放结点本身的信息；一个是双亲域，用来存放结点的双亲在数组中的位置 ( 即数组的下标) 。用c 语言定义的存储结构如下。 t y p e d e fs t r u c tn o d e d a t a t y p ed a t a ； i n tp a r e n t ； ) n o d e ； n o d et 【m 】； 下图展示了一颗树及其双亲表示的存储结构。数组中下标为0 的单元不可用。 a 0 lb 1c ld 2e 4f 4g 4h 5i 5j | | 、【| | | | | | | | | | | | | | 中南大学硕士学位论文第 三章树及j e 应用 s t r u c tn o d e * n e x t ；产指向下一个孩子结点宰7 n o d e ； ( 2 ) 表头结点 t y p e d e f s t r u c tn o d e d a t a t y p ed a t a ； 数据域幸 s t r u c tn o d e 幸f c ：产指向第一个孩子结点，i ) t d ； t d t 【m 】；牛t 【o 】不用幸 下图为孩子链表表示法。数组下标为0 的单元置空。 a2 l l， - i4 一l j 5 b c d67 口 一l u 91 0e f g h l j 一一| | | | | | | | | | | | | | | | | | 中南大学硕士学位论文第三章树及其应用 d a t a t y p ed a t a ；产数据域幸， i n tp a r e n t ；产双亲域木 s t r u c tn o d e f c ：指向第一个孩子结点 ) t d ； t dt m 】；产t o 】不用木 一i 1 一l ，一l 0a i 1 一i 厶 一l j 15 b 1 c 1d 6 一i 一lo ，o 2。91 0e 4 f 4 g 4 h 5 i 5 j 1 7 i ? | | | | | | | | | | | | | | | | | | 中南大学硕上学位论文第三章树及其应用 a a b j c d l - rif 7 1 e f a g 廿 h a l l _ h j 3 2 二叉树的存储和遍历 图3 - 4 孩子兄弟表示法 二叉树是n ( 刀0 ) 个结点的有限集，它或为空树( n - 0 ) ，或由一个根结点和两 棵树分别称为左子树和右子树的互不相交的二叉树构成。由二叉树的定义可以归纳出 二叉树的特点如下。 ( 1 ) 每个结点最多有两棵子树，即二叉树中的结点的度只有三种取值：0 、1 、2 ( 2 ) 子树有左、右之分，其次序不能颠倒。 3 2 1 二叉树的存储 二叉树的存储也有顺序存储和链式存储两种存储结构。 3 2 1 1 顺序存储结构 对于一颗二叉树，其中个结点的编号与等深度的完全二叉树中对应位置上的结点 编号相同，然后用一个数组按照结点的编号顺序依次存放二叉树中的数据元素，就是 二叉树的顺序存储结构。其结点的编号规则是，根结点编号为1 ，然后按照从上到下、 从左到右的顺序对每一个结点进