图 - 深度/广度 优先搜索，两种暴力搜索算法（遍历算法）

图是一种表达能力很强的非线性数据结构，因为要表达很多信息，所以他的实现就要比其它的线性数据结构复杂。相应的，图的搜索（查询）就不像之前的线性结构那样简单了，今天在这里我们介绍两种最简单也是最暴力的图的搜索算法：深度优先搜索 和 广度优先搜索。

注：当你的目的不是查找某个数据，而是获取图中所有的数据的时候，可以将这两种搜索算法改造成图的遍历算法，图的遍历也有很多用处，例如使用网络爬虫获取整个互联网的信息。

对于图的搜索算法，最直接的理解就是：在图中从一个顶点出发，找到到达另一个顶点的路径

图的构建

图的搜索算法可以应用在有向图、无向图中，本文使用无向图作为例子讲解，下面是构建一个图的代码：

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);
  }
}

广度优先搜索（Breadth First Search）

广度优先搜索是一种“地毯式”层层推进的搜索策略，它先查找起始顶点最近的顶点，然后是次近的，依次往外搜索，直到找到期待的数值: 广度优先搜索.jpg

下面是广度优先搜索的代码：

public void bfs(int s, int t) {
  if (s == t) return;
  boolean[] visited = new boolean[v];
  visited[s]=true;
  Queue<Integer> queue = new LinkedList<>();
  queue.add(s);
  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) {
          print(prev, s, t);
          return;
        }
        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 + " ");
}

在搜索算法中，有三个非常重要的辅助变量，理解这三个变量，基本上就能读懂这段代码了：

• visited：记录已经被访问的顶点，用来避免顶点被重复访问。如果顶点 q 被访问，那相应的 visited[q] 会被设置为 true。
• queue：一个队列，用于存储已经被访问，但是还没有被访问过的相连的顶点。广度优先搜索算法是逐层访问的，所以队列中的元素是按层有序的。
• prev：用来记录搜索路径。当我们从 s 开始，搜索到顶点 t 后，使用 prev 数组中的数据构建搜索路径。比如，我们通过顶点 x 访问到了顶点 y ，那我们就将 prev[y] 设置为 x 。由于 prev 是反向构建的，所以我们需要特殊处理才能打印正确的路径信息，你需要看一下 print( ) 函数的实现方式。

下面有一个广度优先搜索过程的分解图，可以帮助你理解代码，特别是三个辅助变量的用途： 广度优先实例1.jpg
广度优先实例2.jpg
广度优先实例3.jpg

复杂度分析

• 时间复杂度：在最坏情况下，算法要遍历所有的顶点和边，也就是 O(V+E)，其中 V 是顶点的个数，E 是边的个数。如果一个图是连通图，那么 E >= V-1 ，所以，它是时间复杂度也可以简写为 O(E)。
• 空间复杂度：我们需要三个辅助变量辅助计算，而这三个辅助变量使用的空间都不会超过 V，所以空间复杂度为 O(V)。

深度优先搜索（Depth First Search）

深度优先搜索最直观的例子就是走迷宫。
假设你在迷宫的某个岔路口，你不知道走哪条路，那你就随意选择一条路，如果这条路是一条死路，就回退到岔口，换一条路继续走，直到找到出口。

这就是一种典型的深度优先搜索策略： 深度优先搜索.jpg
深度优先搜索使用了一个著名的算法思想：回溯思想。这种思想解决问题的过程，非常适合使用递归来实现。

深度优先算法中也使用到了 prev、visted 两个变量以及 print( ) 函数。同时它还使用了一个 found 变量，用于标记是否找到终点 t ，如果 t 以及被找到，我们就不再需要递归查找了：

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 是边的个数。
• 空间复杂度：我们需要递归调用栈 和 两个辅助变量，它们的规模不会超过顶点的个数 V ，所以空间复杂度为 O(V)。

总结

• 深度优先搜索 和 广度优先搜索 是两种非常基础也是非常暴力的搜索算法。
• 他们的时间复杂度都是 O(E)，空间复杂度都是 O(V)。
• 广度优先搜索 是一种地毯式的搜索算法。深度优先搜索 利用了回溯思想和递归技巧。
• 思考，我们能否通过广度优先搜索算法实现QQ中推荐“可能认识的人”的功能？

下面是我自己写的图的代码，可以供你参考

import queue

class Graph:
    def __init__(self, n):
        self.v = [[] for i in range(n)]

    def addEdge(self, x, y):
        '''
        建立一条边
        :param x:边的一个顶点
        :param y: 边的另一个顶点
        :return: None
        '''
        self.v[x].append(y)
        self.v[y].append(x)

    def __repr__(self):
        return str(self.v)

    def dfs(self, s, e):
        '''
        深度优先搜索
        :param s:起始位置
        :param e:结束位置
        :return:None
        '''

        visted = [False for i in range(len(self.v))]  # 记录每个顶点是否被浏览过
        path = [-1 for i in range(len(self.v))]  # 记录路径信息
        path[s] = s
        r = self.recueDfs(s, e, s, visted, path)  # 放入递归程序中

        print('')
        return r

    def recueDfs(self, s, e, cur, visted, path):
        '''
        深度优先搜索会在这里进行递归
        :param s: 起始位置
        :param e: 结束位置
        :param cur: 当前位置
        :param visted: 记录顶点是否被浏览过
        :param path: 记录路径信息
        :return: 寻找完成的路径信息
        '''
        visted[cur] = True

        if cur == e:  # 如果当前顶点是终止顶点
            self.print_path(path, s, e)  # 打印路径
            return path

        for i in self.v[cur]:  # 如不是终点，依次递归该顶点的每个相邻顶点
            if visted[i]:
                continue
            path[i] = cur
            res = self.recueDfs(s, e, i, visted, path)
            # 如果上一层递归有返回值，代表找到了路径，可以直接 return 跳出；如果递归没有返回值，证明没有找到路径，退出递归函数相当于回退
            if res:
                return res

    def bfs(self, s, e):
        '''
        广度优先搜索算法
        :param s: 起始位置
        :param e: 结束位置
        :return:寻找完成的路径信息
        '''
        visted = [False for i in range(len(self.v))]  # 记录每个顶点是否被浏览过
        visted[s] = True
        q = queue.Queue(len(self.v))  # 维护一个队列，用于放置之后要遍历的顶点
        q.put(s)
        path = [-1 for i in range(len(self.v))]  # 记录路径信息
        path[s] = s
        while q.qsize() != 0:  # 队列
            w = q.get()
            for i in self.v[w]:
                if not visted[i]:
                    path[i] = w
                    visted[i] = True
                    q.put(i)
                    if i == e:
                        self.print_path(path, s, e)
                        print('')
                        return path

    def print_path(self, path, s, e):
        '''
        输出路径信息
        :param path: 记录路径信息的数组
        :param s: 起始位置
        :param e: 结束位置
        :return: None
        '''
        if e == s:
            print(e, end='')
            return
        else:
            self.print_path(path, s, path[e])
            print('->' + str(e), end='')


if __name__ == '__main__':
    g = Graph(6)
    g.addEdge(1, 0)
    g.addEdge(1, 2)
    g.addEdge(1, 3)
    g.addEdge(1, 5)
    g.addEdge(2, 5)
    g.addEdge(3, 5)
    g.addEdge(4, 5)
    res = g.bfs(0, 4)
    print(res)
    res = g.dfs(0, 4)
    print(res)

---

以上就是两种图的搜索算法。

注：本文章的主要内容来自我对极客时间app的《数据结构与算法之美》专栏的总结，我大量引用了其中的代码和截图，如果想要了解具体内容，可以前往极客时间