C++实现：邻接矩阵表示无向图及深度遍历

"这篇文档是关于使用C++和Visual C++实现数据结构中的无向图表示，特别是通过邻接矩阵的方式，并进行深度遍历的方法。文档包含了一个完整的程序实例，涵盖了从用户输入图的顶点和边，到构建邻接矩阵，以及显示图的结构和进行深度遍历的步骤。" 在数据结构中，无向图是一种非线性结构，其中的边连接两个顶点，而这两个顶点没有方向性。邻接矩阵是表示无向图的一种常见方法，它是一个二维数组，用于存储图中任意两个顶点之间是否存在边。对于无向图，邻接矩阵是对称的，即如果节点i和节点j之间有一条边，那么矩阵的arcs[i][j]和arcs[j][i]都将被设置为1。 在提供的代码中，定义了名为`MGraph`的结构体，它包含了顶点表（vexs）和邻接矩阵（arcs），以及图的顶点数（vexnum）和边数（arcnum）。`LocateVex`函数用于根据给定的顶点名字找到其在顶点表中的位置，以便在邻接矩阵中进行操作。`CreateUDN`函数则负责创建无向图，从用户那里获取顶点和边的信息，并构造邻接矩阵。最后，`ShowG`函数用于显示图的顶点和边的邻接矩阵，以可视化图的结构。 深度优先遍历（DFS）是图遍历的一种策略，它从一个起点开始，沿着图的边尽可能深地搜索，直到到达叶子节点（没有未访问过的邻接节点的节点），然后回溯到最近的未访问节点，继续搜索。在无向图的邻接矩阵表示中，DFS可以通过递归或栈来实现。然而，这个文档并没有提供具体的DFS实现，但通常会包括一个递归函数，从当前节点开始遍历所有与之相邻的节点，并标记它们为已访问，以避免无限循环。 为了实现深度遍历，可以创建一个递归函数，例如： ```cpp void DFS(MGraph& G, int u, bool visited[MAX]) { visited[u] = true; cout << G.vexs[u] << " "; // 输出当前访问的顶点 for (int v = 0; v < G.vexnum; v++) { if (G.arcs[u][v] == 1 && !visited[v]) { // 如果有边且顶点未访问 DFS(G, v, visited); // 递归访问顶点v } } } int main() { MGraph G; CreateUDN(G); bool visited[MAX] = { false }; DFS(G, 0, visited); // 从0号顶点开始遍历 return 0; } ``` 这个程序首先创建一个图，然后使用DFS函数从第一个顶点开始遍历整个图。在`DFS`函数中，我们标记每个访问过的顶点，以确保不重复访问，并通过邻接矩阵判断是否应该继续深入遍历。 这个文档提供了一个基础的框架，用于使用C++和邻接矩阵表示无向图，并提示了如何构建和显示图的结构。然而，要实现深度遍历，还需要进一步补充代码。