深度优先，广度优先，拓扑排序（实战题解）_深度优先排序

前言

深度遍历和广度遍历在算法占比很大，主要是解决图的问题（树也是图的一种）

一、深度优先遍历

1、深度遍历（DFS）解决什么问题

DFS解决的是连通性的问题，即给定两⼀个起始点（或某种起始状态）和⼀个终点（或某种最终状态），判断是否有⼀条路径能从起点连接到终点。很多情况下，连通的路径有很多条，只需要找出⼀条即可，DFS 只关⼼路径存在与否，不在乎其⻓短。
所以dfs一般都是找路径的

2、算法思想：

图的深度优先搜索(Depth First Search)，和树的先序遍历比较类似。
它的思想：假设初始状态是图中所有顶点均未被访问，则从某个顶点v出发，首先访问该顶点，然后依次从它的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和v有路径相通的顶点都被访问到。 若此时尚有其他顶点未被访问到，则另选一个未被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。
显然，深度优先搜索是一个递归的过程
深度优先遍历特点是，选定一个出发点后进行遍历，能前进则前进，若不能前进，回退一步再前进，或再回退一步后继续前进。依此重复，直到所有与选定点相通的所有顶点都被遍历。

3、例题讲解：

1. 给定⼀个⼆维矩阵代表⼀个迷宫
2. 迷宫⾥⾯有通道，也有墙壁，有墙壁的地⽅不能通过
3. 通道由数字0表示，⽽墙壁由-1表示
4. 现在问能不能从A点⾛到B点？
   
   核心代码：

boolean dfs(int maze[][], int x, int y) {

##判断是否抵达了⽬的地B，是则⽴即返回
 if (x == B[0] && y == B[1]) {
 return true;
 } 

##标记当前点已经被访问过了
 maze[x][y] = -1;

##在规定的四个⽅向上进⾏尝试
 for (int d = 0; d < 4; d++) {
 int i = x + dx[d], j = y + dy[d];

##如果有⼀条路径被找到了，则返回true
 if (isSafe(maze, i, j) && dfs(maze, i, j)) { 
 return true; 
 } 
 } 
 
 ##尝试了所有可能还没找到B，则返回false
 return false; 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

4、实站经典：

79. 单词搜索：
给定一个二维网格和一个单词，找出该单词是否存在于网格中。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例:

board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]
给定 word = "ABCCED", 返回 true
给定 word = "SEE", 返回 true
给定 word = "ABCB", 返回 false
1
2
3
4
5
6
7
8
9

思路：
设函数check(i,j,k) 判断以网格的 (i, j)(i,j) 位置出发，能否搜索到单词 word[k…]，其中word[k…] 表示字符串 word 从第 k 个字符开始的后缀子串。如果能搜索到，则返回 true，反之返回 false。函数check(i,j,k) 的执行步骤如下：
如果 board[i][j] =s[k]当前字符不匹配，直接返回 false。
如果当前已经访问到字符串的末尾，且对应字符依然匹配，此时直接返回true。
否则，遍历当前位置的所有相邻位置。如果从某个相邻位置出发，能够搜索到子串 word[k+1…]，则返回 \texttt{true}true，否则返回 false。
这样，我们对每一个位置 (i,j)(i,j) 都调用函数check(i,j,0) 进行检查：只要有一处返回 true，就说明网格中能够找到相应的单词，否则说明不能找到。
为了防止重复遍历相同的位置，需要额外维护一个与 board 等大的 visited 数组，用于标识每个位置是否被访问过。每次遍历相邻位置时，需要跳过已经被访问的位置。
代码：

class Solution {
   public boolean exist(char[][] board, String word) {
        if(board==null || board.length==0 || board[0].length==0) return false;
        int m=board.length;
        int n=board[0].length;
        boolean[][] visited=new boolean[m][n];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(dfs(board,word,i,j,0,visited)){
                    return true;
                }
            }
        }
        return false;
    }
    private boolean dfs(char[][] board, String word, int i, int j, int start, boolean[][] visited){
        //首先确立剪枝条件
        //注意下标的特点不能够是word.length()-1
        if(start==word.length()){
            return true;
        }
        if(i<0 || i>=board.length || j<0 || j>=board[0].length || word.charAt(start)!=board[i][j] || visited[i][j] ){
            return false;
        }
        visited[i][j]=true;
        if( dfs(board,word,i,j+1,start+1,visited) || dfs(board,word,i,j-1,start+1,visited) || dfs(board,word,i-1,j,start+1,visited) || dfs(board,word,i+1,j,start+1,visited)){
            return true;
        }
        else{
            //回溯
            visited[i][j]=false;
            return false;
        }
    }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

200. 岛屿数量：
给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例 1：

输入：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出：1
1
2
3
4
5
6
7

思想：
我们可以将二维网格看成一个无向图，竖直或水平相邻的 1 之间有边相连。
为了求出岛屿的数量，我们可以扫描整个二维网格。如果一个位置为 1，则以其为起始节点开始进行深度优先搜索。在深度优先搜索的过程中，每个搜索到的 1 都会被重新标记为 0。
最终岛屿的数量就是我们进行深度优先搜索的次数。
代码：

class Solution {
    public int numIslands(char[][] grid) {
        int row=grid.length,col=grid[0].length;
        if(row==0||col==0) return 0;
        int sum=0;
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){
                if(grid[i][j]=='1'){
                dfs(grid,i,j,row,col);
                  sum++;
                }
            }
        }
            return sum;

    }
    void dfs(char[][]grid,int i,int j,int row,int col){
        if(i<0||i>=row||j<0||j>=col||grid[i][j]=='0') return;
        grid[i][j]='0';
        dfs(grid,i-1,j,row,col);
        dfs(grid,i+1,j,row,col);
        dfs(grid,i,j-1,row,col);
        dfs(grid,i,j+1,row,col);
    
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

补充：
「岛屿问题」是一个系列系列问题，比如：
200. 岛屿数量 （Easy）
463. 岛屿的周长 （Easy）
695. 岛屿的最大面积 （Medium）
827. 最大人工岛 （Hard）
多加练习。

二、广度优先

1.广度遍历（BFS）解决什么问题？

bfs一般解决最短路径的问题，广度优先的搜索的是从起始点出发，一层一层的进行，每层当中的点距离起始点的步数都是相同的。
补充：
双端BFS
同时从起始点和终点开始进行的广度优先的搜索成为双端bfs；
双端bfs可以大大提高效率：
例如：想判断社交应用程序中两个人之间需要多少朋友介绍才能互相认识。

2.算法思想：

在广度优先搜索算法中，解答树上结点的扩展是按它们在树中的层次进行的。首先生成第一层结点，同时检查目标结点是否在所生成的结点中，如果不在，则将所有的第一层结点逐一扩展，得到第二层结点，并检查第二层结点是否包含目标结点，……，对层次为n+1的任一结点进行扩展之前，必须先考虑层次完层次为n的结点的每种可能的状态。因此，对于同一层结点来说，求解问题的价值是相同的，可以按任意顺序来扩展它们。通常采用的原则是先生成的结点先扩展。
为了便于进行搜索，要设置一个表存储所有的结点。由于在广度优先搜索算法中，要满足先生成的结点先扩展的原则，所以存储结点的表一般采用队列这种数据结构。
在编写程序时，可用数组q模拟队列。front和rear分别表示队头指针和队尾指针，初始时front=rear=0。
元素x入队操作为 q[rear++]=x;
元素x出队操作为 x =q[front++];
广度优先搜索算法的搜索步骤一般是：
（1）从队列头取出一个结点，检查它按照扩展规则是否能够扩展，如果能则产生一个新结点。
（2）检查新生成的结点，看它是否已在队列中存在，如果新结点已经在队列中出现过，就放弃这个结点，然后回到第（1）步。否则，如果新结点未曾在队列中出现过，则将它加入到队列尾。
（3）检查新结点是否目标结点。如果新结点是目标结点，则搜索成功，程序结束；若新结点不是目标结点，则回到第（1）步，再从队列头取出结点进行扩展。
最终可能产生两种结果：找到目标结点，或扩展完所有结点而没有找到目标结点。
如果目标结点存在于解答树的有限层上，广度优先搜索算法一定能保证找到一条通向它的最佳路径，因此广度优先搜索算法特别适用于只需求出最优解的问题。当问题需要给出解的路径，则要保存每个结点的来源，也就是它是从哪一个节点扩展来的。
对于广度优先搜索算法来说，问题不同则状态结点的结构和结点扩展规则是不同的，但搜索的策略是相同的。广度优先搜索算法的框架一般如下：

void  BFS（）{
    队列初始化；
    初始结点入队；
    while （队列非空） {  
          队头元素出队，赋给current；
          while  （current 还可以扩展） {
              由结点current扩展出新结点new；
              if  （new 重复于已有的结点状态） continue;
              new结点入队；
              if  (new结点是目标状态){
                    置flag= true;    break; 
               }
          }
      }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

对于不同的问题，用广度优先搜索法的算法基本上都是一样的。但表示问题状态的结点数据结构、新结点是否为目标结点和是否为重复结点的判断等方面则有所不同。对具体的问题需要进行具体分析，这些函数要根据具体问题进行编写。

3、例题讲解：

运⽤⼴度优先搜索在迷宫中寻找最短的路径？
核心代码及思想：

void bfs(int[][] maze, int x, int y) {
##创建⼀个队列，将起始点加⼊队列中
 Queue<Integer[]> queue = new LinkedList<>();
 queue.add(new Integer[] {x, y});
 ##只要队列不为空，就⼀直循环下去
		 while (!queue.isEmpty()) {
		 从队列中取出当前要处理的点
 			Integer[] pos = queue.poll();
		 	x = pos[0]; y = pos[1];
				 ##在四个⽅向上进⾏BFS搜索
			 for (int d = 0; d < 4; d++) {
				 int i = x + dx[d], j = y + dy[d];
					## 判断⼀下该⽅向上的点是否已经访问过了
 						if (isSafe(maze, i, j)) {
 						##被访问过，则记录步数，并加⼊队列中
							 maze[i][j] = maze[x][y] + 1;
 							queue.add(new Integer[] {i, j});
 							##找到⽬的地后⽴即返回
							 if (i == B[0] && j == B[1]) return; 
				 } 
	 		} 
 		} 
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

Step 1：创建⼀个队列，将起始点加⼊队列中
Step 2：只要队列不为空，就⼀直循环下去
Step 3：从队列中取出当前要处理的点
Step 4：在四个⽅向上进⾏BFS搜索
Step 5：判断⼀下该⽅向上的点是否已经访问过了
Step 6：被访问过，则记录步数，并加⼊队列中
Step 7：找到⽬的地后⽴即返回

4、实站经典：

279. 完全平方数
给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

示例 1：
输入：n = 12
输出：3 
解释：12 = 4 + 4 + 4
示例 2：
输入：n = 13
输出：2
解释：13 = 4 + 9
1
2
3
4
5
6
7
8

解题思想：
给定一个 N 元树，其中每个节点表示数字 n 的余数减去一个完全平方数的组合，我们的任务是在树中找到一个节点，该节点满足两个条件：

(1) 节点的值（即余数）也是一个完全平方数。
(2) 在满足条件（1）的所有节点中，节点和根之间的距离应该最小。
下面是这棵树的样子：

从上到下逐层构造 N 元树。我们以 BFS（广度优先搜索）的方式遍历它。在 N 元树的每一级，我们都在枚举相同大小的组合。
遍历的顺序是 BFS，而不是 DFS（深度优先搜索），这是因为在用尽固定数量的完全平方数分解数字 n 的所有可能性之前，我们不会探索任何需要更多元素的潜在组合。
算法步骤：
首先，我们准备小于给定数字 n 的完全平方数列表。
然后创建 queue 遍历，该变量将保存所有剩余项在每个级别的枚举。
在主循环中，我们迭代 queue 变量。在每次迭代中，我们检查余数是否是一个完全平方数。如果余数不是一个完全平方数，就用其中一个完全平方数减去它，得到一个新余数，然后将新余数添加到 next_queue 中，以进行下一级的迭代。一旦遇到一个完全平方数的余数，我们就会跳出循环，这也意味着我们找到了解。
注意：在典型的 BFS 算法中，queue 变量通常是数组或列表类型。但是，这里我们使用 set 类型，以消除同一级别中的剩余项的冗余。事实证明，这个小技巧甚至可以增加 5 倍的运行加速。
代码：

class Solution {
  public int numSquares(int n) {

    ArrayList<Integer> square_nums = new ArrayList<Integer>();
    for (int i = 1; i * i <= n; ++i) {
      square_nums.add(i * i);
    }

    Set<Integer> queue = new HashSet<Integer>();
    queue.add(n);

    int level = 0;
    while (queue.size() > 0) {
      level += 1;
      Set<Integer> next_queue = new HashSet<Integer>();

      for (Integer remainder : queue) {
        for (Integer square : square_nums) {
          if (remainder.equals(square)) {
            return level;
          } else if (remainder < square) {
            break;
          } else {
            next_queue.add(remainder - square);
          }
        }
      }
      queue = next_queue;
    }
    return level;
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

三、拓扑排序

1、解决问题

利用bfs和dfs进行判环

2、实战经典：

207. 课程表
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。

例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
解题思路：
本题可约化为： 课程安排图是否是 有向无环图(DAG)。即课程间规定了前置条件，但不能构成任何环路，否则课程前置条件将不成立。
思路是通过 拓扑排序 判断此课程安排图是否是 有向无环图(DAG) 。 拓扑排序原理： 对 DAG 的顶点进行排序，使得对每一条有向边 (u, v)(u,v)，均有 uu（在排序记录中）比 vv 先出现。亦可理解为对某点 vv 而言，只有当 vv 的所有源点均出现了，vv 才能出现。
通过课程前置条件列表 prerequisites 可以得到课程安排图的 邻接表 adjacency，以降低算法时间复杂度，以下两种方法都会用到邻接表。
方法一：入度表（广度优先遍历）
算法流程：
统计课程安排图中每个节点的入度，生成 入度表 indegrees。
借助一个队列 queue，将所有入度为 0的节点入队。
当 queue 非空时，依次将队首节点出队，在课程安排图中删除此节点 pre：
并不是真正从邻接表中删除此节点 pre，而是将此节点对应所有邻接节点 cur 的入度 -1−1，即 indegrees[cur] -= 1。
当入度 -1后邻接节点 cur 的入度为 0，说明 cur 所有的前驱节点已经被 “删除”，此时将 cur 入队。
在每次 pre 出队时，执行 numCourses–；
若整个课程安排图是有向无环图（即可以安排），则所有节点一定都入队并出队过，即完成拓扑排序。换个角度说，若课程安排图中存在环，一定有节点的入度始终不为 0。
因此，拓扑排序出队次数等于课程个数，返回 numCourses == 0 判断课程是否可以成功安排。
代码：

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        int[] indegrees = new int[numCourses];
        List<List<Integer>> adjacency = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();
        for(int i = 0; i < numCourses; i++)
            adjacency.add(new ArrayList<>());
        // Get the indegree and adjacency of every course.
        for(int[] cp : prerequisites) {
            indegrees[cp[0]]++;
            adjacency.get(cp[1]).add(cp[0]);
        }
        // Get all the courses with the indegree of 0.
        for(int i = 0; i < numCourses; i++)
            if(indegrees[i] == 0) queue.add(i);
        // BFS TopSort.
        while(!queue.isEmpty()) {
            int pre = queue.poll();
            numCourses--;
            for(int cur : adjacency.get(pre))
                if(--indegrees[cur] == 0) queue.add(cur);
        }
        return numCourses == 0;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

方法二：深度优先遍历
算法流程：
借助一个标志列表 flags，用于判断每个节点 i （课程）的状态：
未被 DFS 访问：i == 0；
已被其他节点启动的 DFS 访问：i == -1；
已被当前节点启动的 DFS 访问：i == 1。
对 numCourses 个节点依次执行 DFS，判断每个节点起步 DFS 是否存在环，若存在环直接返回 FalseFalse。DFS 流程；
终止条件：
当 flag[i] == -1，说明当前访问节点已被其他节点启动的 DFS 访问，无需再重复搜索，直接返回 TrueTrue。
当 flag[i] == 1，说明在本轮 DFS 搜索中节点 i 被第 22 次访问，即 课程安排图有环 ，直接返回 FalseFalse。
将当前访问节点 i 对应 flag[i] 置 11，即标记其被本轮 DFS 访问过；
递归访问当前节点 i 的所有邻接节点 j，当发现环直接返回 FalseFalse；
当前节点所有邻接节点已被遍历，并没有发现环，则将当前节点 flag 置为 -1−1 并返回 TrueTrue。
若整个图 DFS 结束并未发现环，返回 TrueTrue。
代码：

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> adjacency = new ArrayList<>();
        for(int i = 0; i < numCourses; i++)
            adjacency.add(new ArrayList<>());
        int[] flags = new int[numCourses];
        for(int[] cp : prerequisites)
            adjacency.get(cp[1]).add(cp[0]);
        for(int i = 0; i < numCourses; i++)
            if(!dfs(adjacency, flags, i)) return false;
        return true;
    }
    private boolean dfs(List<List<Integer>> adjacency, int[] flags, int i) {
        if(flags[i] == 1) return false;
        if(flags[i] == -1) return true;
        flags[i] = 1;
        for(Integer j : adjacency.get(i))
            if(!dfs(adjacency, flags, j)) return false;
        flags[i] = -1;
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22