#include<stdio.h> #include<stdlib.h> #include<string.h> #include<limits.h> #include"ALGraph.h" #include"sqqueue.h" void BFSTraverse(ALGraph G); //按广度优先非递归遍历图G int visited[MAX_VERTEX_NUM]; // 访问标志数组(全局量) int main() { ALGraph g; CreateGraphF (g); // 利用数据文件创建图 Display(g); // 输出图 printf("广度优先遍历序列：\n"); BFSTraverse(g); return 0; } void BFSTraverse(ALGraph G) { //按广度优先非递归遍历图G。使用辅助队列Q和访问标志数组visited。 /********** Begin **********/ /********** End **********/ }

### 广度优先遍历（BFS）的实现 广度优先遍历（BFS）是一种从图中任意指定的顶点出发，按照层次依次访问所有未访问过的顶点的遍历方法。与深度优先遍历（DFS）不同，BFS 使用队列来实现对顶点的访问顺序控制。 以下是基于 ALGraph 的非递归 BFS 实现代码： #### 全局访问标志数组 在 BFS 遍历中，需要一个全局访问标志数组 `visited` 来记录每个顶点是否已被访问。初始时，所有顶点均未被访问，因此将 `visited` 数组初始化为 0[^1]。 ```c int visited[MAX_VERTEX_NUM]; // 访问标志数组(全局量) ``` #### 队列结构定义 为了实现 BFS，需要使用队列存储待访问的顶点。可以定义一个简单的队列结构： ```c typedef struct { int data[MAX_VERTEX_NUM]; int front, rear; } SqQueue; void InitQueue(SqQueue *Q) { Q->front = Q->rear = 0; } void EnQueue(SqQueue *Q, int x) { Q->data[Q->rear++] = x; } int DeQueue(SqQueue *Q) { return Q->data[Q->front++]; } int QueueEmpty(SqQueue *Q) { return Q->front == Q->rear; } ``` #### 广度优先遍历函数 以下是从指定顶点出发的 BFS 遍历实现： ```c void BFSTraverse(ALGraph G) { SqQueue Q; // 定义队列 InitQueue(&Q); // 初始化队列 // 初始化访问标志数组 for (int i = 0; i < G.vexnum; i++) { visited[i] = 0; } // 遍历所有顶点 for (int i = 0; i < G.vexnum; i++) { if (!visited[i]) { // 如果顶点未被访问 visited[i] = 1; // 标记为已访问 printf("%c ", G.Vertices[i].vexname); // 访问当前顶点 EnQueue(&Q, i); // 将当前顶点入队 while (!QueueEmpty(&Q)) { // 当队列非空时 int v = DeQueue(&Q); // 出队一个顶点 ArcNode *p = G.Vertices[v].first; // 获取该顶点的第一个邻接点 while (p != NULL) { // 遍历所有邻接点 int adjvex = p->adjvex; // 获取邻接点索引 if (!visited[adjvex]) { // 如果邻接点未被访问 visited[adjvex] = 1; // 标记为已访问 printf("%c ", G.Vertices[adjvex].vexname); // 访问邻接点 EnQueue(&Q, adjvex); // 将邻接点入队 } p = p->next; // 移动到下一个邻接点 } } } } } ``` #### 示例运行 假设输入的图如下所示： ``` 顶点：A B C D E F 边：A->B A->C B->D C->D C->E D->F E->F ``` 对应的邻接表表示为： ``` A -> B -> C B -> D C -> D -> E D -> F E -> F F -> ``` 运行结果为： ``` BFS 遍历结果：A B C D E F ``` --- ### 深度优先遍历（DFS）与广度优先遍历（BFS）的对比 - **访问顺序**：DFS 按照深度优先的方式访问顶点，尽可能深入地访问未访问过的顶点；而 BFS 按照广度优先的方式访问顶点，逐层访问图中的顶点。 - **数据结构**：DFS 使用栈（通常通过递归实现），而 BFS 使用队列来控制访问顺序。 - **应用场景**：DFS 更适合用于寻找路径或检测环路，而 BFS 更适合用于寻找最短路径或层次遍历。 --- ###