“搜索” 算法

深度优先搜索算法和广度优先搜索算法都是基于 “图” 这种数据结构的。这是因为，图这种数据结构的表达能力很强，大部分涉及搜索的场景都可以抽象成 “图”。

广度优先搜索（breadth-first search， BFS） 借助队列实现

广度优先搜索（Breadth-First-Search），我们平常都把简称为 BFS。直观地讲，它其实就是一种 “地毯式” 层层推进的搜索策略，即先查找离起始顶点最近的，然后是次近的，依次往外搜索。

解决最短路径问题的算法被称为广度优先搜索 。

一种用于图的查找算法。

解决两类问题：

  • 第一类问题：从节点 A 出发，有前往节点 B 的路径吗？
  • 第二类问题：从节点 A 出发，前往节点 B 的哪条路径最短？

深度优先和广度优先搜索算法 - 图1

广度优先搜索的分解图

深度优先和广度优先搜索算法 - 图2
深度优先和广度优先搜索算法 - 图3深度优先和广度优先搜索算法 - 图4

复杂度

最坏情况下，终止顶点 t 离起始顶点 s 很远，需要遍历完整个图才能找到。这个时候，每个顶点都要进出一遍队列，每个边也都会被访问一次，所以，广度优先搜索的时间复杂度是 O (V+E)，其中，V 表示顶点的个数，E 表示边的个数。当然，对于一个连通图来说，也就是说一个图中的所有顶点都是连通的，E 肯定要大于等于 V-1，所以，广度优先搜索的时间复杂度也可以简写为 O (E)。

广度优先搜索的空间消耗主要在几个辅助变量 visited 数组、queue 队列、prev 数组上。这三个存储空间的大小都不会超过顶点的个数，所以空间复杂度是 O (V)。

  2. public class Graph { // 无向图
  3.   private int v; // 顶点的个数
  4.   private LinkedList<Integer> adj[]; // 邻接表
  6.   public Graph(int v) {
  7.     this.v = v;
  8.     adj = new LinkedList[v];
  9.     for (int i=0; i<v; ++i) {
  10.       adj[i] = new LinkedList<>();
  11.     }
  12.   }
  14.   public void addEdge(int s, int t) { // 无向图一条边存两次
  15.     adj[s].add(t);
  16.     adj[t].add(s);
  17.   }
  18. }
  20. public void bfs(int s, int t) {
  21.   if (s == t) 
  22.       return;
  23.   boolean[] visited = new boolean[v];
  24.   visited[s]=true;
  25.   Queue<Integer> queue = new LinkedList<>();
  26.   queue.add(s);
  27.   int[] prev = new int[v];
  28.   for (int i = 0; i < v; ++i) {
  29.     prev[i] = -1;
  30.   }
  31.   while (queue.size() != 0) {
  32.     int w = queue.poll();
  33.    for (int i = 0; i < adj[w].size(); ++i) {
  34.       int q = adj[w].get(i);
  35.       if (!visited[q]) {
  36.         prev[q] = w;
  37.         if (q == t) {
  38.           print(prev, s, t);
  39.           return;
  40.         }
  41.         visited[q] = true;
  42.         queue.add(q);
  43.       }
  44.     }
  45.   }
  46. }
  48. private void print(int[] prev, int s, int t) { // 递归打印s->t的路径
  49.   if (prev[t] != -1 && t != s) {
  50.     print(prev, s, prev[t]);
  51.   }
  52.   System.out.print(t + " ");
  53. }

相关题目

语雀内容

语雀内容

语雀内容

深度优先搜索（DFS） 借助栈实现

深度优先搜索（Depth-First-Search），简称 DFS。最直观的例子就是 “走迷宫”。（一条路走到黑，不能走的时候，退回到上一个路口，选择一条路走到黑）

假设你站在迷宫的某个岔路口，然后想找到出口。你随意选择一个岔路口来走，走着走着发现走不通的时候，你就回退到上一个岔路口，重新选择一条路继续走，直到最终找到出口。这种走法就是一种深度优先搜索策略。

搜索的起始顶点是 s，终止顶点是 t，我们希望在图中寻找一条从顶点 s 到顶点 t 的路径。如果映射到迷宫那个例子，s 就是你起始所在的位置，t 就是出口。
这里面实线箭头表示遍历，虚线箭头表示回退。从图中我们可以看出，深度优先搜索找出来的路径，并不是顶点 s 到顶点 t 的最短路径。
深度优先和广度优先搜索算法 - 图5


boolean found = false; // 全局变量或者类成员变量

public void dfs(int s, int t) {
  found = false;
  boolean[] visited = new boolean[v];
  int[] prev = new int[v];
  for (int i = 0; i < v; ++i) {
    prev[i] = -1;
  }
  recurDfs(s, t, visited, prev);
  print(prev, s, t);
}

private void recurDfs(int w, int t, boolean[] visited, int[] prev) {
  if (found == true) return;
  visited[w] = true;
  if (w == t) {
    found = true;
    return;
  }
  for (int i = 0; i < adj[w].size(); ++i) {
    int q = adj[w].get(i);
    if (!visited[q]) {
      prev[q] = w;
      recurDfs(q, t, visited, prev);
    }
  }
}

复杂度

每条边最多会被访问两次，一次是遍历，一次是回退。所以，图上的深度优先搜索算法的时间复杂度是 O (E)，E 表示边的个数。

深度优先搜索算法的消耗内存主要是 visited、prev 数组和递归调用栈。visited、prev 数组的大小跟顶点的个数 V 成正比，递归调用栈的最大深度不会超过顶点的个数，所以总的空间复杂度就是 O (V)。

总结

广度优先搜索和深度优先搜索是图上的两种最常用、最基本的搜索算法，比起其他高级的搜索算法，比如 A、IDA 等，要简单粗暴，没有什么优化，所以，也被叫作暴力搜索算法。所以，这两种搜索算法仅适用于状态空间不大，也就是说图不大的搜索。广度优先搜索，通俗的理解就是，地毯式层层推进，从起始顶点开始，依次往外遍历。广度优先搜索需要借助队列来实现，遍历得到的路径就是，起始顶点到终止顶点的最短路径。深度优先搜索用的是回溯思想，非常适合用递归实现。换种说法，深度优先搜索是借助栈来实现的。在执行效率方面，深度优先和广度优先搜索的时间复杂度都是 O (E)，空间复杂度是 O (V)。