基于深度优先搜索的地图着色算法

摘要

在分析地图着色本质以及深度优先搜索算法优缺点基础上,本文提出一种基于深度优先搜索的地图着色方法,并以全国地图和全国县级行政区划图对本文算法进行了实验验证,取得了较好的着色结果.根据G的邻接链表，采用深度遍历(DFS)方式着色。先用一种颜色对种子节点进行着色，判断与该点的邻接链表上的节点的颜色是否相同，若相同，则改用下一种颜色，重复着色处理;若不同，采用该颜色，并对该节点上的邻接链表上的点进行递归处理。