邻接表实现图的深度优先与广度优先遍历

"本文档提供了一段C语言代码，用于实现图的邻接表数据结构以及深度优先遍历（DFS）和广度优先遍历（BFS）算法。" 这段代码定义了图的相关数据结构和操作，包括节点、边、队列等。邻接表是一种表示图的有效方式，尤其适用于稀疏图，它为每个顶点存储一个链表，链表中的元素表示与该顶点相邻的其他顶点。 1. 定义的数据结构： - `Node` 结构体表示队列中的节点，包含一个整型元素和一个指向下一个节点的指针。 - `Queue` 结构体表示一个简单的环形队列，包含队首和队尾指针。 - `ArcNode` 表示图中的一条边，包含指向相邻顶点的索引和指向下一个边的指针。 - `VNode` 表示图中的一个顶点，包含顶点信息和指向第一条相邻边的指针。 - `AdjList` 是一个顶点数组，用于存储邻接表。 - `Graph` 结构体包含了邻接表、顶点数量和边的数量。 2. 基本操作函数： - `InitQueue` 初始化一个空队列。 - `EnQueue` 向队列中添加元素。 - `DeQueue` 从队列中移除并返回队首元素。 - `QueueEmpty` 检查队列是否为空。 - `LocateVex` 查找指定顶点在图中的位置。 - `CreateGraph` 以邻接表形式创建一个无向连通图，读取用户输入的顶点和边信息。 - `FirstAdjVex` 获取指定顶点的第一个相邻顶点。 - `NextAdjVex` 获取指定顶点相对于当前相邻顶点的下一个相邻顶点。 - `DFS` 深度优先遍历，访问一个顶点及其所有未访问的邻接顶点。 - `DFSTraverse` 对整个图进行深度优先遍历。 - `BFSTraverse` 广度优先遍历，使用队列进行层次遍历。 3. 图的遍历： - 深度优先遍历（DFS）：从一个未访问的顶点开始，递归地访问其所有邻接顶点，直到所有顶点都被访问。在此代码中，DFS通过标记已访问的顶点来避免重复访问。 - 广度优先遍历（BFS）：从一个顶点开始，按层次顺序访问其邻接顶点。BFS使用队列来保持待访问的顶点顺序。 这段代码是实现图遍历的基础，可以用于解决各种问题，如查找最短路径、检测连通性等。在实际应用中，可能需要根据具体需求对代码进行适当的修改和扩展。