广度优先搜索（BFS）总结及其Java实现

图是搜索算法的最常用数据结构，因此需要先储备一些图的概念。
我总结在另一篇博客：非线性数据结构——图的相关概念

广度优先搜索（Breadth-First-Search）

广度优先的思路比较简单，可以通过下面这张图直接理解：

1.BFS算法思路简述
设置一个数组visited[]存放每个结点是否被访问过
（1）访问第一个顶点，置已访问标志；
（2）取第一个邻接点；
（3）若未被访问过，则对其进行DFS；
（4）取下一个邻接点；
重复（3）、（4）直至所有邻接顶点取完。
BFS是一种分层的搜索过程(典型：树的层次遍历) ，每向前走一步可能访问一批顶点, 不像深度优先搜索那样有往回退的情况。因此, 广度优先搜索不是一个递归的过程。
2.图的代码实现

public class Graph{ //无向图
   private int v;   //顶点的个数
   private LinkedList<Integer> adj[];   //邻接表
   public Graph(int v){
        this.v=v;    adj = new LinkedList[v];
        for(int i=0;i<v;i++){  
        adj[i] = new LinkedList<>();  
        }
   }   //无向图一条边存两次
   public void addEdge(int s, int t){
       adj[s].add(t);
       adj[t].add(s);
   }
}

3.BFS代码实现
搜索一条从 s 到 t 的最短路径：
队列的作用：因为广度优先搜索是逐层访问的，当我们访问到第 k 层的顶点的时候，我们需要把第 k 层的顶点记录下来，稍后才能通过第 k 层的顶点来找第 k+1 层的顶点。所以，我们用这个队列来实现记录的功能。
从顶点 s 开始，广度优先搜索到顶点 t 后，prev 数组中存储的就是搜索的路径。不过这个路径是反向存储的。比如，通过顶点 2 的邻接表访问到顶点 3，那 prev[3]就等于 2。

public void bfs(int s, int t) {
  if (s == t) return;
  //visited 是用来记录已经被访问的顶点，用来避免顶点被重复访问。
  boolean[] visited = new boolean[v];
  visited[s]=true;
  //queue 用来存储本身已被访问、但相连的顶点还没有被访问的顶点。
  Queue<Integer> queue = new LinkedList<>();
  queue.add(s);
  //prev 用来记录搜索路径。
  int[] prev = new int[v];
  for (int i = 0; i < v; ++i) {   prev[i] = -1;  }
  //
  while (queue.size() != 0) {
    int w = queue.poll();
    for (int i = 0; i < adj[w].size(); ++i) {
       int q = adj[w].get(i);
       if (!visited[q]) {
         prev[q] = w;
         if (q == t) { //搜索到t，直接返回prev数组，注意逆序
           print(prev, s, t);
           return;
        }
        visited[q] = true;//顶点 q 被访问，visited[q]置为 true。
        queue.add(q);
      }
    }
  }
}
//为了正向打印出路径，我们需要递归地来打印
private void print(int[] prev, int s, int t) { // 递归打印s->t的路径
  if (prev[t] != -1 && t != s) {
    print(prev, s, prev[t]);
  }
  System.out.print(t + " ");
}

本文代码代码部分均来极客时间的《数据结构与算法之美》第31课