C语言实现图的深度与广度优先遍历算法

本篇代码是用C语言实现的图的深度优先遍历（Depth First Search, DFS）和广度优先遍历（Breadth First Search, BFS）算法。首先，我们定义了两个结构体：`vnode`用于表示图中的节点，包含节点数据和指向下一个节点的指针；`Queue`则是一个队列，用于在BFS中实现节点的层次访问。 程序的核心部分包括以下几个函数： 1. `InitQueue()`：初始化队列，将队列的前端和后端都设为NULL。 2. `QueueEmpty()`：检查队列是否为空，通过比较前端和后端指针来判断。 3. `EnQueue()`：向队列末尾添加元素，采用循环索引避免数组溢出。 4. `DeQueue()`：从队列头部取出元素并返回，更新队列前端。 5. `creat()`：函数用于创建图，输入节点数量n和边的数量e。这里采用了邻接表的形式存储图，对于每条边，分别在起点和终点添加双向链表，以便于遍历。 6. `DFS()` 和 `BFS()`：这两个函数分别是深度优先和广度优先遍历的实现。DFS遍历时，通常从一个起始节点开始，递归地访问所有可达的节点。BFS则是逐层访问节点，先访问距离起点最近的节点，再逐渐扩展到更远的节点。 在`DFS`中，代码会先打印节点的编号，然后遍历当前节点的所有邻接节点，直到没有未访问过的节点为止。这体现了深度优先搜索的特点，即深入一条路径直到不能再前进，再转向其他路径。 在`BFS`部分，代码使用了队列来保持节点的顺序，从起点开始，先访问队列的第一个节点（距离起点最近的节点），再将其相邻节点加入队列，形成逐层遍历的结构。这种方式确保了最先访问的是最短路径上的节点。 这段代码提供了一个实用的工具，帮助学习者理解和实现图的深度优先和广度优先遍历算法，这对于理解和解决许多实际问题中的图论问题非常有帮助，比如寻找最短路径、连通性分析等。理解这些基本的遍历策略是数据结构和算法学习的重要组成部分。