数据结构与算法实验报告五（图的存储实现包括加权邻接矩阵，邻接表 图的遍历 最短路径-Dijkstra算法）

一、实验目的

（1）掌握图的存储实现（加权邻接矩阵，邻接表）；

（2）掌握图的遍历；

（3）掌握最短路径-Dijkstra算法（单源最短路径，所有顶点最短路径）或弗洛伊德算法；

（4）针对具体复杂问题，能够对项目进行合理的数据抽象，选择或构建合适的数据结构和算法，具有初步解决复杂工程问题的能力；

（5）在分析复杂工程问题时，能够通过文献研究给出多种数据结构和算法的解决方案，并能够分析相应的优缺点。

二、实验内容

 安阳是中国八大古都之一、国家历史文化名城，是甲骨文的故乡、周易的发源地、红旗渠精神的发祥地，是世界文化遗产殷墟、中国文字博物馆所在地。甲骨文，是中国的一种古老文字，又称“契文”、“甲骨卜辞”、“殷墟文字”或“龟甲兽骨文”，是我们能见到的最早的成熟汉字。2017年11月24日，甲骨文顺利通过联合国教科文组织世界记忆工程国际咨询委员会的评审，成功入选《世界记忆名录》。加入有游客去殷墟博物馆欣赏完了甲骨文，想要去中国文字博物馆了解历代中国文字样本精华，古汉字的构形特征和演化历程。请用所学知识，根据图中各文化景点之间的距离和路径，给该游客推荐一条最短的路径。

（1）用图实现位置信息的存储并能进行遍历等相关操作；

（2）求最短路径相关操作。

三、算法描述

（采用自然语言描述）

1. initializeGraph 函数：

功能：初始化图的数据结构。

操作：

将顶点数量设置为 0。

将边数量设置为 0。

创建一个二维数组（邻接矩阵），并将其所有元素初始化为 0。

2. addVertex 函数：

功能：向图中添加一个新的顶点。

输入参数：

顶点索引（通常是一个整数）。

顶点名称（一个字符串或其他数据类型，用于标识顶点）。

操作：

在顶点列表中增加新顶点，并记录其索引和名称。

更新顶点数量。

3. addEdge 函数：

功能：向图中添加一条边。

输入参数：

起始顶点的索引。

终点顶点的索引。

边的权重（一个数字，表示两个顶点之间的距离或成本）。

操作：

在邻接矩阵中，找到起始顶点和终点顶点对应的行和列。

将该位置的值设置为权重（如果是无向图，还需在对应对称位置设置相同权重）。

更新边数量。

4. dijkstra 函数：

功能：使用迪杰斯特拉算法计算从指定源顶点到图中所有其他顶点的最短路径。

输入参数：源顶点的索引。

操作：

初始化距离数组，将源顶点到自身的距离设为 0，到其他顶点的距离设为无穷大（或非常大的数）。

使用一个集合来跟踪已访问的顶点。

在未访问的顶点中选择距离最小的顶点，标记为已访问，并更新其相邻顶点的距离。

重复上述过程，直到所有顶点都被访问。

5. printShortestPath 函数：

功能：打印从源顶点到目标顶点的最短路径及其距离。

输入参数：

源顶点的索引。

目标顶点的索引。

操作：

根据 dijkstra 函数计算的结果，找到源顶点到目标顶点的最短路径。

打印出最短路径及其对应的距离。

6. displayMenu 函数：

功能：显示一个用户交互菜单，列出可用的操作选项。

操作：

打印菜单项，如“添加顶点”、“添加边”、“查询最短路径”和“退出”。