基于邻接矩阵表示的广度优先遍历。 基于邻接矩阵表示的广度优先遍历。 #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( 2 分 ){ u= 2 分 ; for(w = 0; w < G.vexnum; w++){ if( 2 分 ) { printf("%c ",G.vexs[w]); visited[w] = 1; 2 分 =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) #include <stdio.h> #include <stdlib.h> #define MVNum 100

### 基于邻接矩阵的广度优先遍历 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]。 --- ###