两种实用地图着色算法的比较与实现.doc

1、两种实用地图着色算法的比较与实现摘要：地图着色算法的研究是为了是把相邻的区域用尽可能少的颜色区分开。四色猜想是从理论上指出地图着色所需最小着色数，但考虑到实际应用中速度因素，只需采用尽可能优化的地图着色方案，本文中对两种实用算法进行了比较和实现。 关键字：四色猜想；地图着色；DFS 中图分类号： G255.4 文献标识码： A 引言 “四色猜想”虽然至今尚未得到一个严格的数学证明，但人们似乎已经默认这一著名猜想是对的，即任意一个平图都可以用至多四种不同的颜色对其平面区域进行正常着色。地图着色的应用研究是为了是把相邻的区域用尽可能少的颜色区分开，而不是针对“四色猜想”的问题本身1。地图着色实际应

2、用中速度指标和颜色数目指标同样重要，目标是在可容忍时间消耗的基础上采用尽可能少的颜色进行着色2。 着色算法 对于平面图的着色问题的研究一直成为研究热点，特别是随着计算机的出现和广泛应用，图的着色理论也有了迅速的发展，其应用日益广泛34。现在已经成为研究系统工程、管理工程、计算机可续、通讯、网络理论、运筹学等所必须的一种手段56。 ，本文从实际应用角度列举的两种算法都是实现基于四色猜想的着色优化，但并不一定是最佳的着色算法。 算法 1：根据图 G 的邻接矩阵，依次按节点序号遍历所有节点，进行着色。先用一种颜色对节点着色，判断矩阵中与该节点相邻的节点的颜色是否相同，如果不同，则继续对其他节点遍历。

3、如果相同，则改用其他颜色尝试，直至与相邻点颜色不同。 算法中核心的颜色赋值和碰撞检测处理步骤如下： For (依次遍历图的所有节点 i) For (依次判断的最大颜色数目,颜色 j) 给节点 i 赋值颜色 j； For (序号 k 小于该节点序号 i 的节点) If (与该节点 i 相邻&节点 k 的颜色与 j 相同) Break；/退出循环，开始判断下一颜色。 If (序号 k 大于或等于 i) Break； /使用当前颜色 j，开始检测节点 i+1 算法 2：根据图 G 的邻接链表，采用深度遍历（DFS）方式着色。先用一种颜色对种子节点进行着色，判断与该点的邻接链表上的节点的颜色是否相同，

4、若相同，则改用下一种颜色，重复着色处理；若不同，采用该颜色，并对该节点上的邻接链表上的点进行递归处理。算法的核心处理步骤如下： For（图的所有节点） If（种子节点没有着色） /默认种子节点序号为 0 调用递归函数DFScolor 对种子节点着色； 递归函数 DFScolor 为： For （依次遍历的颜色数目，颜色 j） For （该节点 i 的邻接链表节点 m） IF （节点 i 与相邻节点颜色不相同） 计数器变量 count 加 1； Else/颜色相同 计数器变量 count 置 0；Break； /若相同，则尝试下一种颜色 If （计数器变量等于链表长度） Break；/跳出循环，

5、开始深度遍历链表的节点 For （邻接链表节点） If （邻接链表的节点没有着色） 开始对该节点递归着色，调用上面的处理过程 DFScolor； 上述两种算法可以对任意平面图 G 的顶点着色，但着色算法只是基于四色猜想的优化的着色算法，使着色数目尽可能少，并不能满足最小着色的要求。 算法优化 对于顶点不多的平面图 G，两种算法的处理速度几乎相同，但是当图的数目很大时，基于算法 1 的实现是处理不了的，时间上无法忍受；基于算法 2 的实现，处理时间也是成倍增加。分析原因： 算法 1 中，当平面节点为 N 时，需开辟 NN 的矩阵空间，必然消耗巨大的内存空间，并且开辟空间过程也必然消耗时间，因为矩

6、阵为对称矩阵，所以 N*N 矩阵中存储了大量无用数据；使用邻接矩阵，在着色冲突检测和处理中做了很多无用判断，浪费了时间。总之，图 G 的邻接矩阵的创建过程和着色处理都浪费了大量时间。 算法 2 中，采用邻接链表的存储处理，虽然节省了空间，在一定程度上提高了时间和空间效率，但是因为该算法使用递归调用，原理上使用了堆栈结构，所以当节点数目很大时，在着色的冲突处理上必然影响了处理效率。 优化方案： 首先，算法 1 借鉴算法 2 的优点，改用邻接链表存储图 G，节省了内存空间，同时有效地提高了判断处理效率，减少了循环次数，一定程度上节省处理时间。在处理多节点时，优势更为明显。 其次，对图 G 中节点，

7、按照度进行由大到小排序，优先对度大的节点着色。因为先对度大的节点着色，可以减少碰撞机会和避免一些碰撞处理（即可以减少算法 2 中递归调用的堆栈的回退操作） ，同时可以减少着色使用的颜色数目。所以，在算法 1 中，可以先对图节点排序再着色处理；在算法 2 中，是将最大度的节点设为种子节点。算法中引进排序，可以有效地提高着色效果，减少着色的颜色数目。实际着色应用中，当图的节点很大时，排序效果明显；当节点数目不多时，可以不进行排序。再次， 算法中使用了临时的着色标志数组，提高了判断效果。在实际着色应用中可以根据图的节点数目不同，来分别采用两种算法的处理实现，从而达到提高处理时间和优化着色颜色。 算法

8、实现与比较 作者以 Visual C# 2005 为开发工具， 基于 Arc Engine 实现了地图着色功能，验证上面的两种着色算法的正确性。并通过着色效果和时间消耗对比，从实际着色处理角度出发，选择更优的着色方案。 三种着色功能，经过排序处理着色后的效果不会出现重色；未经过排序直接着色处理，会出现重色，需要第五种填充颜色。从着色效果角度，当图的节点数目较多时排序处理是很必要的，虽然增加了部分时间消耗，但是着色颜色却能减少一种，采用四种颜色着色效果更均匀。 利用算法 1 不采用排序处理时，需要使用五种颜色才能将全国地图区分开；采用排序处理，只需要四种颜色就可以将全国省市自治区地图区分开。 利

9、用三种方式分别对中国地图的着色处理，着色效果相同的情况下，消耗时间对比如下： 着色方式 消耗时间 算法 1，链表方式 36 秒 859 毫秒 算法 1，矩阵方式 5 分 21 秒 703 毫秒 算法 2 35 秒 406 毫秒 可见，图的邻接矩阵方式处理着色时间消耗是惊人的。随着图顶点数目的增加，矩阵方式不可取，相反，链表方式存储处理着色问题能节省大量时间，节点数目越多，效果越明显。采用链表方式的算法 1 和算法 2 在处理效率上几乎相同，在节点数目不大时，算法 2 一般优于算法1。 当节点数目很大时，两种算法的优劣将会改变。对节点排序的效果不明显，排序与否都需要六种颜色，排序相反会消耗大量的

10、时间。实际应用中，当节点数目很大时，为了保证速度可以不进行排序处理。 算法 2 由于递归中堆栈的使用导致空间和时间的大量消耗，在着色效率上会低于算法 1，见下表。 着色方式 消耗时间 算法 1，链表方式 算法 1，矩阵方式 逐渐趋于无限大 算法 2 通过试验对比，从地图着色的实际应用角度考虑，可以将算法 1 和算法 2 结合起来，当图的节点较少时，进行排序处理最好采用算法 2 着色处理；当图的节点很大时，不进行排序处理，最好采用链表方式的算法 1 着色处理。 结束语 本文中考虑到实际应用中速度和着色颜色两种因素，对两种实用算法进行了对比和实现，通过试验对比，在实际应用中采用尽可能优化的地图着色

11、方案。 参考文献 1 Appel K, Haken W. The solution of the four-color-map problemJ. Scientific American，1977,(10):108-121. 2 辛柱鼎 “四色定理”的计算机验证2001 年度全国计算机软件考试高级程序员级下午试题五评析J计算机时代，2002，(3):17-18 3 常友渠，肖贵元，曾敏贪心算法的探讨与研究J重庆电力高等专科学校学报，2008，9(3):40-47 4 卓新建，章祥荪用 Hopfield-型神经网络解四色猜想问题J运筹学学报，1999，(3):53-58 5 梁述明，陆忠武四色图着色问题的混沌神经网络解法J武汉科技大学学报(自然科学版)，2006，(6)：165-169 6 王淑栋，许进，刘会新用混合遗传算法求解图的邻强边着色问题J系统工程与电子技术，2003，(5):26-29