概述:
广度优先搜索(也称宽度优先搜索,缩写BFS)是连通图的一种遍历策略。因为它的思想是从一个顶点V0开始,辐射状地(就和MC中的水一个样)遍历其周围较广的区域,故得名。
广搜是一种用于图形搜索和遍历的算法,它从起始节点开始,依次访问其相邻节点,然后再依次访问这些节点的相邻节点,以此类推,直到找到目标节点或者遍历了整个图形。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
模板:
1. 定义一个节点数据结构
其中x、y记录当前节点的位置,step记录步数。
2. 定义地图数组、标记数组和方向数组。
P. S:方向数组视情况而定,有时情况更加复杂
3.BFS函数
过程:
1. 将起始节点标记为已访问,并将其加入到队列中。
2. 当队列不为空时,从队列的头部取出一个节点,依次访问它的相邻节点。
3. 如果相邻节点未被访问,则将其标记为已访问,并将其加入到队列的尾部。
4. 重复步骤2和步骤3,直到队列为空或者找到目标节点。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
标程:
输入:第1行输入地图的行数n和列数m,第2行输入起点坐标(sx, sy),第3行终点坐标(ex, ey),此后的n行输入一个地图(.表示通道,#表示墙)
输出:从起点到终点的最少步数,若无法到达则输出−1-1−1
数据范围:n,m≤500n,m ≤500n,m≤500 且 sx,ex≤nsx,ex≤nsx,ex≤n 且 sy,ey≤msy,ey≤msy,ey≤m
样例输入:
样例输出:
这是一道最短路径的模板题,许多题目的代码和这道题基本完全一样,不过是换了一种表述。
实现代码如下:
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
图中的BFS(例题为树上两点之间的距离,来自信友队):
题目描述:
给你一棵无根树,求树上两个点之间的距离。
输入格式:
第一行输入一个整数 n,表示树的总点数。
(1≤n≤10001≤ n≤ 10001≤n≤1000)
接下来n−1行每行输入两个整数表示一条树边
最后一行输入两个点 a,b
输出格式:
输出一个整数表示 a,b之间的距离
样例输入:
样例输出:
标程:
这道题说白了就是图的BFS,只得注意的是本标程中图的存储方式是邻接表,即使用n个向量(vector[ ])实现,每一个向量存对应顶点的所有相连的点(邻居)。
既然提都提到了,那么就把无权值无向图的邻接表的标程放出来吧:
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
结语:
DFS和BFS同为最最最基础的搜索算法,是参加比赛必须掌握的,最主要的还是——
刷题!
刷题!!
刷题!!!
刷题!!!!
刷题!!!!!
刷题!!!!!!
与其在这儿补干货,还不如在课上好好听,课后多刷题(doge