Posted by lily's blog on May 9, 2025

广搜和深搜

问题

什么题型适合使用广度优先搜索而不是深度优先搜索？

视具体题目要求的答案而定，因为不管是深搜还是广搜的基本定义都是从当前节点出发，向周围节点扩散搜索的搜索方法。

  • 深搜顾名思义就是先对某一条路径进行深度搜索（直到搜索至终点之后才会返回）。
  • 而广搜则是需要兼顾所有方向，每一个搜索方向的进度都是一样的，所有方向齐头并进，适合搜索节奏需要保持一致的题型，一般最短路径题型会用到广搜，因为所有方向的搜索同时进行，先找到终点的那条路径一定是最短路径。

总结：根据判断遍历的方式是否影响最终题目要求的结果而选择深搜或是广搜

举例： 如果题目只要求这张二维表格中的xxx所有值，那么二者皆可。 如果题目要问最快到达某个点的速度（时间/长度）是多少，那么广搜优先。

深搜的优点是代码简单（递归），且记忆化搜索后时间复杂度会降低（少了很多次递归调用） 广搜代码细节较多，且需要自己控制栈的进出

所以我们一般在搜索所有路径时选择深搜（广搜也可，但深搜简单），甚至在需要到达的路径简单的情况下（从出发点到终点没有其他的限制条件，反例：走迷宫需要判断中间条件，即某个方向能不能走），可以将搜索简化成动态规划解法，见题62. 不同路径

搜索的上下左右四个方向的含义是什么？

选择遍历哪些方向需要根据题型而定，例如腐烂的橘子一题994. 腐烂的橘子，橘子腐烂速度从腐烂橘子中心向四个方向扩展，那么就可以检索上下左右四个方向，并且需要标记已经遍历过的位置。例如类似寻找路径的题目：62. 不同路径，寻找达右下角的点的位置，要求不走回头路有多少种走法（走回头路的话算上各种折返恐怕答案量指数级增长了），这时我们走的方向必须只能向右或是向下。

例题

例如，200. 岛屿数量 这道题目既可以使用深搜也可以使用广搜，因为遍历的过程不影响

深搜代码

优化点是可以进行记忆化搜索，新增一个二维表格记录已经遍历过的节点的值，当再次搜索到时可以直接返回该值不需要继续递归

class Solution {

    public int numIslands(char[][] grid) {

        int n = grid.length;

        int ans = 0;

        for (int i=0;i<n;i++){

            for (int j=0;j<grid[i].length;j++){

                if (grid[i][j]=='1'){

                    dfs(i, j, grid);

                    ans++;

                }

            }

        }

        return ans;

    }

  

    private void dfs(int x, int y, char[][] grid){

        // 遇到边界说明找到岛屿边缘返回

        if (x>grid.length-1 || x<0 || y>grid[x].length-1 || y<0) return;

        // 或是遍历过了就返回

        if (grid[x][y] == '0') return;

        // 遇到1，将当前1改为0表示以及遍历过

        grid[x][y] = '0';

        // 遍历四个方向

        dfs(x+1, y, grid);

        dfs(x-1, y, grid);

        dfs(x, y+1, grid);

        dfs(x, y-1, grid);

        return;

    }

}

广搜代码

import java.util.LinkedList;
import java.util.Queue;

public class Solution {

    private final static int[][] DIRECTIONS =  {{-1, 0}, {0, -1}, {1, 0}, {0, 1}}; 

    private int rows;

    private int cols;

    private char[][] grid;

    private boolean[][] visited;


    public int numIslands(char[][] grid) {

        rows = grid.length;

        if (rows == 0) {

            return 0;

        }

        cols = grid[0].length;

        this.grid = grid;

        visited = new boolean[rows][cols];

  

        int count = 0;

        for (int i = 0; i < rows; i++) {

            for (int j = 0; j < cols; j++) {

                if (!visited[i][j] && grid[i][j] == '1') {

                    bfs(i, j);

                    count++;

                }

            }

        }

        return count;

    }

    private void bfs(int i, int j) {

        Queue<Integer> queue = new LinkedList<>();

        queue.offer(i * cols + j);

        // 注意：这里要标记上已经访问过

        visited[i][j] = true;

        while (!queue.isEmpty()) {

            int cur = queue.poll();

            int curX = cur / cols;

            int curY = cur % cols;

            for (int k = 0; k < 4; k++) {

                int newX = curX + DIRECTIONS[k][0];

                int newY = curY + DIRECTIONS[k][1];

                if (inArea(newX, newY) && grid[newX][newY] == '1' 
                && !visited[newX][newY]) {

                    queue.offer(newX * cols + newY);

                    // 特别注意：在放入队列以后，要马上标记成已经访问过，
                    // 语义也是十分清楚的：反正只要进入了队列，迟早都会遍历到它

                    // 而不是在出队列的时候再标记，如果是出队列的时候再标记，
                    // 会造成很多重复的结点进入队列，造成重复的操作，
                    // 这句话如果你没有写对地方，代码会严重超时的

                    visited[newX][newY] = true;

                }

            }

        }

    }

    private boolean inArea(int x, int y) {

        return x >= 0 && x < rows && y >= 0 && y < cols;
    }
}

有向图和无向图

有向图是否存在环

深搜

思路

  1. 创建 visited 数组用于记录每个节点是否被遍历过。维护一个onStack数组，用于记录深搜时递归调用栈中的节点。通过一个二维链表维护有向图的连邻表。
    • 连邻表：使用传入的关系数组去创建一个二维列表，二维列表的下标代表当前节点，下标对应列表中存储当前节点可以直接连接到的下一个节点。

  2. 对于没被遍历过的节点，进行深度搜索。

  3. 递归调用 DFS遍历当前节点的所有未访问的邻居节点，如果遇到一个在当前调用栈中已经访问过的邻居节点，说明存在环路，返回 true。否则全部遍历结束后在当前节点可达路径中未发现环路，返回false。

  4. 搜索完所有的节点都未发现环路说明这个有向图不存在环路。
private boolean[] visited;
private boolean[] onStack;

private boolean dfs(int vertex) {
    visited[vertex] = true;
    onStack[vertex] = true;

    for (int neighbor : adj[vertex]) {
        if (!visited[neighbor]) {
            if (dfs(neighbor)) {
                return true; // 发现环路
            }
        } else if (onStack[neighbor]) {
            return true; // 发现环路
        }
    }

    onStack[vertex] = false; // 完成当前节点的搜索
    return false; // 没有发现环路
}

public boolean hasCycle(int numberOfVertices) {
    visited = new boolean[numberOfVertices];
    onStack = new boolean[numberOfVertices];

    for (int i = 0; i < numberOfVertices; i++) {
        if (!visited[i]) {
            if (dfs(i)) {
                return true; // 图中存在环
            }
        }
    }
    return false; // 图中不存在环
}

代码

  1. 初始化连邻表
public boolean isCycle(int num, int[][] edge){
	
}

拓扑排序

因为拓扑排序的核心在于处理依赖关系。 如果图中存在环，某些节点的入度将永远不会变为 0，因为它们依赖于其他节点，而那些节点又依赖于它们自身或其他节点，从而形成闭环。

思路

  1. 统计连邻表的同时，计算入度， 对于图中的每个节点，即有多少条边指向该节点。

  2. 初始化队列，将所有入度为 0 的节点放入一个队列，表示这些节点没有前置依赖关系可以直接从此位置开始访问。

  3. 使用一个int型变量辅助记录所有出度可以变为0的节点。

  4. 从队列中取出一个节点，将其相邻节点的入度减 1。如果减 1 后该节点入度变为 0，则立即把这个邻节点添加到队列中。重复此步骤，直到队列为空。（直到所有入度为0，可以直接被处理的节点都被访问并且处理过）。

  5. 当队列为空后，循环结束，如果计数器的值等于图中的节点总数，说明所有节点都被处理，没有循环依赖关系，图中不存在环。如果计数器的值小于节点总数，说明有节点未被处理，图中存在环。

代码

例题

  • 判断逻辑的核心：通过入度和队列的管理，确保每个节点在没有依赖时可以被处理，从而判断图中是否存在环。
  • 时间复杂度：这个算法的时间复杂度是 O(V + E)，其中 V 是节点数，E 是边数。
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class TopologyTest {

	private List<Integer>[] adjacencyList;

	/**
	 * 判断是否存在环
	 * @param num 节点数
	 * @param edges 连线
	 * @return
	 */
	public boolean hasCycle(int num, int[][] edges){
		//记录每个节点的入度
		int[] indegree = new int[num];
		//初始化邻接表
		this.adjacencyList = new ArrayList[num];
		for(int i = 0; i < num; i++){
			//每个节点的相邻节点（节点0对应邻接表中第0个元素，依次类推）
			adjacencyList[i] = new ArrayList<>();
		}
		//根据线的走向计算节点的相邻节点
		for(int[] edge : edges){
			int from = edge[0];
			int to = edge[1];
			adjacencyList[from].add(to);
			indegree[to]++;
		}
		//使用队列存放所有入度为0的节点
		Queue<Integer> queue = new LinkedList<>();
		for(int i = 0; i < num; i++){
			if(indegree[i] == 0){
				queue.offer(i);
			}
		}
		int visited = 0;
		while(!queue.isEmpty()){
			int vertex = queue.poll();
			visited++;
			for(int neighbor : adjacencyList[vertex]){
				if(--indegree[neighbor] == 0){
					queue.add(neighbor);
				}
			}
		}
		return visited != num;
	}
	
}
FEATURED TAGS
JAVASE JavaWEB Spring python基础 学习工具 数据结构与算法 爬虫学习 计算机网络 springBoot BugNotice springSecurity projectLearning SQL
FRIENDS