C++实现图的深度优先搜索(DFS)算法

"本文介绍了一种C++实现的图的深度优先遍历算法，以及如何创建无向图（Undirected Graph，UDG）的数据结构。" 在计算机科学中，图是一种重要的数据结构，用于表示对象之间的关系。图由顶点（vertices）和边（edges）组成，可以用来模拟各种复杂的关系，如网络、社交网络、文件系统等。深度优先遍历（Depth First Search, DFS）是图的一种遍历策略，它从一个起点开始，尽可能深地探索图的分支，直到到达叶子节点，然后回溯到最近未访问的节点，继续深入另一个分支。 在给定的代码中，首先定义了几个常量和类型定义，如`TRUE`和`FALSE`表示布尔值，`MAX_NAME`表示最大顶点名称长度，`MAX_VERTEX_NUM`表示图的最大顶点数。`AdjMatrix`定义了一个邻接矩阵，用于存储图的边信息，每个`ArcCell`包含一个整型`adj`表示边的存在（1表示存在，0表示不存在），以及指向附加信息的指针`info`。 接下来，定义了`MGraph`结构体，它包含了图的顶点数组`vexs`、邻接矩阵`arcs`，以及顶点数`vexnum`和边数`arcnum`。 `LocateVex`函数用于在图中找到指定顶点的索引。它遍历`vexs`数组，通过`strcmp`函数比较输入的顶点名称与数组中的元素，如果匹配则返回索引，否则返回-1。 `CreateUDG`函数创建了一个无向图。用户输入顶点数和边数，接着输入顶点的名称，然后输入边的连接信息（两个顶点的名称）。`CreateUDG`使用邻接矩阵来存储这些信息，其中`adj`值设置为1表示存在一条边，因为是无向图，所以边的两端都标记为1。 深度优先遍历的算法通常包括以下步骤： 1. 从任意顶点开始，将其标记为已访问。 2. 访问该顶点，并递归地访问所有未访问的邻接顶点。 3. 回溯到上一个顶点，继续访问其他未访问的邻接顶点，直到所有可达顶点都被访问。 在C++中，可以使用递归或栈来实现DFS。由于提供的代码片段中没有实际的DFS实现，我们可以补充一个基本的DFS函数： ```cpp void DFS(MGraph G, int start) { Boolean visited[MAX_VERTEX_NUM] = {0}; // 初始化所有顶点为未访问 visited[start] = TRUE; printf("访问顶点: %s\n", G.vexs[start]); for (int i = 0; i < G.vexnum; ++i) { if (G.arcs[start][i].adj && !visited[i]) { DFS(G, i); } } } int main() { MGraph G; CreateUDG(&G); DFS(G, 0); // 从第一个顶点开始遍历 return 0; } ``` 这个`DFS`函数首先初始化一个布尔数组`visited`来跟踪每个顶点的访问状态，然后从给定的起始顶点开始遍历，访问所有可达的未访问顶点。 总结来说，这段代码提供了创建无向图的数据结构和基础操作，但没有实现完整的深度优先遍历。要完成遍历，需要添加上述的DFS函数，或者根据具体需求进行相应的修改和扩展。