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

"图的遍历算法设计，使用C语言实现深度优先搜索(DFS)和广度优先搜索(BFS)，并通过链表存储图结构。" 在计算机科学中，图遍历是图形理论中的一个重要概念，用于访问图中所有节点。这里我们关注的是图的深度优先遍历和广度优先遍历，这两种遍历方法常用于搜索、拓扑排序等问题。本文将详细介绍这两种遍历算法的实现。 首先，定义了两个结构体：`ARCNODE` 和 `VEXNODE`。`ARCNODE` 表示图中的边，包含一个邻接顶点（adjvex）和指向下一个边的指针（next）。`VEXNODE` 代表图中的顶点，包括顶点值（vertex）和指向第一条边的指针（firstarc）。 `adjlist` 是一个二维数组，用于存储图的邻接矩阵表示，其中 `adjlist[0]` 和 `adjlist[1]` 分别代表两种不同的图表示。这可能是为了实现两种遍历方式或处理有向图和无向图的不同。 `creatadjlist()` 函数用于创建图的邻接列表。它接受顶点数（vexnum）和边数（arcnum）作为输入，然后读取每条边的起始顶点（v1）和结束顶点（v2），通过动态分配内存创建边并将其添加到相应顶点的邻接表中。 深度优先搜索（DFS）是一种递归的遍历方法，从给定的起点开始，尽可能深地探索图的分支，直到到达叶子节点，然后再回溯。在给出的代码中，`dfs()` 函数实现了DFS。它首先打印当前顶点，然后标记该顶点已访问（将 `adjlist[0][v].vertex` 设置为1），接着遍历与当前顶点相连的所有未访问顶点，并对它们递归调用 `dfs()`。 DFS 的主要优点是空间效率高，因为它只需要一个栈来保存待回溯的节点。缺点是在某些情况下可能会导致较深的递归，可能会导致栈溢出。 广度优先搜索（BFS）则使用队列进行遍历，从起点开始，先访问所有相邻的未访问节点，再访问这些节点的相邻节点，以此类推。由于此代码中没有提供BFS的实现，我们可以简单描述其步骤： 1. 将起始节点放入队列。 2. 创建一个空集合，记录已访问的节点。 3. 当队列非空时，取出队首节点，访问它，并将它加入已访问集合。 4. 将该节点的所有未访问邻居入队。 5. 重复步骤3和4，直到队列为空。 BFS 的优点是它能找到最短路径（对于无权图），并且不会导致深度递归。缺点是需要额外的空间来存储队列。 总结，这段代码提供了图的邻接列表表示以及深度优先遍历的实现。要实现广度优先遍历，可以按照上述BFS的逻辑编写一个新函数。在实际应用中，根据问题需求选择合适的遍历策略，如在寻找最短路径或避免深度递归时，通常会选择BFS。