图论算法理论、实现及应用.pdf

【实例简介】
图论算法理论、实现及应用.pdf 清华大学
前言 、图论研究及图论教学0 图论( Graph Theory)是数学的一个分支,它以图为研究对象。图论中的图是由若干个给定的 顶点、及若干条连接两个顶点的边所构成的图形,这种图形通常用来描述某些事物之间的某种特 定关系,用顶点代表事物,用连接两个顶点的边表示相应两个事物间具有这种关系。这种图提供 了一个很自然的数据结构,可以对自然科学和社会科学中许多领域的问题进行恰当的描述或建模, 因此图论研究越来越得到这些领域的专家和学者的重视。 图论最早的研究源于瑞士数学家莱昂哈德·欧拉( Leonhard euler,1707~1783),他在1736 年成功地解决了哥尼斯堡(Kω nigsberg)七桥问题,从而开创了图论的研究。 哥尼斯堡七桥问题。东普鲁士哥尼斯堡市(今俄罗斯加里宁格勒)有一条布格( Pregel)河, 如图1白a)所示。布格河横贯哥尼斯堡城区,它有两条支流,在这两条支流之间夹着一块岛形地带, 这里是城市的繁华地区。全城分为北、东、南、岛四个区,各区之间共有七座桥梁联系着。 人们长期生活在河畔、岛上,来往于七桥之间。有人提出这样一个问题:能不能一次走遍所 有的七座桥,而每座桥只准经过一次?问题提出后,很多人对此很感兴趣,纷纷进行试验,但在 相当长的时间里,始终未能解决。 (B) 东(D) C 南C) (a) (b) 图1七桥问题 欧拉在1736年解决了这个问题,他将这个问题抽象为一个图论问题:把每一块陆地用一个顶 点来代替,将每一座桥用连接相应两个顶点的一条边来代替,从而得到一个图(如图1(b)所示) 欧拉证明了这个问题没有解(详见本书5.1节),并且推广了这个问题,给出了“对于一个给定的 图,能否用某种方式走遍所有的边、且没有重复”的判定法则。这项工作使欧拉成为图论及拓扑 学的创始人。 在此后的两百多年时间里,图论的研究从萌芽阶段,逐渐发展成为数学的一个新分支。特别 是从20世纪初期开始,在生产管理、交通运输、计算机和通讯网络等方面涌现了许多离散性问题, 这极大地促进了图论的发展。20世纪70年代以后,由于高性能计算机的出现,使大规模的图论 问题的求解成为可能。现在,图论理论广泛应用在运筹学、计算机科学、电子学、信息论、控制 论、网络理论、经济管理等领域。 由于图论的重要性,越来越多的大学将图论单独作为一门课程来开设,把它作为数学、计算 本文中关于图论课程教学改革的一些思想,已经发表在《计算机教育》2009年第20期上,论文题目为《计算机专业 图论课程教学改革探索》,即参考文献[20获得《计算机教育》杂志社举办的“英特尔杯”20090年全国计算机教育优 秀论文评比二等奖)。 图论算法理论、实现及应用 杋科学、电子学、管理学等专业本科生和硏究生的必修课或选修课。很多其他课程的内容也都涉 及到图论知识,如离散数学、运筹学、拓扑学等。介绍图论理论的教材逐渐增多,其中也不乏优 秀的教材,如文献[。这些课程和教材或者是侧重于完整的图论知识体系介绍、以及复杂的 图论定理的数学证明,或者是侧重于从应用数学的角度研究图论在各领域的应用。 另外,为了实现用计算杋程序求解各种应用问题,计算机科学家抽象岀许多数据结构,如栈 队列、堆、树及二叉树、图等,其中图是最重要的数据结构之一,也是应用得最广的数据结构之 。数据结构课程是专门硏究这些数据结枃的描述、实现及应用的课程。数据结构课程讲到图论 部分时,侧重于图结构的描述、图结构的存储、少量基本的图论算法的实现等等 许多学生(特别是计算机专业的学生)在学习图论时,都不满足于图论算法的手工和草稿纸 演算,迫切地想知道如何用程序实现图论中的算法,以及如何将这些算法思想用来求解实际问题 据作者调査统计,市面上侧重于用程序实现图论算法、并通过例题阐述图论算法思想及其应用 的教材少之又少。本教材希望能弥补这一缺憾。所以本书立足于图论算法理论和思想的描述及程 序实现,并以大量的 ACM/ICPC竞赛题目来阐述图论算法思想在求解这些题目中的应用。接下来 简要地介绍 ACMICPC程序设计竞赛。 、 ACM/ICPC程序设计竞赛 1.ACMIICPC ACM/ICPO( ACM International Collegiate Programming Contest,国际大学生程序设计竞赛) 是由美国计算机协会ACM( Association for Computing Machinery)主办的,世界上公认的规模最 大、水平最高的国际大学生程序设计竞赛,其目的旨在使大学生运用计算机来充分展示自己分析 问题和解决问题的能力。该项竞赛从1977年第一次举办世界总决赛以来,至今已连续举办30多 届了。该项竞赛一直受到国际各知名大学的重视,并受到全世界各著名计算机公司的高度关注。 ACM/ICPC竞赛分区域预赛和总决赛两个阶段进行,各预赛区第一名自动获得参加世界总决 赛的资格。世界总决赛安排在每年的3~4月举行,而区域预赛安排在上一年的9~12月在各大洲 举行。 ACMICPC竞赛以组队方式进行比赛,每支队伍由不超过3名队员组成,比赛时每支队伍只 能使用一台计算机。在5个小时的比赛时间里,参赛队伍要解答610道指定的题目。排名时,首 先根据解题数目来排名,如果多支队伍解题数量相同,则根据队伍的总用时进行排名(用时越少, 排名越靠前)。每支队伍的总用时为每道解答正确的题目的用时总和。每道解答正确的题目的用时 为从比赛开始计时到该题目解答被判定为正确的时间,其间每一次错误的提交运行将被加罚20分 钟时间。最终未正确解答的题目不记入总时间,其提交也不加罚时间。 ACMICPC竞赛在公平竞争的前提下,提供了一个让大学生充分展示用计算机解决问题的能 力与才华的平台。 ACMICPC竞赛鼓励创造性和团队协作精神,鼓励在编写程序时的开拓与创新, 它考验参赛选手在承受相当大的压力下所表现出来的非凡能力。竞赛所触发的大学生的竞争意识 为加速培养计算机人才提供了最好的动力。竞赛中对解决问题的苛刻要求和标准使得大学生对解 决问题的深度和广度展开最大程度的追求,也为计算机科学的研究和发展作了一个最好的导向。 2.在线评判网站 随着 ACMICPC程序设计竞赛的推广,各种程序在线评判( Online judge,简写为OJ)网站 也应运而生,这为程序设计爱好者提供了一种新的程序实践方法:在线程序实践。 ①作者对互动出版网站(www.china-pub.com)和卓越亚马逊网站(www.amazon.cn)上列出的全部图论相关书目及目 录进行了仔细的分析,从而得出的结论 在线程序实践是指由OJ网站提供题目,用户在线提交程序,OJ网站的在线评判系统实时评 判并反馈评判结果。这些题目一般具有较强的趣味性和挑战性,评判过程和结果也公正及时,因 此能引起用户的极大兴趣。 用户在解题时编写的解答程序通过网页提交给在线评判系统称为提交运行,每一次提交运行 会被判为正确或者错误,判决结果会及时显示在网页上 用户从评判系统收到的反馈信息包括: " Accepted程序通过评判! Compile error"—程序编译出错。 " Time limit exceeded"—程序运行超过该题的时间上限还没有得到输出结果。 " Memory Limit Exceeded-内存使用量超过题目里规定的上限。 "outpυ ut Limit exceeded"—输出数据量过大(可能是因为陷入死循环了)。 " Presentation error"—输出格式不对,可检査空格、空行等等细节。 " Run Time error"—程序运行过程中出现非正常中断,如数组越界等。 Wrong Answer"—用户程序的输出错误。 等等。 用户可以根据OJ系统反馈回来的评判结果反复修改程序,直到最终收获 Accept(程序正确)。 这个过程不仅能培养用户独立分析问题、解决问题的能力,而且每成功解决一道题目都能给用户 带来极大的成就感。 、本书安排 本书共分9章,每章内容安排如下: 第1章介绍图论的一些基本概念,以及图的两种重要存储表示方法:邻接矩阵和邻接表,并 初步讨论了存储方式对图论算法复杂度的影响。 第2章讨论了图的遍历,遍历是很多图论算法的基础。本章介绍了两种重要的遍历方法:深 度优先搜索和广度优先搜索,并对这两种遍历算法的思想、程序实现、算法复杂度作了详细的分 析和讨论。本章还讨论了活动网络,包括AOV网络与拓扑排序问题、AOE网络和关键路径问题。 第3章讨论树与生成树问题,主要介绍求无向连通图最小生成树的三个算法:克鲁斯卡尔 ( Kruskal)算法、 boruvka算法和普里姆(Prin)算法,并对这三个算法的思想、程序实现、算 法复杂度作了详细的分析和讨论。另外,本章还讨论了判断生成树是否唯一的方法。 第4章讨论了有向网(或无向网)中一个典型的问题:最短路径问题。本章介绍了求解最短 路径问题的4个算法:Dsa算法、 Bellman-FoH算法、SPH算法和Fod算法,这4个算法分 别适用于有向网(或无向网)中各边权值的取值的不同情形及问题求解的不同需要。本章着重对 这4个算法的思想、递推过程、算法复杂度作了详细的讨论,并对这4个算法作了详细的对比分 析。本章还介绍了求最短路径的算法思想在求解差分约束系统中的应用。 第5章讨论了可行遍性问题,包括欧拉回路、汉密尔顿回路以及中国邮递员问题。前两个概 念容易混淆,欧拉回路要求经过每条边一次且仅一次并回到出发点,而汉密尔顿回路要求经过每 个顶点一次且仅一次并回到出发点。本章介绍这相关概念及定理,并讨论这两种回路及中国邮递 员问题的求解方法和应用。 第6章讨论了网络流问题。许多系统包含了流量问题,例如,公路系统中有车辆流,控制系 统中有信息流,供水系统中有水流,金融系统中有现金流等等。从问题求解的需求出发,网络流 问题可以分为:网络最大流,流量有上下界的网络的最大流和最小流,最小费用最大流,流量有 图论算法理论、实现及应用 上下界的网络的最小费用最大流等。本章介绍各种网络流问题的求解方法。 第7章讨论了点支配集、点覆盖集、点独立集、边覆盖集、边独立集(匹配),这些概念之间 存在一定的联系,也容易混淆。本章主要讨论了各种匹配问题,以及求解二部图最大匹配的算法 程序实现和应用。 第8章讨论图的连通性,这是图论中一个重要的概念。本章介绍了无向连通图和非连通图 无向图的点连通性(包括割顶集、割点、顶点连通度、点双连通图等)、边连通性(包括割边集、 割边、边连通度、边双连通图等)、有向图的强连通性(包括强连通、弱连通和单连通)。本章着 重介绍上述概念及求解算法。 第9章讨论平面图和着色问题。本章介绍了平面图和非平面图的概念、平面图的判定方法, 以及图的顶点着色、边着色、平面图的面着色等概念和求解算法。 四、本书读者对象及本书特点 本书的读者对象为计算机专业学生或对 ACM/ICPC竞赛感兴趣的学生,可以作为高等院校计 算机(或相关专业)的图论等相关课程的主教材,也可作为 ACMICPO竞赛的辅导教材。学生或 读者应该具备CC艹语言知识,已经掌握了一定的程序设计思想和方法,具备一定的算法分析与 设计能力,并能熟练使用数据结构。 本书在内容取材、描述上具有如下特点。 1)许多图论教材对图论概念的描述不一致,造成读者的阅读困难,本书试图改变这一现状。 在每个概念的表述上作者査阅了大量的图论著作并进行比较分析。在本书中,作者对每个概念采 用大多数图论教材采用(或约定)的名词、定义方法等。 2)本书对图论算法思想的描述尽可能采用浅显易懂的语言来描述。 3)本书忽略所有图论定理的证明,着重分析图论算法的思想,重点在于这些图论算法的程序 实现。对图论算法的程序实现是以 ACMICPC例题来阐述的。上下两册书共收录了130余道 ACMICPC竞赛题目,例题和练习题各约占一半。本书附录列出了本书所有例题和练习题在ZOJ、 POJ及UVA上的题号。 4)本书图表内容丰富。全书共绘制了270余幅图表,为此在目录后专门列出了本书的图录 5)为方便读者阅读和使用,作者对本书中出现的图论术语、符号、图论算法及应用分别作了 索引,列在本书后面 五、致谢 本书收录了130余道 ACMICPC竞赛题目,这些题目在阐述图论算法思想、演示图论算法应 用等方面起着重要的作用,部分例题的解答程序也参考了网络上发布的一些源代码。同时,本书 在编写过程中还参考了国内外多本优秀的图论教材(详见参考文献)。在此,编者对这些题目、源 代码和图论教材的作者一并表示忠心的谢意。 本书的编写和岀版得到了2010年浙江省教育科学规划研究课题“以大学生学科竞赛为契机推 动课程群的规划与建设”(编号:SCG156)的支持,在此表示感谢。另外,本书的岀版得到了北 京大学出版社的大力支持,在此表示衷心的感谢。 由于作者水平有限,在编写本书时难免出错,欢迎读者指正,或者读者有什么好的建议,都 可以联系编者:wguiping@163.com。不胜感激!!! 编者 2010年1月 目录 第1章图的基本概念及图的存储 3.1.1树 11基本概念 111 3.1.2森林 555 1.1.1有向图与无向图 32生成树及最小生成树 1.1.2完全图、稀疏图、稠密图 321生成树 1.1.3顶点与顶点、顶点与边的关系…3 322最小生成树 1.14顶点的度数及度序列 33克鲁斯卡尔( )算法 1.1.5二部图与完全二部图 3.3.1 算法思想 116图的同构 332等价类与并查集 1.17子图与生成树 3.3.3 Kruskal算法实现 118路径 5677899 3.34B oruvka .95 1.19连通性 3.35例题解析 1.1.10权值、有向网与无向网 34普里姆(Pim)算法 图的存储表示 341Prim算法思想 106 121邻接矩阵…… 342Prim算法实现 107 1.2.2邻接表 15 343关于普里姆算法的进一步讨论.110 12.3关于邻接矩阵和邻接表的进一步 344例题解析 111 讨论 5判定最小生成树是否唯 120 第2章图的遍历与活动网络问题 3.5.1最小生成树不唯一的原因分析.120 2.1DFS遍历 3.52判定最小生成树是否唯一的方法121 22.1DFS算法思想 444 3.53例题解析 212DFS算法的实现及复杂度分析……25第4章最短路径问题 127 2.1.3例题解析 28 4.1边上权值非负情形的单源最短路径问题 22BFS遍历 Dijkstra算法 127 22.1BFS算法思想 4.1.1算法思想 127 22.2BFS算法的实现及复杂度分析…41 4.1.2算法实现 129 2.2.3关于DFS算法和BFS算法的说明.43 4.1.3关于 Dijkstra算法的进一步讨论.132 2.2.4例题解析.… 43 4.14例题解析 133 23活动网络一AOV网络 61 4.2边上权值为任意值的单源最短路径问题 2.3.1AOV网络与拓扑排序 61 一 Bellman-Ford算法… 143 2.3.2拓扑排序实现方法 42.1算法思想 143 2.3.3关于拓扑排序的进一步说明….67 42.2算法实现 145 2.34例题解析 42.3关于 Bellman-Ford算法的进一步 24活动网络一AOE网络 78 讨论 148 2.4.1AOE网络与关键路径 4.24例题解析 2.42关键路径求解方法 79 4.3 Bellman-Ford算法的改进一SPFA算法.161 第3章树与图的生成树 4.3.1算法思想…. 16 3.1树与森林… 4.32算法实现 图论算法理论、实现及应用 4.3.3关于SPFA算法的进一步讨论…165 64.1基本概念 324 4.34例题解析…… 166 642最小费用最大流算法 325 44所有顶点之间的最短路径一Foyd算法…175 644例题解析 327 4.4.1算法思想 176 第7章支配集、覆盖集、独立集与匹配 340 4.42算法实现… 177 7.1点支配集、点覆盖集、点独立集 340 44.3关于Foyd算法的进一步分析….180 7.1.1点支配集 340 4.44例题解析 180 7.1.2点覆盖集 341 4.5差分约束系统 7.1.3点独立集 4.5.1差分约東系统与最短路径 7.1.4点支配集、点覆盖集、点独立集 4.52例题解析 之间的联系 第5章可行遍性问题 208 7.2点支配集、点覆盖集、点独立集的求解.345 51欧拉回路 208 7.2.1逻辑运算 345 51.1基本概念及定理 208 7.22极小点支配集的求解 345 51.2欧拉回路的判定 211 7.2.3极小点覆盖集、极大点独立集的 52欧拉回路的求解 219 求解 52.1DFS搜索求解欧拉回路 219 73边覆盖集与边独立集 .347 522 Fleury(佛罗莱)算法. 7.3.1边覆盖集… .347 53中国邮递员问题 233 7.32边独立集(匹配) 54汉密尔顿回路 234 7.3.3最大边独立集(最大匹配)与最 541基本概念及定理 235 小边覆盖集之间的联系 5.42汉密尔顿回路求解 74匹配问题 350 第6章网络流问题 242 741完美匹配 351 6.1网络最大流 242 742二部图的完备匹配与完美匹配..351 61.1基本概念 242 74.3最佳匹配 352 6.1.2最大流最小割定理 247 7.44匹配问题求解的基本概念及思路352 6.1.3网络最大流的求解 248 7.5二部图最大匹配问题的求解 353 6.1.4 般增广路方法 7.5.1网络流解法 353 Ford- Fulkerson算法 248 7.42匈牙利算法 355 6.1.5最短增广路算法 256 7.4.3例题解析 6.16连续最短增广路算法- Dinic算法260第8章图的连通性问题 .380 617一般预流推进算法 262 8.1基本概念 380 6.1.8最高标号预流推进算法 265 81.1连通图与非连通图. 380 6.1.9网络最大流算法总结 266 8.1.2无向图的点连通性 381 6.1.10例题解析 266 8.1.3无向图的边连通性 382 62最小割的求解 8.14无向图顶点连通性和边连通性的 6.3流量有上下界的网络的最大流和最小流.300 联系 384 6.3.1流量有上下界的容量网络 8.1.5有向图的连通性 6.3.2流量有上下界的网络的最大流.303 82无向图点连通性的求解及应用 6.3.3流量有上下界的网络的最小流.304 8.21关节点的求解 6.34例题解析 310 322重连通分量的求解 64最小费用最大流 323顶点连通度的求解 2 目录 83无向图边连通性的求解及应用 401 92.1欧拉公式 440 831割边的求解 401 922欧拉公式的应用 441 8.32边双连通分量的求解 405 9.3平面图的判定 445 833边连通度的求解 412 94图的着色问题 446 84有向图强连通性的求解及应用 416 941地图染色与四色猜想 446 8.41有向图强连通分量的求解算法416 942图的着色 447 842有向图强连通分量的应用 418 943图着色的应用 449 第9章平面图及图的着色问题 437 9.44图着色求解算法及例题解析…..450 9.1基本概念… 437 索引 91.1平面图与非平面图 437 、图论术语索引 91.2区域与边界 、符号索引 459 9.1.3极大平面图与极小非平面图.…438 、图论问题及算法索引…. 46 914平面图的对偶图 439附录本书例题和练习题目录… 91.5关于平面图的一些定理 439 参考文献 92欧拉公式及其应用 440 【实例截图】
【核心代码】