武汉理工大学图上机实验报告.pdf

这篇实验报告是关于武汉理工大学理学院数学系的一门课程——数据结构与算法的实验，主要关注图的理论和实现。实验旨在让学生掌握在Visual C++环境下进行图的基本操作，包括理解图的邻接矩阵和邻接表的存储结构，以及深度优先遍历算法。 1. **邻接矩阵和邻接表**：在图的存储结构中，邻接矩阵是一种常用的方法，它使用二维数组来表示图中顶点之间的连接。如果存在从顶点i到顶点j的边，则邻接矩阵中的元素arcs[i][j]为非零值。对于无向图，邻接矩阵是对称的，即arcs[i][j] = arcs[j][i]。邻接表则是用链表表示每个顶点的邻接顶点，节省空间，尤其适用于稀疏图。 2. **深度优先遍历(DFS)**：这是一种图的搜索策略，从起始顶点开始，沿着边尽可能深地探索图的分支，直到访问所有可达顶点。DFS通常使用栈来实现，其基本步骤包括访问当前顶点、将其标记为已访问，然后递归地对未访问的邻接顶点进行相同操作。在C++程序中，可以实现为递归函数或者使用栈数据结构。 3. **C++程序设计**：实验报告中的代码片段展示了如何在C++中实现图的操作。例如，`Visit`函数用于输出访问的顶点，`Input`函数用于输入顶点的名称，`InputArc`和`OutputArc`处理边的信息输入和输出。`CreateUDG`函数则用于创建无向图，它需要用户输入顶点数量和边信息，然后初始化邻接矩阵。 4. **数据类型定义**：实验报告中的`Status`和`Boolean`是自定义的数据类型，分别用于表示函数返回的状态和布尔值。`MGraph`结构体封装了图的所有信息，包括顶点向量`vexs`、邻接矩阵`arcs`、顶点数`vexnum`、边数`arcnum`和图的类型`kind`。 5. **图的类型**：`GraphKind`枚举类型定义了四种图的类型：有向图(DG)，有向无环图(DN)，无向图(UDG)和无向无环图(UDN)。实验中涉及的是无向图UDG。 6. **输入输出处理**：程序中包含了从文件读取和输出到文件的函数，如`InputArcFromFile`和`OutputArc`，这对于处理大量边信息或保存和加载图的结构非常有用。 通过这个实验，学生不仅可以学习到图的抽象数据类型及其在C++中的实现，还能实践如何将算法转换为实际的计算机程序，从而提高编程和问题解决能力。此外，实验报告还强调了正确输入和输出的重要性，这对于调试和验证程序的正确性至关重要。