https://time.geekbang.org/column/article/70891

引子

之前图的表示方法，讲到如何用有向图，无向图来表示社交网络。社交网络中有一个六度分割理论，即你与世界上另一个人间隔关系不会超过六度，也就是平均只需要六步就可以联系到任何两个互不相识的人。
一个用户一度连接用户就是他的好友，二度连接用户就是他的好友的好友，三度连接用户就是他的好友的好友的好友。社交网络中 可以通过用户之间连接关系实现推荐“可能认识的人”。
开篇问题，给一个用户，如何找出用户所有的三度（包含一度、二度、三度）好友关系？
使用深度优先和广度优先搜索算法。

什么是“搜索”算法？

算法建立在具体数据结构上，深度优先搜索和广度优先搜索就是基于“图”这种数据结构，因为图的数据结构表达能力很强，大部分涉及搜索的场景都可以抽象成“图”。
图上搜索方法，实际就是从图找一个顶点出发，到另一个顶点的路径。bfs dfs是最简单“暴力”的搜索方法，还有A、IDA等启发式搜索方法。
图用邻接表实现。
bfs，dfs既可以无向图也可以有向图。

  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. }

图的定义。

广度优先遍历 BFS

“地毯式”层层递推搜索策略，查找离顶点最近的，然后次近的，依次向外搜索。
31|深度和广度优先搜索：如何找出社交网络中的三度好友关系？ - 图1

s起始顶点，t终止顶点。搜索从s到t的路径，实际上求得的就是s到t的最短路径。

  2. public void bfs(int s, int t) {
  3.   if (s == t) return;//s=t直接返回
  4.   boolean[] visited = new boolean[v];
  5.   visited[s]=true;
  6.   Queue<Integer> queue = new LinkedList<>();//队列
  7.   queue.add(s);
  8.   int[] prev = new int[v];
  9.   for (int i = 0; i < v; ++i) {
  10.     prev[i] = -1;
  11.   }//prev赋初值
  12.   while (queue.size() != 0) {
  13.     int w = queue.poll();//弹出第一个元素 并删除
  14.    for (int i = 0; i < adj[w].size(); ++i) {//size为边的个数。
  15.       int q = adj[w].get(i);
  16.       if (!visited[q]) {
  17.         prev[q] = w;//q未访问，则prev值（上一个节点）置为w
  18.         if (q == t) {
  19.           print(prev, s, t);
  20.           return;
  21.         }
  22.         visited[q] = true;
  23.         queue.add(q);
  24.       }
  25.     }
  26.   }
  27. }
  29. private void print(int[] prev, int s, int t) { // 递归打印s->t的路径
  30.   if (prev[t] != -1 && t != s) {
  31.     print(prev, s, prev[t]);//“打印 s->t ”相当于 “打印s -> prev[t] + 打印 t ”
  32.   }
  33.   System.out.print(t + " ");
  34. }

visited用来记录已经被访问的顶点，用来避免顶点被重复访问。如果顶点q被访问，那相应的visited[q]被设置为true。
queue是一个队列，用来存储已经被访问、但相连的顶点还没有被访问的顶点。因为广度优先搜索是逐层访问的，也就是说，我们只有把第k层顶点全部访问完成后，才能访问第k+1层顶点。当我们访问第k层顶点的时候，我们需要把第k层顶点记录下来，稍后才能通过第k层顶点来找第k+1层的顶点。所有，用队列来实现记录的功能。
prev用来记录搜索路径。当从顶点s开始，广度优先搜索到顶点t后，prev数组中存储的就是搜索的路径。不过，这个路径是反向存储的。prev[w]存储的是，顶点w是从哪个前驱顶点遍历过来的。比如，我们通过顶点2的邻接表访问到顶点3，那prev[3]就等于2.为了正向打印出路径，需要递归的来打印。可以看一下print函数实现方式。
31|深度和广度优先搜索：如何找出社交网络中的三度好友关系？ - 图2

31|深度和广度优先搜索：如何找出社交网络中的三度好友关系？ - 图3

31|深度和广度优先搜索：如何找出社交网络中的三度好友关系？ - 图4

时间复杂度分析

最坏情况下，终止顶点 t 离起始顶点 s 很远，需要遍历完整个图才能找到。这个时候，每个顶点都要进出一遍队列，每个边也都会被访问一次，所以，广度优先搜索的时间复杂度是 O(V+E)，其中，V 表示顶点的个数，E 表示边的个数。当然，对于一个连通图来说，也就是说一个图中的所有顶点都是连通的，E 肯定要大于等于 V-1，所以，广度优先搜索的时间复杂度也可以简写为 O(E)。（树的特性是E = V - 1，树是边最少的联通图，因此一般而言E >= V -1）。
广度优先搜索的空间消耗主要在几个辅助变量 visited 数组、queue 队列、prev 数组上。这三个存储空间的大小都不会超过顶点的个数，所以空间复杂度是 O(V)。（广度优先搜索的空间消耗主要在几个辅助变量 visited 数组、queue 队列、prev 数组上。这三个存储空间的大小都不会超过顶点的个数，所以空间复杂度是 O(V)。 深度优先搜索算法的消耗内存主要是 visited、prev 数组和递归调用栈。visited、prev 数组的大小跟顶点的个数 V 成正比，递归调用栈的最大深度不会超过顶点的个数，所以总的空间复杂度就是 O(V)。 在执行效率方面，深度优先和广度优先搜索的时间复杂度都是 O(E)，空间复杂度是 O(V)）。

深度优先搜索（DFS）

最直观例子就是走迷宫。
假设你站在迷宫的某个岔路口，然后想找到出口。你随意选择一个岔路口来走，走着走着发现走不通的时候，你就回退到上一个岔路口，重新选择一条路继续走，直到最终找到出口。这种走法就是一种深度优先搜索策略。
31|深度和广度优先搜索：如何找出社交网络中的三度好友关系？ - 图5
起点s，终点t。实现代表遍历，虚线代表回退。深度优先搜索找出来的路径并不是顶点s到顶点t的最短路径。
深度优先搜索用的是 回溯的思想。这种思想非常时候用递归。

  2. boolean found = false; // 全局变量或者类成员变量
  4. public void dfs(int s, int t) {
  5.   found = false;
  6.   boolean[] visited = new boolean[v];
  7.   int[] prev = new int[v];
  8.   for (int i = 0; i < v; ++i) {
  9.     prev[i] = -1;
  10.   }
  11.   recurDfs(s, t, visited, prev);
  12.   print(prev, s, t);
  13. }
  15. private void recurDfs(int w, int t, boolean[] visited, int[] prev) {
  16.   if (found == true) return;
  17.   visited[w] = true;
  18.   if (w == t) {
  19.     found = true;
  20.     return;
  21.   }
  22.   for (int i = 0; i < adj[w].size(); ++i) {
  23.     int q = adj[w].get(i);
  24.     if (!visited[q]) {
  25.       prev[q] = w;
  26.       recurDfs(q, t, visited, prev);
  27.     }
  28.   }
  29. }

prev、visit变量和print函数，和广度优先搜索的代码实现是一样的。
但有一个特殊遍历found，作用表示当找到终止点t后，就不再继续查找了。
个人感觉深度和广度实际上都适用这一段逻辑，都是在某个顶点遍历该顶点相连接的其他顶点。而且对于每个顶点来说都可以递归这段逻辑。唯一且重要的区别是，为了保证广度优先的特征（以某个顶点一层一层往外），利用了queue，来保证同一层的顶点靠在一起处理（如同一年级学生靠一起排一条长队，二年级的再排好队跟着一年级学生一样），这样就能实现按层搜索。如果没有这个queue，就成为了深度优先，来一个学生，就为他办完整个流程的事。

时间复杂度

从前面的图可以看出，每条边最多会被访问两次，一次是遍历，一次是回退。所以，图上的深度优先搜索算法的时间复杂度是 O(E)，E 表示边的个数。
深度优先搜索算法的消耗内存主要是 visited、prev 数组和递归调用栈。visited、prev 数组的大小跟顶点的个数 V 成正比，递归调用栈的最大深度不会超过顶点的个数，所以总的空间复杂度就是 O(V)。

解答开篇

使用广度优先搜索，与用户距离边数是2的点，就是二度好友关系。用一个数组来记录每个顶点和起始点距离，就可以找到三度好友关系等。

小结

广度优先搜索和深度优先搜索是图上的两种最常用、最基本的搜索算法，比起其他高级的搜索算法，比如 A、IDA 等，要简单粗暴，没有什么优化，所以，也被叫作暴力搜索算法。所以，这两种搜索算法仅适用于状态空间不大，也就是说图不大的搜索。
广度优先搜索，通俗的理解就是，地毯式层层推进，从起始顶点开始，依次往外遍历。广度优先搜索需要借助队列来实现，遍历得到的路径就是，起始顶点到终止顶点的最短路径。深度优先搜索用的是回溯思想，非常适合用递归实现。换种说法，深度优先搜索是借助栈来实现的。在执行效率方面，深度优先和广度优先搜索的时间复杂度都是 O(E)，空间复杂度是 O(V)。
广度优先需要维护一个队列。当图中顶点很多，层次很深时，会导致队列需要很大内存。所以BFS适合顶点不多，层次不太深的情况 深度优先在每层搜索只维护一个顶点，节省内存 但深度优先是一条路走到底，没法找到最短路径。所以深度优先缺点是仅仅能找到解，但无法判断是否是最优解。优点是内存消耗小。

深度 ：借助一个栈。
广度：借助一个队列。

思考

  1. 能否用深度优先算法解决开篇问题？

用深度遍历，遍历到第三层的时候就回溯到上层节点，知道所有三度都找到。

  1. 学习数据结构最难的不是理解和掌握原理，而是能灵活地将各种场景和问题抽象成对应的数据结构和算法。今天的内容中提到，迷宫可以抽象成图，走迷宫可以抽象成搜索算法，你能具体讲讲，如何将迷宫抽象成一个图吗？或者换个说法，如何在计算机中存储一个迷宫？

将迷宫的每个岔口记为”顶点”，岔口之间的路径记为”边”，可以用邻接表存储，也可以用邻接矩阵存储。但是个人感觉，像那种标准的方格迷宫，适合用邻接矩阵存储，因为稠密度比较高。

另一个比较好的 bfs dfs算法解释