基于邻接矩阵表示的广度优先遍历。 #include <stdio.h> #include <stdlib.h> #define MVNum 100 int visited[MVNum]; typedef struct{ char vexs[MVNum]; int arcs[MVNum][MVNum]; int vexnum,arcnum; }Graph; void CreateUDN(Graph &G);//实现细节隐藏 void BFS(Graph G, int v){ char Q[MVNum]; int f=0,r=0; int u,w; printf("%c ",G.vexs[v]); visited[v] = 1; Q[r++]=v; while( ){ u= ; for(w = 0; w < G.vexnum; w++){ if( ) { printf("%c ",G.vexs[w]); visited[w] = 1; =w; } } } } void BFSTraverse(Graph G){ int v; for(v = 0; v < G.vexnum; ++v) visited[v] = 0; for(v = 0; v < G.vexnum; ++v) if(!visited[v]) BFS(G, v); } int main(){ Graph G; CreateUDN(G); BFSTraverse(G); return 0; }

### 基于邻接矩阵的广度优先遍历 C语言实现 以下是基于邻接矩阵表示的广度优先遍历（Breadth First Search, BFS）的C语言实现及其详细解释： #### 完整代码实现 ```c #include <stdio.h> #define MAX_VERTEX 100 // 最大顶点数 // 初始化访问标记数组 void initVisited(int visited[], int vertexNum) { for (int i = 0; i < vertexNum; i++) { visited[i] = 0; } } // 队列定义及相关操作 typedef struct QueueNode { int data[MAX_VERTEX]; int front, rear; } SqQueue; void InitQueue(SqQueue *Q) { Q->front = Q->rear = 0; } int IsEmptyQueue(SqQueue *Q) { return Q->front == Q->rear ? 1 : 0; } void EnQueue(SqQueue *Q, int value) { if ((Q->rear + 1) % MAX_VERTEX == Q->front) { // 队满处理 printf("Error: The queue is full.\n"); return; } Q->data[Q->rear] = value; Q->rear = (Q->rear + 1) % MAX_VERTEX; } int DeQueue(SqQueue *Q) { if (IsEmptyQueue(Q)) { // 队空处理 printf("Error: The queue is empty.\n"); return -1; } int value = Q->data[Q->front]; Q->front = (Q->front + 1) % MAX_VERTEX; return value; } // 访问函数，用于打印当前节点 void visit(char vertex[], int v) { printf("%c ", vertex[v]); } // 广度优先遍历函数 void BFSTraverse(int arc[][MAX_VERTEX], char vertex[], int vertexNum, int startVertex) { int visited[vertexNum]; // 记录各顶点是否被访问过 initVisited(visited, vertexNum); SqQueue Q; InitQueue(&Q); visit(vertex, startVertex); // 输出起点信息 visited[startVertex] = 1; // 标记已访问 EnQueue(&Q, startVertex); // 起点入队 while (!IsEmptyQueue(&Q)) { // 当队列不为空时继续循环 int currentVertex = DeQueue(&Q); // 出队 for (int neighbor = 0; neighbor < vertexNum; neighbor++) { if (arc[currentVertex][neighbor] == 1 && !visited[neighbor]) { // 如果未访问且有边相连 visit(vertex, neighbor); // 访问邻居节点 visited[neighbor] = 1; // 标记为已访问 EnQueue(&Q, neighbor); // 将邻居节点加入队列 } } } } // 主程序测试 int main() { int graph[MAX_VERTEX][MAX_VERTEX] = { {0, 1, 1, 0}, {1, 0, 0, 1}, {1, 0, 0, 1}, {0, 1, 1, 0} }; char vertices[] = {'A', 'B', 'C', 'D'}; int numVertices = sizeof(vertices) / sizeof(vertices[0]); printf("BFS Traversal starting from A:\n"); BFSTraverse(graph, vertices, numVertices, 0); // 从顶点'A'开始遍历 printf("\n"); return 0; } ``` --- #### 代码详解 1. **初始化访问标志数组** 使用`initVisited`函数将所有顶点的访问状态设置为未访问（即置零）。这一步是为了确保每次调用BFS前都能正确重置访问记录。 2. **队列的操作** 实现了一个简单的环形队列结构体`SqQueue`以及其基本操作： - `InitQueue`: 初始化队列。 - `EnQueue`: 向队列尾部插入元素。如果队列为满则报错退出。 - `DeQueue`: 删除队首元素并返回值。如果队列为空则报错退出。 3. **核心逻辑——BFSTraverse** - 创建一个布尔型数组`visited`来跟踪哪些顶点已被访问。初始状态下全部设为未访问。 - 利用辅助队列存储待访问的顶点编号，并按照先进先出的原则逐一扩展这些顶点的所有直接连通顶点。 - 对每个新发现的顶点执行如下动作： - 打印该顶点的信息； - 设置对应位置的`visited`标志位为真； - 把它压入队列等待后续进一步探索其他关联节点[^1]。 4. **主函数部分** 构造了一张小型无向图作为输入样例展示如何调用上述功能完成整个流程演示[^3]。 --- ###

### 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]。