合肥工业大学图论实验：邻接矩阵与邻接表

"本实验主要关注图数据结构的掌握，包括图的基本概念、存储结构（邻接矩阵和邻接表）以及两种遍历算法（深度优先遍历和广度优先遍历）。实验还要求计算图中边的数量。" 在计算机科学中，图是一种重要的抽象数据类型，用于表示对象之间的关系。实验的目的是让学生熟悉并能够实现图的相关操作。以下是实验涉及的具体知识点： 1. **图的基本概念**：图由顶点（vertices）和边（edges）组成，边连接两个顶点，表示它们之间的关系。图可以是无向的（边没有方向）或有向的（边有方向）；可以是加权的（边附带数值）或无权的（边无数值）。 2. **邻接矩阵**：这是一种二维数组的存储结构，用于表示图中顶点之间的邻接关系。如果顶点i和j之间存在边，那么邻接矩阵中的元素`edge[i][j]`（或`edge[j][i]`对于无向图）为1，否则为0。邻接矩阵适用于所有顶点之间关系都需要频繁查询的情况，但空间效率较低，因为即使没有边也会占用空间。 3. **邻接表**：相比于邻接矩阵，邻接表更节省空间，尤其当图稀疏（边数远小于顶点数的平方）时。它为每个顶点维护一个链表，链表中的节点代表与其相邻的其他顶点。邻接表在进行遍历和查找特定邻接关系时效率更高。 4. **深度优先遍历（DFS）**：从某个顶点出发，沿着某条路径一直走下去，直到无法再深入，然后回溯到上一个顶点，选择未访问的邻接顶点继续深入。DFS使用栈来辅助实现，适用于寻找树的分支结构或判断图的连通性。 5. **广度优先遍历（BFS）**：从起点开始，逐层访问所有相邻的顶点，然后再访问下一层的顶点。BFS使用队列来辅助实现，通常用于找出图中两点之间的最短路径。 6. **边数的计算**：在邻接矩阵中，边数可以通过计算非零元素的个数得出；在邻接表中，可以通过遍历所有顶点的邻接链表，统计链表的长度之和得到。 7. **程序实现**：给出的代码片段是一个简单的C++类`graph`，包含了构造函数、创建邻接矩阵、DFS和BFS遍历、访问标记数组以及计算边数等方法。在实际编程中，还需要考虑输入处理、错误检查以及可能的优化。 8. **Dijkstra算法**：虽然在摘要中未明确提及，但在类`graph`中包含了一个`dijkstra`方法，这通常是用来解决单源最短路径问题的算法。Dijkstra算法从一个源顶点开始，逐步扩展找到到所有顶点的最短路径，它通常与优先队列（如二叉堆）一起使用。 这个实验旨在通过实践加深对图数据结构的理解，掌握其存储和遍历算法，以及如何在实际问题中应用这些知识。在完成实验后，学生应能熟练地处理与图相关的各种问题。