图的表示与遍历（BFS/DFS）

图的基本概念

有向图 vs. 无向图：边是否有方向。
有权图 vs. 无权图：边是否有权重。
度（Degree）：节点的边数；有向图分为入度（in-degree）和出度（out-degree）。

图的存储方式

邻接列表（Adjacency List）

// n 个节点（编号 0 到 n-1）
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
// 添加边 u → v
graph.get(u).add(v);
// 无向图还需：graph.get(v).add(u);

空间：O(V + E)，适合稀疏图（大多数图）。

邻接矩阵（Adjacency Matrix）

int[][] grid = new int[n][n];
grid[u][v] = 1;  // 或权重 w

空间：O(V²)，适合稠密图，查询 (u,v) 是否相邻为 O(1)。

深度优先搜索（DFS）

DFS 沿一条路径不断深入，直到无法再走才回退。

boolean[] visited;

void dfs(List<List<Integer>> graph, int node) {
    visited[node] = true;
    System.out.println(node);  // 访问节点
    for (int neighbor : graph.get(node)) {
        if (!visited[neighbor]) {
            dfs(graph, neighbor);
        }
    }
}

// 调用（处理非连通图需遍历所有节点）
void dfsAll(List<List<Integer>> graph, int n) {
    visited = new boolean[n];
    for (int i = 0; i < n; i++) {
        if (!visited[i]) dfs(graph, i);
    }
}

时间：O(V + E)，空间：O(V)（递归栈 + visited 数组）。

DFS 应用：岛屿数量

int numIslands(char[][] grid) {
    int rows = grid.length, cols = grid[0].length;
    int count = 0;
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] == '1') {
                count++;
                dfsIsland(grid, r, c);  // 沉没整个岛屿
            }
        }
    }
    return count;
}

void dfsIsland(char[][] grid, int r, int c) {
    if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length
        || grid[r][c] != '1') return;
    grid[r][c] = '0';  // 标记为已访问（沉没）
    dfsIsland(grid, r + 1, c);
    dfsIsland(grid, r - 1, c);
    dfsIsland(grid, r, c + 1);
    dfsIsland(grid, r, c - 1);
}

广度优先搜索（BFS）

BFS 层层扩展，先访问近邻，再访问远邻。用队列实现。

int bfs(List<List<Integer>> graph, int start, int target) {
    boolean[] visited = new boolean[graph.size()];
    Queue<Integer> queue = new LinkedList<>();
    queue.offer(start);
    visited[start] = true;
    int steps = 0;
    while (!queue.isEmpty()) {
        int size = queue.size();
        for (int i = 0; i < size; i++) {  // 一次处理一层
            int node = queue.poll();
            if (node == target) return steps;
            for (int neighbor : graph.get(node)) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.offer(neighbor);
                }
            }
        }
        steps++;
    }
    return -1;  // 未找到
}

BFS 的最短路径：在无权图中，BFS 遍历到目标节点时的层数，就是从源点到目标的最短路径长度。

时间：O(V + E)，空间：O(V)（队列 + visited）。

BFS 应用：最短路径（二进制矩阵）

int shortestPathBinaryMatrix(int[][] grid) {
    int n = grid.length;
    if (grid[0][0] == 1 || grid[n-1][n-1] == 1) return -1;
    int[][] dirs = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
    Queue<int[]> q = new LinkedList<>();
    q.offer(new int[]{0, 0, 1});  // (行, 列, 路径长度)
    grid[0][0] = 1;               // 标记已访问
    while (!q.isEmpty()) {
        int[] cur = q.poll();
        int r = cur[0], c = cur[1], len = cur[2];
        if (r == n-1 && c == n-1) return len;
        for (int[] d : dirs) {
            int nr = r + d[0], nc = c + d[1];
            if (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] == 0) {
                grid[nr][nc] = 1;
                q.offer(new int[]{nr, nc, len + 1});
            }
        }
    }
    return -1;
}

克隆图

深拷贝一张无向图。用 HashMap 保存「原节点 → 克隆节点」的映射，避免重复克隆。

Map<Node, Node> visited = new HashMap<>();

Node cloneGraph(Node node) {
    if (node == null) return null;
    if (visited.containsKey(node)) return visited.get(node);
    Node clone = new Node(node.val);
    visited.put(node, clone);
    for (Node neighbor : node.neighbors) {
        clone.neighbors.add(cloneGraph(neighbor));
    }
    return clone;
}

连通分量

无向图的连通分量：可以互相到达的最大节点集合。遍历所有未访问节点，每次 DFS 就是一个连通分量。

int countComponents(int n, int[][] edges) {
    List<List<Integer>> graph = new ArrayList<>();
    for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
    for (int[] e : edges) {
        graph.get(e[0]).add(e[1]);
        graph.get(e[1]).add(e[0]);
    }
    boolean[] visited = new boolean[n];
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            dfs(graph, visited, i);
            count++;
        }
    }
    return count;
}

DFS vs. BFS 选择指南

有向图中的环检测

使用三色标记：白（0）= 未访问，灰（1）= 正在访问，黑（2）= 已完成。

int[] color;
boolean hasCycle;

void detectCycleDFS(List<List<Integer>> graph, int node) {
    color[node] = 1;  // 灰：正在访问
    for (int neighbor : graph.get(node)) {
        if (color[neighbor] == 1) { hasCycle = true; return; }  // 碰到灰节点 → 有环
        if (color[neighbor] == 0) detectCycleDFS(graph, neighbor);
    }
    color[node] = 2;  // 黑：已完成
}

小结

• 邻接表是图最常用的存储方式，空间 O(V+E)
• DFS 递归实现简洁，适合路径、连通性、拓扑；注意用 visited 防止重复访问
• BFS 天然按层扩展，适合最短路径、最小步数问题
• 遍历非连通图时，需外层循环遍历所有节点