C语言实现邻接矩阵图的深度优先遍历(DFS)

本文主要介绍了如何使用C语言通过邻接矩阵来实现图的深度优先遍历（DFS）。其中，提供了相关的数据结构定义、函数接口以及一个简单的裁判测试程序。 在图论中，深度优先遍历是一种用于遍历或搜索树或图的方法。它从根节点开始，然后尽可能深地搜索树的分支，直到找到目标节点或达到最大深度。在图中，深度优先遍历通常通过递归方式完成，沿着边逐个访问未访问过的邻接顶点。 在这个问题中，图被存储为一个邻接矩阵`G`，由`MGraph`结构体定义。`MGraph`包含三个成员：`Nv`表示顶点的数量，`Ne`表示边的数量，以及一个二维数组`G`，用于存储图的权重信息。邻接矩阵`G[i][j]`的值表示顶点i到顶点j的边的权重，如果存在边，则非零，否则为0。 `DFS`函数是实现深度优先遍历的核心，它接受三个参数：`MGraph Graph`表示图，`Vertex V`表示开始遍历的顶点，`void (*Visit)(Vertex)`是一个回调函数指针，用于在访问每个顶点时执行特定操作，例如打印顶点编号。 `Visit`函数是一个简单的示例，它只是打印出被访问的顶点的编号。在实际应用中，这个函数可以执行更复杂的操作，如记录路径、计算最短路径等。 深度优先遍历的步骤如下： 1. 从指定的顶点V开始，设置当前顶点为已访问（通过`Visited[V] = true`）。 2. 调用`Visit(V)`来处理（访问）当前顶点。 3. 遍历V的所有邻接顶点U（即与V有边相连的顶点），如果U未被访问过（`Visited[U] == false`），则递归调用`DFS(Graph, U, Visit)`。 4. 完成当前顶点所有邻接顶点的处理后，回溯到上一顶点。 在裁判提供的测试程序中，`CreateGraph()`函数创建图并初始化`Visited`数组，而`main()`函数读取用户输入的起始顶点V，然后调用`DFS()`进行遍历，并打印出结果。 在实现深度优先遍历时，需要注意以下几点： - 访问标记数组`Visited`的初始化非常重要，确保每个顶点在遍历开始前都被标记为未访问。 - 递归调用`DFS()`时，必须检查邻接顶点是否已被访问，防止无限循环。 - 当没有更多未访问的邻接顶点时，递归返回上一层，继续处理其他顶点。 这种基于邻接矩阵的深度优先遍历方法适用于稠密图，即边的数量接近于顶点数量的平方。对于稀疏图，使用邻接表可能更节省空间。