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

本文档介绍了一种使用C++实现图的遍历方法，包括深度优先搜索(DFS)和广度优先搜索(BFS)。代码示例展示了如何构建邻接链表表示图，并进行遍历。 在计算机科学中，图是一种数据结构，用于表示对象之间的关系。图由顶点（或节点）和边（或连接）组成。遍历图是指从一个特定顶点出发，按照某种顺序访问图中的所有顶点。常用的遍历方法有两种：深度优先搜索和广度优先搜索。 深度优先搜索(DFS)是一种递归的遍历策略，它首先访问当前节点，然后尽可能深地探索图的分支，直到到达叶子节点（无相邻节点的节点），再回溯到最近的未访问节点，继续进行下一次访问。DFS通常使用栈来辅助实现。 广度优先搜索(BFS)则是从起始顶点开始，逐层地访问所有相邻节点，先访问离起始顶点近的节点，再访问远的节点。BFS通常使用队列来辅助实现。 给定的代码示例首先定义了一个`node`结构体，用于存储图的顶点信息，包括数据、标志（表示是否已访问过）和指向下一个顶点的指针。`creategraph`函数用于创建图，通过输入的顶点数量和边的信息，构建邻接链表。用户输入的两个顶点编号表示一条边，代码会更新相应的邻接链表，增加边的数量，并确保边的双向性。 深度优先搜索和广度优先搜索的具体实现没有在给出的代码中展示，但通常可以使用以下方式实现： 1. 深度优先搜索(DFS)： - 使用栈存储待访问的顶点。 - 从起始顶点开始，将顶点入栈，并标记为已访问。 - 当栈不为空时，弹出栈顶顶点，访问该顶点，然后将其所有未访问过的邻接顶点入栈。 - 重复以上步骤，直到栈为空。 2. 广度优先搜索(BFS)： - 使用队列存储待访问的顶点。 - 将起始顶点入队，并标记为已访问。 - 当队列不为空时，出队一个顶点，访问该顶点，然后将其所有未访问过的邻接顶点入队。 - 重复以上步骤，直到队列为空。 在实际应用中，DFS和BFS各有优缺点。DFS适合寻找最短路径问题（如求解迷宫），而BFS则常用于找到最小生成树（如Prim算法）或者最近公共祖先等问题。理解并掌握这两种遍历方法对于解决图论问题至关重要。