Turbo C中无向图非递归遍历算法详解及数据结构实现

本篇文章主要探讨了在C语言中使用Turbo C编译器实现无向图的非递归遍历。主要内容围绕以下几个关键知识点展开： 1. 数据结构定义： 文章首先定义了一个名为`Graph`的数据结构，它包含两个主要部分：`V`数组表示顶点，存储每个顶点的值（整型，范围为1到`M`）；`R`二维数组表示邻接矩阵，用于表示图中各个顶点之间的连接关系，其中`R[i][j] = 1`表示顶点`i`与`j`之间有边。 2. 图的创建函数`creatgraph`： 函数接受一个`Graph`指针和顶点数量`n`作为输入参数。它初始化`V`数组并将所有顶点赋值为1到`n`，然后填充邻接矩阵`R`为全零。用户通过输入`r1`和`r2`来指定边的存在，确保图是无向的（即每条边双向连接）。 3. 打印图函数`printgraph`： 该函数用于显示图的邻接矩阵，通过遍历`R`数组并打印元素，展示图的结构。 4. 遍历算法： 文章的核心部分涉及非递归遍历，使用深度优先搜索（DFS）算法。首先定义一个`visited`数组用于标记已访问的顶点。`visitvex`函数负责打印当前访问的顶点值，`firstadjvex`函数寻找与给定顶点`vex`相邻且未访问过的第一个顶点，`nextadjvex`则递归地找到下一个未访问的邻居。 5. 深度优先搜索（DFS）： `dfs`函数是实现无向图遍历的关键，它接收一个`Graph`指针和起始顶点`vex`。函数内部将`vex`标记为已访问，然后通过调用`firstadjvex`和`nextadjvex`递归地访问其所有邻居，直到遍历完整个连通分量。 总结来说，本文提供了一种使用C语言和Turbo C编译器实现无向图非递归遍历的方法，利用邻接矩阵和深度优先搜索算法来探索图中的节点。这对于理解图论基础以及如何在实际编程中处理数据结构具有重要意义。