C语言实现图的邻接矩阵与链表存储下的深度/广度优先遍历

本篇文章主要探讨了图的存储与遍历在C语言中的实现，针对两种不同的图数据结构——邻接矩阵和邻接链表，分别介绍了如何进行深度优先遍历（DFS）和广度优先遍历（BFS）。以下是对文章核心知识点的详细解析： 1. 图的存储结构： - **邻接矩阵**：作者使用一个二维数组`edges`来表示图的邻接关系，其中`edges[i][j]`表示顶点`i`和`j`之间是否有边。`vexs`数组则用于存储每个顶点的名称或标识符。 2. 图的创建函数`CreateGraph`： - 函数接受两个输入参数，即顶点数量`vexnum`和边的数量`arcnum`。 - 用户通过交互式输入方式为每个顶点赋值，并记录它们的名称。 - 邻接矩阵初始化为全零，用户随后输入边的信息，如果边连接的是已知的顶点，则对应的邻接矩阵元素设置为1，表示存在边。 3. **深度优先遍历（DFS）**： - `Depth`函数实现了深度优先遍历算法，它首先访问一个未访问过的顶点（`i`），并将其标记为已访问（这里省略了对`visited`数组的更新，但通常会在访问后将其设为`TRUE`）。 - 然后递归地遍历其相邻且未访问过的顶点（`j`），直到所有可达路径都被探索。 4. **深度优先搜索（DFS）函数`Depthsearch`**： - 函数初始化`visited`数组为全`FALSE`，然后从所有未访问的顶点开始调用`Depth`函数进行遍历。 - 这个过程确保了先访问最近的顶点，从而实现了深度优先搜索的效果。 5. **邻接链表**： - 文章没有提供邻接链表的详细实现，但可以推测，邻接链表通常会用一个节点结构来存储每个顶点及其连接的顶点列表，这样在查找邻接顶点时效率更高，特别是对于稀疏图。 6. **广度优先遍历（BFS）**： - 文中虽然没有给出邻接链表版本的BFS实现，但理解BFS通常是通过队列数据结构来逐层扩展节点，首先访问起始顶点，然后按顺序访问其相邻的未访问顶点，这种方式保证了遍历路径是最短的。 这篇文章提供了C语言实现图的两种存储结构以及相应的深度优先和广度优先遍历方法。通过邻接矩阵的方式，适合于内存占用较大但查询相邻顶点快速的情况；而邻接链表则更适合于查询频繁且图较稀疏的场景。理解和掌握这些基本概念和技术对于理解和设计高效的图算法至关重要。