C++邻接矩阵实现图的深度优先遍历

本篇文档主要讲解C++中如何利用数据结构实现图的深度遍历，特别是针对邻接矩阵这一存储结构。在深度优先遍历算法的实现过程中，我们首先会定义两个关键模板类：`_edge` 和 `vertex`，以及一个名为 `graphLink` 的类，它们共同构成了图的基本结构。 1. **邻接矩阵存储结构**： 邻接矩阵是一种常见的图的存储方式，它通过一个二维数组来表示图中顶点之间的连接关系。在这个结构中，每个元素 `_nodeTable[i][j]` 表示从顶点 i 到顶点 j 是否存在边，如果存在则值为非零，不存在则为零。邻接矩阵适用于稠密图，即图中的边数接近于可能的最大边数。 2. **图的创建与初始化**： 在 `graphLink` 类中，`_graphLink(int sz=100)` 构造函数用于初始化图，其中参数 sz 定义了默认的顶点数量。该类还提供了插入顶点 (`bool insV(const T& vert)`) 和边 (`bool insE(int v1, int v2)`) 的方法，用于动态添加新的顶点和边到图中。 3. **深度优先遍历算法**： - `int getFirstNeighBor(int v)` 和 `int getNextNeighBor(int v, int w)` 分别用于获取给定顶点 v 的第一个和下一个邻居。这涉及到遍历邻接矩阵来查找与 v 相邻的顶点。 - `int getVertexPos(const T& vert)` 是一个辅助函数，用于查找给定顶点在 `_nodeTable` 中的位置，以便后续操作。 4. **模板类的定义与比较操作**： - `_edge` 类定义了一个指向 `_link` 的指针，表示边的连接，同时包含顶点编号 `_dest` 和边的权重 `_cost`。`bool operator!=(...)` 重载了不等于运算符，用于比较两个边对象是否相同。 - `vertex` 类包含顶点的数据 `T_data` 和一个指向 `_adj` 的指针，表示与该顶点相连的边集合。 5. **输入/输出操作**： 还提供了友元函数 `istream&operator>>(istream& is, _graphLink<T,E>& rhs)` 和 `ostream&operator<<(ostream& os, _graphLink<T,E>& rhs)`，允许从输入流（如 cin）读取数据到图类实例，以及将图的信息写入输出流（如 cout）。 通过这个C++代码，你可以实现对任何给定图（顶点数自定）进行邻接矩阵的构建，并进行深度优先遍历，这对于理解和处理图的连通性、路径搜索等问题非常有帮助。在实际编程中，你需要根据具体需求调用这些方法，并可能需要扩展或优化以适应更复杂的图算法。