#include<stdio.h> #include<stdlib.h> #include<string.h> #include<limits.h> #include"MGraph.h" #include"sqqueue.h" void BFSTraverse(MGraph G);// 图G存在，从第1个顶点起，按广度优先非递归遍历图G,并对每个顶点调用函数… /********** End **********/ }

### C语言中的图广度优先遍历（BFS）非递归实现 在C语言中，可以通过队列来实现图的广度优先遍历（BFS）。以下是基于邻接矩阵表示法 `MGraph` 和顺序队列 `sqqueue` 的具体实现方法。对于每个访问到的顶点，可以调用指定的函数。 #### 数据结构定义 为了便于理解，先定义两个数据结构：一个是用于存储图的邻接矩阵 `MGraph`；另一个是用于辅助操作的顺序队列 `SqQueue`。 ```c #define MAX_VERTEX_NUM 20 // 假设最大顶点数为20 typedef struct { char vexs[MAX_VERTEX_NUM]; // 存储顶点信息 int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵 int vexnum, arcnum; // 当前顶点数和边数 } MGraph; // 定义顺序队列 SqQueue #define QUEUE_SIZE 100 // 队列大小 typedef struct { int data[QUEUE_SIZE]; int front, rear; } SqQueue; ``` #### 初始化队列 初始化顺序队列以便后续使用： ```c void InitQueue(SqQueue *Q) { Q->front = Q->rear = 0; // 初始时前后指针均置零 } int QueueEmpty(SqQueue Q) { // 判断队列是否为空 return (Q.front == Q.rear); } // 入队操作 void EnQueue(SqQueue *Q, int e) { if ((Q->rear + 1) % QUEUE_SIZE == Q->front) { printf("Queue is full\n"); return; } Q->data[Q->rear] = e; Q->rear = (Q->rear + 1) % QUEUE_SIZE; } // 出队操作 int DeQueue(SqQueue *Q) { if (QueueEmpty(*Q)) { printf("Queue is empty\n"); return -1; // 返回错误标志 } int e = Q->data[Q->front]; Q->front = (Q->front + 1) % QUEUE_SIZE; return e; } ``` #### 广度优先遍历算法 下面是一个完整的广度优先遍历（BFS）实现，其中会针对每一个被访问的节点调用给定的函数 `visit()`。 ```c #include <stdio.h> // 访问某个顶点的操作 void visit(int v) { printf("Visited vertex: %d\n", v); // 输出当前访问的顶点编号 } // 广度优先搜索 void BFSTraverse(MGraph G, void (*visit)(int)) { int visited[MAX_VERTEX_NUM] = {0}; // 创建并初始化已访问数组 SqQueue Q; InitQueue(&Q); for (int i = 0; i < G.vexnum; ++i) { // 对每个未访问过的连通分量执行BFS if (!visited[i]) { visit(i); // 访问起始顶点 visited[i] = 1; // 设置该顶点已被访问 EnQueue(&Q, i); // 将其加入队列 while (!QueueEmpty(Q)) { // 只要队列不空就继续处理下一个层 int u = DeQueue(&Q); // 获取队首元素u，并将其移除队列 for (int w = 0; w < G.vexnum; ++w) { // 找出所有与u相邻且尚未访问的顶点 if (G.arcs[u][w] && !visited[w]) { visit(w); // 访问新找到的顶点w visited[w] = 1; // 标记它已经被访问过 EnQueue(&Q, w); // 加入队列等待进一步扩展 } } } } } } ``` 以上代码实现了对任意无向图或者有向图进行广度优先遍历时的功能[^1]。通过调整参数传递方式还可以支持更多自定义行为。 #### 测试程序片段 假设我们有一个简单的四节点完全图作为测试对象，则可按如下方式进行验证： ```c int main() { MGraph graph; // 构建一个简单例子... graph.vexnum = 4; graph.arcnum = 6; strcpy(graph.vexs,"ABCD"); /* 设定弧 */ memset(graph.arcs, 0, sizeof(graph.arcs)); graph.arcs[0][1]=graph.arcs[0][2]=graph.arcs[0][3]=1; graph.arcs[1][0]=graph.arcs[1][2]=graph.arcs[1][3]=1; graph.arcs[2][0]=graph.arcs[2][1]=graph.arcs[2][3]=1; graph.arcs[3][0]=graph.arcs[3][1]=graph.arcs[3][2]=1; BFSTraverse(graph, &visit); return 0; } ``` 此段代码展示了如何创建一个小规模的全连接网络以及对其应用前述编写的广度优先搜索逻辑[^2]。