目录
任务书
1引言 3
1.1课题背景与意义 3
2系统需求分析与总体设计 4
2.1系统需求分析 4
2.2系统总体设计 4
3系统详细设计 6
3.1有关数据结构的定义 6
3.2主要算法设计 7
4系统实现与测试 15
4.1系统实现 15
4.2系统测试 16
5总结与展望 24
5.1全文总结 24
5.2工作展望 24
6体 会 25
7参考文献 26
8附录 27
1引言
1.1课题背景与意义
在数据结构学习图后，没有进行大量的训练来巩固，对于图的认识还是停留在书本上比较浅显的位置。希望通过这个课题来掌握图的存储结构与基本算法，深入了解图的结构特点以及实现实际应用，通过解决较复杂的基于图模型的实际问题，对于图形成一个完整的认识。
实际问题即通过以中国各省份为图的顶点，以省份之间的交通网络为图的弧，交通联系代价为弧的权值构造一个图的模型。然后运用书上的最短路径的知识来构建代价最小的交通网络，从而以最小的代价生成一个能够联通全国的交通网络。关于该实现，目前最为广泛的算法主要是普里姆和克利斯卡尔算法，根据实际问题特点（为稠密图，3个顶点，100多条边），选择的最优算法为普里姆算法。通过染色问题实现地图着色，且相邻地点不可着相同颜色，求最少的着色方法，并简单验证四色猜想。该算法实现主要是回溯法解决染色问题，也可以通过这个桥梁来进一步了解回溯法的具体思想，了解其他典型回溯问题（比如八皇后问题）。
该课题主要是想通过以解决简单的实际问题模型来反过来理解图的一系列算法及图的实际意义，用理论知识来指导实际应用，并用实际应用反过来巩固理论知识。
2系统需求分析与总体设计
2.1系统需求分析
设计有效的逻辑数据结构与存储结构表示中国各行政区域的有关信息（如省会城市名，电话区号，人口数，地理位置等）及行政区域间的相邻关系、省会城市间的距离；分析与设计有效的算法对行政区域图进行染色，使每个行政区域染一种颜色且相邻的省份染不同颜色，而总的颜色数最少；另外如在全国省城之间建立通信网，构造费用最低的通信线路铺设方案。
2.2系统总体设计
本系统主要存储运算结构为一个存储图指针的数组，该数组可以同时操作20个图。图的结点信息包括图当前的结点数和弧数，以及一个结点数组的基地址。结点的基本信息包括顶点的值和指向第一条依附该顶点的弧的指针。而弧的信息包括弧指向的顶点的位置，弧的权值以及指向下一条弧的指针。
结点信息包括省名，省会城市名，人口数以及连接相关省的指针，弧信息包括弧尾以及弧的权值。
系统下的子菜单（即具体的实现函数）有：造图，销毁图，返回结点值，增加顶点或弧等20个子功能，并额外增加了文件的读入与写出功能。在这些图的基本操作外新增加生成最小生成树以及判断当前最少色数的函数。
主要模块为生成最小生成树模块和最少染色数模块。最小生成树模块希望通过输入图，返回图的最小生成树信息及执行时间，而最少染色数模块希望通过输入图，返回最少需要的染色数及每一个顶点的着色情况。
