C++实现图的遍历：深度优先搜索与广度优先搜索

"C++程序实现图的遍历，包括深度优先搜索（DFS）和广度优先搜索（BFS）。" 在计算机科学中，图是一种数据结构，用于表示对象之间的关系或连接。图的遍历是指按照特定顺序访问图中的每个节点。本资源提供的C++程序展示了如何使用DFS和BFS两种方法来遍历图。 1. **图的定义** 在这个程序中，图使用邻接表（Adjacency List）的数据结构来表示。邻接表是一种节省空间的图表示方式，每个节点（顶点）都有一个链表，链表中的每个元素代表与其相邻的节点。 - `AdjList` 结构体表示邻接表，包含一个整型变量 `vertex` 存储节点值，以及一个指向 `EdgeNode` 的指针 `link` 指向该节点的所有邻居。 - `EdgeNode` 结构体表示边，包含一个整型变量 `adjvex` 存储邻接节点的索引，以及一个指向下一个边的指针 `next`。 2. **构建邻接表** 函数 `build_adjlist` 用于输入图的信息并构建邻接表。它首先初始化所有节点的链接为空，然后根据用户输入的边信息添加边到邻接表中。 3. **深度优先搜索（DFS）** DFS 是一种递归的遍历方法，从给定的起始节点开始，先访问当前节点，然后依次访问未被访问过的相邻节点。在本程序中，`dfs` 函数实现了这一过程。它通过一个全局数组 `Visited` 来记录节点是否已被访问，避免重复访问，并使用递归调用来遍历所有可达节点。 4. **广度优先搜索（BFS）** BFS 使用队列（在这里是数组 `q`）进行遍历，从起始节点开始，先访问所有与起始节点相邻的未访问节点，然后再访问这些节点的相邻节点，以此类推。`bfs` 函数中，`f` 和 `r` 分别表示队列的前端和后端，`Visited` 数组同样用于标记节点是否已被访问。 5. **运行程序** 用户需要输入图的节点数 `n` 和边数 `e`，然后按顺序输入每条边的两个端点。程序会先构建邻接表，然后对指定节点执行DFS和BFS，输出遍历路径。 这个程序提供了一个基础的图遍历实现，但可以进一步优化，例如使用智能指针管理内存，或者使用STL容器如`vector`和`queue`来替代自定义的链表和数组。此外，为了处理更复杂的图，可以考虑使用邻接矩阵或其他高级图算法，如拓扑排序、最短路径等。