一.基本概念
广度优先搜索就是一种通过逐层遍历所有访问队形，从而找到通过最短节点数到达目标的算法。、
主要用于解决在一个无加权图下找到从起点S到指定点W的最短路径。
二.基本理解
如下图所示， 要寻找从节点0到节点节点3的最短路径，在第一轮搜索中会把节点1、2、5当做搜索对象，在第二轮搜索中会把节点2、3、4当做搜索对象，此时，找到目标节点3，所以从节点0到节点3的最短路径为2，这就是BFS的基本原理；可能有人会问，为什么在第二次搜索中还会搜索到2，这是因为虽然在第一次搜索中经过了节点2，但是是作为0的下一层节点进行搜索的，第二次搜索节点2是作为节点1的下一层节点进行搜索的(在实际的算法实现过程中，会直接将2标记为已经遍历，避免第二次重复搜索)
图片来源：https://zhuanlan.zhihu.com/p/137296658(侵权必删)
三.算法的基本流程
BFS经常借助队列来实现，队列的特性就是FIFO(First in First out)，基本的流程如下：
- 将符合要求的节点加入队列，并把该节点标记为已遍历状态，防止后续造成死循环；
- 当队列不为空时，从队列中取出一个节点V
- 获取该节点相邻的节点并继续放入队列，如果当前节点等于目标节点，直接返回
四.代码示例
以leetcode909题目为例：
总结题意就是：从位置1到位置n的最短移动次数，*和蛇分别是代表要移动到对应方格。
可以看出 是求最短路径问题，所以可以考虑安装BFS的方式求解；
代码实现：
1 class Solution { 2 //转换成一维的数组 就是找一条路径 就是深度优先搜索 3 //要把对应的id转换为对应的行和列 4 public int snakesAndLadders(int[][] board) { 5 int length = board.length; 6 boolean[] visited = new boolean[length * length + 1]; 7 Queue<int[]> que = new LinkedList<int[]>(); 8 que.offer(new int[]{1, 0}); 9 while(!que.isEmpty()){ 10 int[] curr = que.poll(); 11 for(int i = 1; i <= 6; ++i){ 12 int nxt = curr[0] + i; 13 if(nxt > length * length){ 14 break; 15 } 16 int[] rc = id2rc(nxt, length); 17 if(board[rc[0]][rc[1]] > 0){ 18 nxt = board[rc[0]][rc[1]]; 19 } 20 if(nxt == length *length){ 21 return curr[1] + 1; 22 } 23 if(!visited[nxt]){ 24 visited[nxt] = true; 25 que.offer(new int[]{nxt, curr[1] + 1}); 26 } 27 } 28 } 29 return -1; 30 } 31 32 public int[] id2rc(int id, int n) { 33 int r = (id - 1) / n, c = (id - 1) % n; 34 if (r % 2 == 1) { 35 c = n - 1 - c; 36 } 37 return new int[]{n - 1 - r, c}; 38 } 39 }
五.leetcode相关题目(持续更新)
815. 公交路线
773. 滑动谜题