C++实现图的深度优先遍历(DFS)

本文主要介绍了如何在C++中实现图的深度优先遍历(DFS)。深度优先遍历是一种用于遍历或搜索树或图的算法，它沿着树的深度尽可能深地搜索，直到找到目标节点或者遍历完所有节点。 在给定的代码中，首先定义了两个结构体`ArcNode`和`VNode`，它们分别表示图中的边（Arc）和顶点（Vertex）。`ArcNode`结构体包含一个整型变量`adjVex`，表示边连接的相邻顶点的索引，以及一个指向下一个相邻顶点的指针`nextArc`。`VNode`结构体则包含了顶点的数据（`char data`）和指向第一条相邻边的指针（`ArcNode* firstArc`）。 接着，定义了一个名为`AlGraph`的结构体，用于存储整个图的信息。`AlGraph`包含一个`AdjList`类型的数组`vertices`，表示图中的所有顶点，以及两个整型变量`vexnum`和`arcnum`，分别记录顶点数量和边的数量。 `DFS`函数是深度优先遍历的核心部分。它接受一个`AlGraph`类型的图`G`和一个顶点索引`v`作为参数。在函数内部，首先将当前访问的顶点标记为已访问（`visit = true`），然后输出顶点数据。接下来，通过`FirstAdjVex`和`NextAdjVex`函数遍历所有与当前顶点相邻的未访问顶点，并递归调用`DFS`进行深度遍历。 在`main`函数中，创建了一个邻接矩阵`a`来表示图的连接关系，然后初始化了一个`AlGraph`结构体`G`，包括其顶点数据、边的数量和顶点的数量。对于每个顶点，根据邻接矩阵创建了相应的边链表，并将其设置为顶点的第一个相邻边。 在实际的图处理中，`FirstAdjVex`和`NextAdjVex`函数通常用于获取顶点的第一个相邻顶点和下一个相邻顶点。这两个函数没有在提供的代码中定义，但在实际应用中需要根据具体图的结构来实现。例如，`FirstAdjVex`可以返回顶点的第一个相邻边的`adjVex`，而`NextAdjVex`则返回当前边的下一个相邻边的`adjVex`。 这段C++代码展示了如何构建一个图的邻接表表示，并利用深度优先遍历算法对图进行遍历。这个例子特别适用于理解图遍历的概念，以及如何在C++中操作结构体和指针来实现图的抽象数据类型。