图与 Trie：关系网络与前缀查询

这一课你将能做到

1. 区分图的 DFS 与 BFS，并知道网格类问题如何把格子当节点
2. 用「访问标记 + 邻居复制」完成无向图克隆，避免死循环
3. 手写前缀树（Trie）的插入、查找、前缀匹配，说出它相对哈希的优势

为什么要学

树是「一个父节点」的受限结构，图则放开了一切限制：任意节点间都可以有边，社交关系、路网、微服务调用链、依赖打包（Maven 的依赖树其实常成环成图）都是图。图算法是面试中后段的常客，也是后端系统设计的常识：导航算路用 Dijkstra、信息流推荐用图遍历、死锁检测本质是环检测。

本课选三个最具代表性的入口：岛屿数量（网格 DFS，把二维坐标当节点）、克隆图（理解图遍历中「已访问」标记的双重作用）、前缀树 Trie（搜索框联想、敏感词匹配、路由前缀匹配的底层结构，本站站内搜索的关键词提示也用得上）。这三题打通，图类题就有了通用的腿脚。

先建立图像

图的两种遍历与树一致，区别只在于图必须防重复访问：

DFS：栈/递归，一条路走到底再退回
BFS：队列，像水波一样一圈圈扩展
访问标记：visited 集合，防止沿边走回已处理节点（无向图尤其必要）

网格映射为图：每个格子是节点，上下左右相邻即有边：

网格              坐标邻居
1 1 0             (r,c) 的邻居：
1 0 0              (r-1,c) (r+1,c) (r,c-1) (r,c+1)
0 1 1            走之前检查：不出界 + 是陆地 + 未访问

Trie 的长相：

  root
  /  \
 a    b
 |    |
 p    y → 单词结束
/ \
p→  p→（app、apple 共用前缀，分叉处共享节点）

跟着做

步骤 1：LeetCode 200「岛屿数量」（中等）

二维网格里 '1' 是陆地、'0' 是水，上下左右相连的陆地算一座岛，求岛的数量。

算法：遍历每个格子；遇到一块没访问过的陆地，岛数 +1，然后用 DFS 把与它相连的整片陆地全部标记为已访问（沉岛处理：直接改成 '0'）。

class Solution {
    public int numIslands(char[][] grid) {
        int count = 0;
        for (int r = 0; r < grid.length; r++) {
            for (int c = 0; c < grid[0].length; c++) {
                if (grid[r][c] == '1') {
                    count++;
                    dfs(grid, r, c);
                }
            }
        }
        return count;
    }

    private void dfs(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'; // 标记访问（就地修改，省掉 visited 数组）
        dfs(grid, r - 1, c);
        dfs(grid, r + 1, c);
        dfs(grid, r, c - 1);
        dfs(grid, r, c + 1);
    }
}

逐点讲：时间 O(R·C)（每格至多处理一次），空间 O(R·C)（最坏全陆地时递归栈深度）。把 DFS 换成队列就是 BFS，可避免深递归栈溢出。

步骤 2：LeetCode 133「克隆图」（中等）

给定一个无向连通图中某节点的引用，返回图的深拷贝。节点结构为 val 和邻居列表。

关键：边是共享的，不能无脑递归（A 复制时要复制 B，B 又要复制 A → 无限递归）。用一个 Map<原节点, 克隆节点>，它既是访问标记，又提供「已经造好的替身」。