深度优先搜索与广度优先搜索

╰半橙微兮° 2022-10-19 08:08 348阅读 0赞

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

图上的搜索算法，最直接的理解就是，在图中找出从一个顶点出发，到另一个顶点的路径。为了搞清楚图的搜索算法，必须先把图的存储方式理解透彻。

图的存储

图有多种存储方法，最常用的两种分别是：邻接矩阵和出边数组。

邻接矩阵的存储方式如下图所示，底层依赖一个二维数组。

20210710115718293.png

对于无向图来说，如果顶点i与顶点j之间有边，我们就将A[i][j]和 A[j][i]标记1；对于有向图来说，如果顶点i到顶点j之间，有一条箭头从顶点i指向顶点j的边，那我们就将A[i][j]标记为1。同理，如果有一条箭头从顶点j指向顶点i的边，我们就将A[j][i]标记为1。对于带权图，数组中就存储相应的权重。

用邻接矩阵来表示一个图，虽然简单、直观，但是比较浪费存储空间。对于无向图来说，如果A[i][j]等于1，那A[j][i]也肯定等于1。实际上，我们只需要存储一个就可以了。也就是说，无向图的二维数组中，如果我们将其用对角线划分为上下两部分，那我们只需要利用上面或者下面这样一半的空间就足够了，另外一半白白浪费掉了。

针对上面邻接矩阵比较浪费内存空间的问题，出边数组可以避免空间浪费。如下图所示，每个顶点对应一条链表，链表中存储的是与这个顶点相连接的其他顶点。
20210710115358161.png

例如上图中，我们要确定，是否存在一条从顶点2到顶点4的边，那我们就要遍历顶点2的所有出边，看出边是否能到达顶点4。所以，比起邻接矩阵的存储方式，在出边数组中查询两个顶点之间的关系就没那么高效了。

  1. //无向图
  2. public class UndirectedGraph {  
  3.     /** * 顶点的个数 */
  4.     private int v;
  5.     /** * 邻接表(出边数组） */
  6.     private ArrayList<Integer>[] edges;
  8.     public UndirectedGraph(int v) { 
  9.       this.v = v;
  10.       edges = new ArrayList[v];
  11.       for (int i = 0; i < v; ++i) { 
  12.         edges[i] = new ArrayList<>();
  13.       }
  14.     }
  16.     /** * 对于无向图，其实就是点s到点t的两条边 * 用两条有向边代表无向图中的一条边 */
  17.     public void addEdge(int s, int t) { 
  18.       edges[s].add(t);
  19.       edges[t].add(s);
  20.     }
  21. }

深度优先搜索（DFS）

深度优先搜索用的是一种比较著名的算法思想，回溯思想。这种思想解决问题的过程，非常适合用递归来实现。例如下图中演示了用深度优先搜索的思想寻找一条从点s到点c的路径的方法。从图中我们可以看出，深度优先搜索找出来的路径，并不是点s到点c的最短路径。

20210710123412283.png

我把上面的过程用递归的形式写下来如下。深度优先搜索代码里，有个比较特殊的全局变量found，它的作用是，当我们已经找到终止点之后，我们就不再递归地继续查找了。

  1. //全局变量或者类成员变量
  2. boolean found = false;
  3. private int  v;
  4. private ArrayList<Integer>[] edges;
  6. public void existPath(int start, int t) { 
  7.     boolean[] visited = new boolean[v];
  8.     recurDfs(start, t, visited);
  9. }
  11. private void recurDfs(int current, int t, boolean[] visited) { 
  12.     if (found == true) { 
  13.         return;
  14.     }
  15.     visited[current] = true;
  16.     if (current == t) { 
  17.         found = true;
  18.         return;
  19.     }
  20.     for (int i = 0; i < edges[current].size(); ++i) { 
  21.         int q = edges[current].get(i);
  22.         if (!visited[q]) { 
  23.             recurDfs(q, t, visited);
  24.         }
  25.     }
  26. }

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

广度优先搜索（BFS）

广度优先搜索直观地讲，就是一种“地毯式”层层推进的搜索策略，即先查找离起始顶点最近的，然后是次近的，依次往外搜索。理解起来并不难，示意图如下。
20210710125744447.png

尽管广度优先搜索的原理挺简单，但代码实现还是稍微有点复杂度。实际上，这样得到的一条路径就是从起始点到指定点的最短路径。

  1. private boolean existPathBfs(int current, int t) { 
  2.     if (current == t) { 
  3.         return true;
  4.     }
  5.     visited[current] = true;
  6.     Queue<Integer> queue = new ArrayDeque<>();
  7.     queue.add(current);
  8.     while (!queue.isEmpty()) { 
  9.         int point = queue.poll();
  10.         for (int i = 0; i < edges[point].size(); ++i) { 
  11.             int q = edges[point].get(i);
  12.             if (!visited[q]) { 
  13.                 if (q == t) { 
  14.                     return true;
  15.                 }
  16.                 queue.add(q);
  17.                 visited[q] = true;
  18.             }
  19.         }
  20.     }
  21.     return false;
  22. }

BFS代码中的queue是一个队列，用来存储已经被访问、但相连的顶点还没有被访问的顶点。因为广度优先搜索是逐层访问的，也就是说，我们只有把第k层的顶点都访问完成之后，才能访问第k+1层的顶点。当我们访问到第k层的顶点的时候，我们需要把第k层的顶点记录下来，稍后才能通过第k层的顶点来找第k+1层的顶点。所以，我们用这个队列来实现记录的功能。

广度优先搜索的时间、空间复杂度是多少呢？最坏情况下，终止顶点t离起始顶点s很远，需要遍历完整个图才能找到。这个时候，每个顶点都要进出一遍队列，每个边也都会被访问一次，所以，广度优先搜索的时间复杂度是 O(V+E)，其中，V表示顶点的个数，E表示边的个数。当然，对于一个连通图来说，也就是说一个图中的所有顶点都是连通的，E肯定要大于等于V-1，所以，广度优先搜索的时间复杂度也可以简写为O(E)。空间消耗主要在几个辅助变量visited数组、queue队列上。这三个存储空间的大小都不会超过顶点的个数，所以空间复杂度是O(V)。

DFS与BFS的实际应用

样题一：岛屿的数量

给你一个由’1’(陆地)和 ‘0’(水)组成的的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。此外，你可以假设该网格的四条边均被水包围。
20210710142420104.png
DFS的思路：将二维网格看成一个无向图，竖直或水平相邻的点’1’之间有边相连。为了求出岛屿的数量，我们可以扫描整个二维网格。如果一个位置为’1’，则以其为起始节点开始进行深度优先搜索。在深度优先搜索的过程中，每个搜索到的’1’都会被重新标记。

最终岛屿的数量就是我们进行深度优先搜索的次数。

  1. class Solution { 
  3.     //垂直水平四个方向组成的方向数组
  4.     private int[] dx = { -1,0,1,0};
  5.     private int[] dy = { 0,1,0,-1};
  6.     private boolean[][] visited;
  8.     public int numIslands(char[][] grid) { 
  9.         visited = new boolean[grid.length][grid[0].length];
  10.         int ans = 0;
  11.         for (int i = 0; i < grid.length; i++) { 
  12.             for (int j = 0; j < grid[0].length; j++) { 
  13.                 if (grid[i][j] == '1' && !visited[i][j]) { 
  14.                     //以grid[i][j]这个点为起点，作深度优先遍历
  15.                     dfs(grid, i, j);
  16.                     //递归的次数就是图中陆地独立成片的块数
  17.                     ans++;
  18.                 }
  19.             }
  20.         }
  21.         return ans;
  22.     }
  24.     //从点(x,y)出发，深度优先遍历
  25.     private void dfs(char[][] grid, int x, int y) { 
  26.         //标记当前点grid[x][y]已经访问过了
  27.         visited[x][y] = true;
  28.         //然后遍历grid[x][y]点的所有出边，这里就是上下左右4个
  29.         for (int i = 0; i < 4; i++) { 
  30.             int nx = x + dx[i];
  31.             int ny = y + dy[i];
  32.             //判断坐标合法时，才继续遍历
  33.             if(nx < 0 || nx >= grid.length || ny < 0 || ny >= grid[0].length) { 
  34.                 continue;
  35.             }
  36.             //只遍历没访问过且为陆地的点
  37.             if (grid[nx][ny] == '1' && !visited[nx][ny]) { 
  38.                 dfs(grid, nx, ny);
  39.             }
  40.         }
  41.     }
  42. }

同样地，我们也可以使用广度优先搜索代替深度优先搜索。

BFS的思路：为了求出岛屿的数量，我们可以扫描整个二维网格。如果一个位置为‘1’，则将其加入队列，开始进行广度优先搜索。在广度优先搜索的过程中，从原点出发能到达的每个点‘1’都会被重新标记。直到队列为空，搜索结束。

最终岛屿的数量就是我们进行广度优先搜索的次数。

  1. class Solution { 
  3.     //垂直水平四个方向组成的方向数组
  4.     private int[] dx = { -1,0,1,0};
  5.     private int[] dy = { 0,1,0,-1};
  6.     private boolean[][] visited;
  8.     public int numIslands(char[][] grid) { 
  9.         visited = new boolean[grid.length][grid[0].length];
  10.         int ans = 0;
  11.         for (int i = 0; i < grid.length; i++) { 
  12.             for (int j = 0; j < grid[0].length; j++) { 
  13.                 if (grid[i][j] == '1' && !visited[i][j]) { 
  14.                     //以grid[i][j]这个点为起点，作广度优先遍历
  15.                     bfs(grid, i, j);
  16.                     ans++;
  17.                 }
  18.             }
  19.         }
  20.         return ans;
  21.     }
  23.     //从点(x,y)出发，广度优先遍历
  24.     private void bfs(char[][] grid, int x, int y) { 
  25.         //标记点(x,y)为已经访问过了
  26.         visited[x][y] = true;
  27.         Queue<Pair> queue = new ArrayDeque<>();
  28.         queue.add(new Pair(x, y));
  29.         while (!queue.isEmpty()) { 
  30.             Pair pair = queue.poll();
  31.             //然后遍历grid[x][y]点的所有出边，这里就是上下左右4个
  32.             for (int i = 0; i < 4; i++) { 
  33.                 int nx = pair.row + dx[i];
  34.                 int ny = pair.column + dy[i];
  35.                 //判断坐标合法时，才继续遍历
  36.                 if(nx < 0 || nx >= grid.length || ny < 0 || ny >= grid[0].length) { 
  37.                     continue;
  38.                 }
  39.                 //只遍历没访问过且为陆地的点
  40.                 if (grid[nx][ny] == '1' && !visited[nx][ny]) { 
  41.                     queue.add(new Pair(nx, ny));
  42.                     //入队时标记visited数组
  43.                     visited[nx][ny] = true;
  44.                 }
  45.             }
  46.         }
  47.     }
  49.     class Pair { 
  50.         int row;
  51.         int column;
  52.         public Pair(int row, int column) { 
  53.             this.row = row;
  54.             this.column = column;
  55.         }
  56.     }
  57. }

样题二：被包围的区域

20210710140111601.png

注意关键解释：被围绕的区域不会存在于边界上，换句话说，任何边界上的 ‘O’ 都不会被填充为 ‘X’。 任何不在边界上，或不与边界上的 ‘O’ 相连的 ‘O’ 最终都会被填充为 ‘X’。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

问题可以转化为：从边界上的‘O’出发所有能被访问到的‘O’都不能被填充为’X’，剩下的‘O’可以被填充为’X’，这是一个搜索问题。

思路：将所有存在于边界上的点’O’都打上标记，例如标记为’#’，然后从这些点出发作搜索，所有能到达的点’O’也打上标记’#’，最后将矩阵中所有标记为’#‘的点都填充为’O’，所有为’O’的点都填充为’X’。

DFS思路下的代码。

  1. class Solution { 
  3.     private int[] dx = { -1,0,1,0};
  4.     private int[] dy = { 0,1,0,-1};
  5.     private boolean[][] visited;
  7.     //寻找和边界连通的O，如果这个O与边界连通，那么不能替换，否则要替换
  8.     public void solve(char[][] board) { 
  9.         visited = new boolean[board.length][board[0].length];
  10.         for (int i = 0; i < board.length; i++) { 
  11.             for (int j = 0; j < board[0].length; j++) { 
  12.                 if (board[i][j] == 'X') { 
  13.                     continue;
  14.                 }
  15.                 //判断点是否在边界上,如果在边界上并且是O，并且没访问过，就访问一次
  16.                 boolean isEdge = (i == 0 || j == 0 || i == board.length - 1 || j == board[0].length - 1);
  17.                 if (isEdge && board[i][j] == 'O') { 
  18.                     dfs(board, i, j);
  19.                 }
  20.             }
  21.         }
  22.         for (int i = 0; i < board.length; i++) { 
  23.             for (int j = 0; j < board[0].length; j++) { 
  24.                 if (board[i][j] == 'O') { 
  25.                     board[i][j] = 'X';
  26.                 } else if (board[i][j] == '#') { 
  27.                     board[i][j] = 'O';
  28.                     continue;
  29.                 }
  30.             }
  31.         }
  32.     }
  34.     //从点(x,y)出发作深度优先遍历，访问从点(x,y)所能到达的所有点
  35.     private void dfs(char[][] board, int x, int y) { 
  36.         if (board[x][y] == '#') { 
  37.             return;
  38.         }
  39.         visited[x][y] = true;
  40.         board[x][y] = '#';
  41.         //然后遍历board[x][y]的所有点，这里就是上下左右4个
  42.         for (int i = 0; i < 4; i++) { 
  43.             int nx = x + dx[i];
  44.             int ny = y + dy[i];
  45.             //判断坐标合法时，才继续遍历
  46.             if(nx < 0 || nx >= board.length || ny < 0 || ny >= board[0].length) { 
  47.                 continue;
  48.             }
  49.             //只遍历没访问过且为'O'的点
  50.             if (board[nx][ny] == 'O' && !visited[nx][ny]) { 
  51.                 dfs(board, nx, ny);
  52.             }
  53.         }
  54.     }
  55. }

BFS思路下的代码。

  1. class Solution { 
  3.     private int[] dx = { -1,0,1,0};
  4.     private int[] dy = { 0,1,0,-1};
  5.     private boolean[][] visited;
  7.     //寻找和边界连通的O，如果这个O与边界连通，那么不能替换，否则要替换
  8.     public void solve(char[][] board) { 
  9.         visited = new boolean[board.length][board[0].length];
  10.         for (int i = 0; i < board.length; i++) { 
  11.             for (int j = 0; j < board[0].length; j++) { 
  12.                 if (board[i][j] == 'X') { 
  13.                     continue;
  14.                 }
  15.                 //判断点是否在边界上,如果在边界上并且是'O'，并且没访问过，就访问一次
  16.                 boolean isEdge = (i == 0 || j == 0 || i == board.length - 1 || j == board[0].length - 1);
  17.                 if (isEdge && board[i][j] == 'O') { 
  18.                     bfs(board, i, j);
  19.                 }
  20.             }
  21.         }
  22.         for (int i = 0; i < board.length; i++) { 
  23.             for (int j = 0; j < board[0].length; j++) { 
  24.                 if (board[i][j] == 'O') { 
  25.                     board[i][j] = 'X';
  26.                 } else if (board[i][j] == '#') { 
  27.                     board[i][j] = 'O';
  28.                     continue;
  29.                 }
  30.             }
  31.         }
  32.     }
  34.     //从点(x,y)出发作深度优先遍历，访问从点(x,y)所能到达的所有点
  35.     private void bfs(char[][] board, int x, int y) { 
  36.         visited[x][y] = true;
  37.         board[x][y] = '#';
  38.         Queue<Pair> queue = new ArrayDeque<>();
  39.         queue.add(new Pair(x, y));
  40.         while (!queue.isEmpty()) { 
  41.             Pair pair = queue.poll();
  42.             //然后遍历board[x][y]的所有点，这里就是上下左右4个
  43.             for (int i = 0; i < 4; i++) { 
  44.                 int nx = pair.row + dx[i];
  45.                 int ny = pair.column + dy[i];
  46.                 //判断坐标合法时，才继续遍历
  47.                 if(nx < 0 || nx >= board.length || ny < 0 || ny >= board[0].length) { 
  48.                     continue;
  49.                 }
  50.                 //只遍历没访问过且为'O'的点
  51.                 if (board[nx][ny] == 'O' && !visited[nx][ny]) { 
  52.                     queue.add(new Pair(nx, ny));
  53.                     visited[nx][ny] = true;
  54.                     board[nx][ny] = '#';
  55.                 }
  56.             }
  57.         }
  58.     }
  60.     class Pair { 
  61.         int row;
  62.         int column;
  63.         public Pair(int row, int column) { 
  64.             this.row = row;
  65.             this.column = column;
  66.         }
  67.     }
  68. }

样题三：省份数量

d838cca637de47e581e6c423b2e14cee.png

思路：给出的矩阵isConnected其实就是典型的邻接矩阵，这种图的存储方式很简洁。对于无向图，矩阵按对角线对称。问题可以转化成求无向图中连通块的个数，顶点数量为n，顶点的编号为0到n-1，矩阵isConnected描述了各个顶点的连接情况（矩阵中有一半信息是冗余的）。只需要从一个顶点出发遍历其能到达的其他所有顶点，当前顶点与其能到达的其他顶点构成连通块，统计这样的连通块的个数。

DFS与BFS的思路都能解决此问题，代码如下：

  1. class Solution { 
  2.     //在无向图中，若从顶点a到顶点b有路径,则称a和b是连通的。
  3.     //若无向图中，任意两个不同的顶点都连通，则称无向图为连通图
  4.     //求无向图中连通块数量
  5.     public int findCircleNum(int[][] isConnected) { 
  6.         int ans = 0;
  7.         //初始化
  8.         int v = isConnected.length;
  9.         boolean[] visited = new boolean[v];
  11.         //无向图中共有v个顶点，顶点编号为0到v-1，找图中连通块的数量
  12.         for (int i = 0; i < v; i++) { 
  13.             //已经访问过的不再访问
  14.             if (!visited[i]) { 
  15.                 //连通块的数量就是dfs或bfs搜索的次数
  16.                 // dfs(isConnected, i, visited);
  17.                 bfs(isConnected, i, visited);
  18.                 ans++;
  19.             }
  20.         }
  22.         return ans;
  23.     }
  25.     //深度优先搜索
  26.     private void dfs(int[][] isConnected, int cur, boolean[] visited) { 
  27.         //已经访问过了，不再访问
  28.         if (visited[cur]) { 
  29.             return;
  30.         }
  31.         visited[cur] = true;
  32.         //从点cur出发，遍历其能到达的所有其他点，cur自己除外
  33.         for (int i = 0; i < isConnected[0].length; i++) { 
  34.             if (i != cur && isConnected[cur][i] == 1) { 
  35.                 dfs(isConnected, i, visited);
  36.             }
  37.         }
  38.     }
  40.     //广度优先搜索
  41.     private void bfs(int[][] isConnected, int cur, boolean[] visited) { 
  42.         //已经访问过了，不再访问
  43.         if (visited[cur]) { 
  44.             return;
  45.         }
  46.         Queue<Integer> queue = new ArrayDeque<>();
  47.         visited[cur] = true;
  48.         queue.add(cur);
  49.         //从顶点cur出发，遍历其能到达的其他点
  50.         while (!queue.isEmpty()) { 
  51.             Integer vertex = queue.poll();
  52.              //从顶点cur出发，遍历其能到达的并且没有访问过的其他点
  53.              for (int i = 0; i < isConnected[0].length; i++) { 
  54.                  if (i != vertex && isConnected[vertex][i] == 1 && visited[i] == false) { 
  55.                      queue.add(i);
  56.                      visited[i] = true;
  57.                  }
  58.              }
  59.         }
  60.     }
  61. }

小结

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

发表评论

表情：
评论列表 （有 0 条评论，348人围观）

还没有评论，来说两句吧...

相关阅读

    相关 深度优先搜索与广度优先搜索

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

    ╰半橙微兮°╰半橙微兮°/ 0 赞/ 349 阅读