任务书

p 设计目的：掌握图的存储结构与基本算法，通过解决较复杂的基于图模型的实际问题，提高学生对数据结构知识综合运用的技能与实践能力。

p 设计内容：设计有效的逻辑数据结构与存储结构表示中国各行政区域的有关信息（如省会城市名，电话区号，人口数，地理位置等）及行政区域间的相邻关系、省会城市间的距离；分析与设计有效的算法对行政区域图进行染色，使每个行政区域染一种颜色且相邻的省份染不同颜色，而总的颜色数最少；另外如在全国省城之间建立通信网，构造费用最低的通信线路铺设方案。

p 设计要求：

⑴从互联网或相关资料获取可靠的行政区域及其地理数据，有关数据与信息以文件形式存储，用无向网建模上述问题并以文件保存。

⑵界面上能够显示与输出求解结果，具有对各省份相关信息的查询功能。对主要算法进行理论复杂度分析，并实测其执行效率。

⑶在界面设计与其他功能上可自由发挥，行政区划母图如图1，可以供界面设计处理之用。

p 设计提示：每个行政区域作为一个顶点，邻接矩阵作为主要存储结构，边的权值及信息设置兼顾染色与通信网构建需求；用回溯法设计染色算法，用典型求解最小生成树的算法解决最小费用通信网规划问题。顶点信息在涵盖上述要求信息之外还可作适当补充，通过输入顶点与边的信息建立无向连通网。

p 参考文献：

[1] 严蔚敏, 吴伟民. 数据结构（C语言版）. 北京: 清华大学出版社,1997

[2] 王晓东. 计算机算法设计与分析. 北京: 电子工业出版社, 2007

[3] 严蔚敏, 吴伟民, 米宁. 数据结构题集（C语言版）. 北京: 清华大学出版社,1999

[4] 谢力军,李晓梅,何佳等. 基于模糊最小生成树的通信网络架设模型.吉首大学学报（自然科学版），2010,31(4):43~46