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

一、概念广度优先搜索Breadth-First SearchBFS核心思想是 “逐层遍历、先宽后深”—— 从起点出发先访问距离为 1 的所有节点再访问距离为 2 的所有节点以此类推。BFS 天然适合求解最短路径、最少步数、连通块计数等问题且能保证找到最优解。二、核心思想从起点出发先访问所有直接邻居第一层再访问邻居的邻居第二层像水波一样向外扩散直到找到目标或遍历完所有节点。举例说明如下A/B C/ \ /D E F以上是一个树形结构广度优先搜索访问顺序A → B → C → D → E → F三、BFS 核心原理核心要素队列QueueBFS 的核心数据结构用于存储待访问的节点遵循 “先进先出FIFO” 原则保证逐层遍历访问标记visited避免重复访问节点重复计算终止状态表示每个节点需记录关键信息如坐标、步数、状态值等。基本流程初始化将起点加入队列标记为已访问循环处理队列取出队首节点处理该节点如判断是否为终点、统计信息遍历该节点的所有 “邻接节点”合法、未访问的节点将邻接节点加入队列标记为已访问终止条件找到目标 → 结束并返回路径队列为空 → 无目标 / 遍历完成典型应用场景最短路径迷宫、网格、地图导航树的层序遍历按行打印二叉树连通性检测判断图是否连通、找连通分量四、C语言实现#includestdio.h#includestdlib.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-vertexv;newNode-nextNULL;returnnewNode;}// 创建图Graph*createGraph(intvNum){Graph*graph(Graph*)malloc(sizeof(Graph));graph-vertexNumvNum;for(inti0;ivNum;i){graph-adj[i]NULL;graph-visited[i]0;}returngraph;}// 添加边无向图voidaddEdge(Graph*graph,intsrc,intdest){// src - destNode*newNodecreateNode(dest);newNode-nextgraph-adj[src];graph-adj[src]newNode;// dest - srcnewNodecreateNode(src);newNode-nextgraph-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-rearMAX_VERTEX-1)return;if(q-front-1)q-front0;q-data[q-rear]val;}// 出队intdequeue(Queue*q){if(q-frontq-rear||q-front-1)return-1;returnq-data[q-front];}// 判断队列是否为空intisEmpty(Queue*q){returnq-front-1||q-frontq-rear;}// 广度优先搜索 BFSvoidbfs(Graph*graph,intstart){Queue*qcreateQueue();// 起点入队并标记访问graph-visited[start]1;enqueue(q,start);printf(BFS 遍历顺序);while(!isEmpty(q)){// 出队intcurrdequeue(q);printf(%d ,curr);// 遍历邻接节点Node*tempgraph-adj[curr];while(temp!NULL){intvtemp-vertex;if(graph-visited[v]0){graph-visited[v]1;enqueue(q,v);}temptemp-next;}}printf(\n);}// 主函数测试intmain(){// 示例图5 个顶点intvertexNum5;Graph*graphcreateGraph(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;}