算法-图的遍历广度优先 BFS 和深度优先 DFS

一、图的两种基础存储结构

图的本质是「节点+边」的集合，分为有向图、无向图、带权图、无权图。最常用的只有两种存储方式：邻接矩阵、邻接表。

1. 邻接矩阵

用二维数组存储图的连通关系，适合节点数量少、稠密图（边多）的场景。

定义规则：假设 graph 为 n*n 矩阵

graph[i][j] = 1：表示节点 i 和节点 j 之间有边相连
graph[i][j] = 0：表示节点 i 和节点 j 无连通边

优缺点：

优点：判断两点是否连通 O(1)，实现简单
缺点：空间复杂度高 O(n²)，稀疏图浪费空间

Java 定义

// n 为节点总数
int n = 5;
// 初始化n阶邻接矩阵
int[][] graph = new int[n][n];

// 构建无向图：0-1、1-2、2-3相连
graph[0][1] = 1;
graph[1][0] = 1;
graph[1][2] = 1;
graph[2][1] = 1;
graph[2][3] = 1;
graph[3][2] = 1;

2. 邻接表

用列表嵌套列表的方式存储，只记录每个节点的相邻节点，是最常用的存储方式，适配稀疏图。

定义规则：graph.get(i) 是一个列表，存储所有与节点 i 直接相连的节点。

优缺点：

优点：空间利用率高，遍历速度快，适配大规模节点
缺点：判断两点连通需要遍历邻接列表，效率略低

Java 定义

import java.util.ArrayList;
import java.util.List;

public class GraphDemo {
    public static void main(String[] args) {
        // n 为节点总数
        int n = 5;
        // 初始化邻接表
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }

        // 构建无向图：0-1、1-2、2-3相连
        graph.get(0).add(1);
        graph.get(1).add(0);
        graph.get(1).add(2);
        graph.get(2).add(1);
        graph.get(2).add(3);
        graph.get(3).add(2);
    }
}

二、图的两种遍历方式

图遍历的难点：存在环，必须记录已访问节点，避免死循环。所有遍历都需要搭配 visited 访问数组去重，下面统一使用邻接表实现。

1. DFS 深度优先遍历

关键思路：一条路走到黑，走不通再回溯。优先递归遍历当前节点的第一个邻接点，直到没有未访问节点，再退回上一层遍历其他节点。

适用场景：岛屿问题、路径查找、连通分量统计、拓扑排序

Java 邻接表 DFS 通用模板

import java.util.ArrayList;
import java.util.List;

public class DfsDemo {
    // DFS递归遍历
    public static void dfs(int node, List<List<Integer>> graph, boolean[] visited) {
        // 标记当前节点已访问
        visited[node] = true;
        System.out.print(node + " ");

        // 遍历当前节点所有邻接节点
        for (int neighbor : graph.get(node)) {
            if (!visited[neighbor]) {
                dfs(neighbor, graph, visited);
            }
        }
    }

    public static void main(String[] args) {
        int n = 5;
        // 构建测试图
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        graph.get(0).add(1);
        graph.get(1).add(0);
        graph.get(1).add(2);
        graph.get(2).add(1);
        graph.get(2).add(3);
        graph.get(3).add(2);

        boolean[] visited = new boolean[n];
        // 遍历所有节点，处理非连通图
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfs(i, graph, visited);
            }
        }
    }
}

2. BFS 广度优先遍历

核心思路：层层扩散，逐层遍历。借助队列实现，先遍历当前节点的所有邻接点，再依次遍历邻接点的邻接点。

适用场景：最短路径、层序遍历、最小步数、拓扑排序

Java 邻接表 BFS 通用模板

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class BfsDemo {
    public static void bfs(int start, List<List<Integer>> graph, boolean[] visited) {
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);
        visited[start] = true;

        while (!queue.isEmpty()) {
            int node = queue.poll();
            System.out.print(node + " ");

            // 遍历所有邻接节点
            for (int neighbor : graph.get(node)) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.offer(neighbor);
                }
            }
        }
    }

    public static void main(String[] args) {
        int n = 5;
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            graph.add(new ArrayList<>());
        }
        graph.get(0).add(1);
        graph.get(1).add(0);
        graph.get(1).add(2);
        graph.get(2).add(1);
        graph.get(2).add(3);
        graph.get(3).add(2);

        boolean[] visited = new boolean[n];
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                bfs(i, graph, visited);
            }
        }
    }
}

三、算法题举例

两道算法题，分别对应 DFS、BFS 的核心用法：

1. 岛屿数量（DFS 经典）

题目描述：给你一个由 '1'（陆地）和 '0'（水）组成的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿由相邻的陆地拼接而成（上下左右相邻）。

思路：

遍历网格每一个格子，遇到未访问的陆地，岛屿数+1
通过 DFS 深度遍历，将该岛屿所有相连陆地标记为已访问（直接置0去重）
遍历完成后，统计总岛屿数量

Java 代码

class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) {
            return 0;
        }

        int m = grid.length;
        int n = grid[0].length;
        int count = 0;

        // 遍历整个网格
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 发现未访问的陆地
                if (grid[i][j] == '1') {
                    count++;
                    dfs(grid, i, j);
                }
            }
        }
        return count;
    }

    // 深度优先遍历，淹没当前岛屿
    private void dfs(char[][] grid, int i, int j) {
        int m = grid.length;
        int n = grid[0].length;
        // 越界或者不是陆地，直接返回
        if (i < 0 || i >= m || j < 0 || j >= n || grid[i][j] == '0') {
            return;
        }

        // 标记为已访问（原地修改，省去visited数组）
        grid[i][j] = '0';

        // 上下左右四个方向递归遍历
        dfs(grid, i + 1, j);
        dfs(grid, i - 1, j);
        dfs(grid, i, j + 1);
        dfs(grid, i, j - 1);
    }
}

总结：网格图是特殊的邻接图，无需提前建表，直接通过上下左右遍历。采用原地修改网格的方式去重，节省空间。DFS 快速淹没整片连通陆地，统计连通块数量。

2. 01矩阵（BFS 层序最短路径）

题目描述：给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的最短距离。两个相邻元素间的距离为 1 。

解题思路：

以所有0为起点，同时向外层扩散 BFS
BFS 天然层序遍历，首次访问到1时的层数，就是最短距离
初始化队列存入所有0节点，标记已访问，逐层更新距离

Java代码

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

class Solution {
    public int[][] updateMatrix(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        int[][] dist = new int[m][n];
        boolean[][] visited = new boolean[m][n];
        Queue<int[]> queue = new LinkedList<>();

        // 方向数组：上下左右
        int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

        // 所有0节点入队，作为BFS起点
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 0) {
                    queue.offer(new int[]{i, j});
                    visited[i][j] = true;
                }
            }
        }

        // 多起点BFS逐层扩散
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int x = cur[0];
            int y = cur[1];

            for (int[] dir : dirs) {
                int nx = x + dir[0];
                int ny = y + dir[1];
                // 合法坐标且未访问
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny]) {
                    dist[nx][ny] = dist[x][y] + 1;
                    visited[nx][ny] = true;
                    queue.offer(new int[]{nx, ny});
                }
            }
        }
        return dist;
    }
}

总结：BFS 是无权图最短路径的最优解，多起点 BFS 是这道题的技巧。

四、图算法总结

稀疏图、大规模节点：优先用邻接表（List<List<Integer>>）；小规模稠密图：可用二维数组邻接矩阵
路径搜索、连通分量、回溯问题、网格淹没：用 DFS（递归实现简洁好写）
最短路径、最小步数、层序扩散、多起点遍历：用 BFS（队列实现）
优先原地修改数组/矩阵去重，减少 visited 数组创建，代码更精简、效率更高

算法