【入门级-算法-7、搜索算法：广度优先搜索】

一、概念
广度优先搜索（Breadth-First Search，BFS）核心思想是 “逐层遍历、先宽后深”—— 从起点出发，先访问距离为 1 的所有节点，再访问距离为 2 的所有节点，以此类推。BFS 天然适合求解最短路径、最少步数、连通块计数等问题，且能保证找到最优解。

二、核心思想
从起点出发，先访问所有直接邻居（第一层），再访问邻居的邻居（第二层），像水波一样向外扩散，直到找到目标或遍历完所有节点。
举例说明如下：
A
/
B C
/ \ /
D E F
以上是一个树形结构，广度优先搜索访问顺序：A → B → C → D → E → F

三、BFS 核心原理

1. 核心要素
   队列（Queue）：BFS 的核心数据结构，用于存储待访问的节点，遵循 “先进先出（FIFO）” 原则，保证逐层遍历；
   访问标记（visited）：避免重复访问节点，重复计算终止
   状态表示：每个节点需记录关键信息（如坐标、步数、状态值等）。
2. 基本流程
   初始化：将起点加入队列，标记为已访问；
   循环处理队列：
   取出队首节点，处理该节点（如判断是否为终点、统计信息）；
   遍历该节点的所有 “邻接节点”（合法、未访问的节点）；
   将邻接节点加入队列，标记为已访问；
   终止条件：
   找到目标 → 结束并返回路径
   队列为空 → 无目标 / 遍历完成
3. 典型应用场景
   最短路径（迷宫、网格、地图导航）
   树的层序遍历（按行打印二叉树）
   连通性检测（判断图是否连通、找连通分量）

四、C语言实现

#include<stdio.h>#include<stdlib.h>// 定义最大顶点数#defineMAX_VERTEX100// 邻接表节点结构typedefstructNode{intvertex;structNode*next;}Node;// 邻接表头结构typedefstructGraph{Node*adj[MAX_VERTEX];intvisited[MAX_VERTEX];intvertexNum;}Graph;// 队列结构（核心）typedefstructQueue{intdata[MAX_VERTEX];intfront;intrear;}Queue;// 创建新节点Node*createNode(intv){Node*newNode=(Node*)malloc(sizeof(Node));newNode->vertex=v;newNode->next=NULL;returnnewNode;}// 创建图Graph*createGraph(intvNum){Graph*graph=(Graph*)malloc(sizeof(Graph));graph->vertexNum=vNum;for(inti=0;i<vNum;i++){graph->adj[i]=NULL;graph->visited[i]=0;}returngraph;}// 添加边（无向图）voidaddEdge(Graph*graph,intsrc,intdest){// src -> destNode*newNode=createNode(dest);newNode->next=graph->adj[src];graph->adj[src]=newNode;// dest -> srcnewNode=createNode(src);newNode->next=graph->adj[dest];graph->adj[dest]=newNode;}// 初始化队列Queue*createQueue(){Queue*q=(Queue*)malloc(sizeof(Queue));q->front=-1;q->rear=-1;returnq;}// 入队voidenqueue(Queue*q,intval){if(q->rear==MAX_VERTEX-1)return;if(q->front==-1)q->front=0;q->data[++q->rear]=val;}// 出队intdequeue(Queue*q){if(q->front>q->rear||q->front==-1)return-1;returnq->data[q->front++];}// 判断队列是否为空intisEmpty(Queue*q){returnq->front==-1||q->front>q->rear;}// 广度优先搜索 BFSvoidbfs(Graph*graph,intstart){Queue*q=createQueue();// 起点入队并标记访问graph->visited[start]=1;enqueue(q,start);printf("BFS 遍历顺序：");while(!isEmpty(q)){// 出队intcurr=dequeue(q);printf("%d ",curr);// 遍历邻接节点Node*temp=graph->adj[curr];while(temp!=NULL){intv=temp->vertex;if(graph->visited[v]==0){graph->visited[v]=1;enqueue(q,v);}temp=temp->next;}}printf("\n");}// 主函数测试intmain(){// 示例图：5 个顶点intvertexNum=5;Graph*graph=createGraph(vertexNum);// 构建边addEdge(graph,0,1);addEdge(graph,0,2);addEdge(graph,1,3);addEdge(graph,1,4);addEdge(graph,2,4);// 从 0 开始 BFSbfs(graph,0);return0;}