graph
- 格式：doc
- 大小：54.00 KB
- 文档页数：8
实验八图论算法
现实生活中的诸多问题可以转换为相应的图论问题，例如交通流、航空路线、室内线路布置等问题。
图由若干个顶点和顶点之间的连接边组成，一种简单方法是使用邻接矩阵来存储图，但是该方法通常会浪费较多的存储空间，因而标准的方法是使用邻接表来存储图。
本实验实现图和它的一些相关应用。
1.实验目的
a)掌握图的组织和存储结构；
b)掌握图的常用算法：创建顶点、创建边、删除边、查找边等；
c)掌握图的一些基本应用。
2.实验内容
一、图的实现
目标：基于邻接表结构定义一个有向图，并实现其常用算法。
其中，图中每个顶点存放一个字符串数据，每条边存放一个浮点型数据信息。
(一)算法填空：根据功能提示，完善下划线处的代码。
（1）图数据类型的定义
定义相应的结构体数据类型，用来表示图中的相关数据对象。
（2）初始化图
在使用图之前，初始化其为一个空图。
可以通过一个函数实现该操作，函数接收一个待初始化的图的地址作为参数。
（3）创建图顶点
给定一个顶点数据，在图中为其创建一个新顶点。
（4）创建图边
在图中的两个顶点之间创建一条有向边，并存储边上的数据信息
（5）调试
使用上述操作，完成下面代码，运行并调试程序。
(二)算法练习：根据功能提示，实现算法。
（1）删除图边
删除图中的某条有向边<v1, v2>。
算法实现提示：1）在顶点v1的邻接表中查找是否存在邻接顶点v2；2）如果存在，把该邻接顶点从v1的邻接表中移除。
如删除成功，返回1；否则返回-1。
函数原型如下：
（2）查找图顶点
在图中查找包含给定数据的顶点。
如找到，返回顶点索引；否则，返回-1。
函数原型如下：
（3）查找图边
在图中查找一条特定的有向边<v1, v2>。
如找到，返回该边所对应的邻接顶点；否则，返回NULL。
函数原型如下：
（4）调试
构建测试数据，在主函数中调用上述所有操作，运行并调试程序。
(三)思考
（1）图中顶点的单链表存储
在当前的图定义存储中，我们使用数组来存放图中的顶点。
这种方式虽然实现简单，但是存在以下不足：(1) 最多只能存放MAXVERTEXNUM个元素；(2) 如果删除图中的某个顶点，存储在之后的其它顶点的索引号会发生改变，相应地需要更新对应边中的顶点索引号，这需要较大的时间开销。
为了解决这一问题，可考虑使用单链表来存储图中的顶点，进而在邻接表中的邻接顶点中存放对应顶点的地址而不是顶点索引。
尝试使用单链表来存储图中顶点，并实现其常用算法。
二、图的应用
目标：利用图来解决一些实际应用问题。
（1）无权图最短路径问题
给定一个无权图，计算一个顶点到其它顶点的最短路径。
以学校的景点图为例，计算从某一景点到达另一景点需要借道其它景点数最少的路线。
注意：该路线不一定距离最短。
为了实现该问题，对图顶点数据类型进行了扩充，具体算法如下：
（2）带权图最短路径问题
类似地，给定一个带权图，可计算一个顶点到其它顶点的最短路径。
以学校的景点图为例，计算从某一景点到达另一景点距离最短的路线。
算法可通过如下函数实现：
（3）最小生成树问题
给定一个带权的连通图，为其计算一棵最小生成树。
以学校的景点图为例（各个景点之间均连通），假设每条道路的单位造价成本相同，在现有景点图的基础上，设计一个可以保证所有景点有道路相通但总造价最小的景点连接方案。
算法可通过如下函数实现：
（4）综合练习
利用图实现一个简单的航线管理系统。
这里，航线中的每个出发或者到达城市对应着图中的一个顶点，而每条航线对应着两个顶点之间的一条有向边。
程序基本要求如下：
a)建立一个用户可交互程序，程序主菜单包含两个最基本的功能选项：添加航
线信息、查询航线信息；
b)每条航线包含如下基本信息：起止城市名称、航班号、机票价格、飞行距离、
出发时间、到达时间；
c)在添加航线信息时，如果出发或者到达城市所对应的顶点不存在，则在图中
创建相应顶点；
d)在查询航线信息时，用户可以按照如下条件进行查询：出发和到达城市、航
班号。
