图与 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<原节点, 克隆节点>，它既是访问标记，又提供「已经造好的替身」。

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    private final Map<Node, Node> cloned = new HashMap<>();

    public Node cloneGraph(Node node) {
        if (node == null) {
            return null;
        }
        if (cloned.containsKey(node)) {
            return cloned.get(node); // 替身已存在，直接复用
        }
        Node copy = new Node(node.val, new ArrayList<>());
        cloned.put(node, copy); // 先登记，再递归邻居，斩断环
        for (Node neighbor : node.neighbors) {
            copy.neighbors.add(cloneGraph(neighbor));
        }
        return copy;
    }
}

// 题目提供的节点类（这里给出以便代码完整）
class Node {
    public int val;
    public List<Node> neighbors;
    Node(int v, List<Node> n) { val = v; neighbors = n; }
}

逐点讲：「先放 map 再递归」与链表「断链前先存」同理，是处理所有含环引用的标准动作。时间 O(V+E)，空间 O(V)。

步骤 3：LeetCode 208「实现 Trie（前缀树）」（中等）

支持插入单词、判断单词是否存在、判断是否有单词以某前缀开头。

每个节点持有 26 个子节点槽和一个「单词是否在此结束」标记。

class Trie {
    private final Trie[] children = new Trie[26];
    private boolean endOfWord = false;

    public Trie() {
    }

    public void insert(String word) {
        Trie node = this;
        for (char c : word.toCharArray()) {
            int i = c - 'a';
            if (node.children[i] == null) {
                node.children[i] = new Trie(); // 路径不存在才新建
            }
            node = node.children[i];
        }
        node.endOfWord = true;
    }

    public boolean search(String word) {
        Trie node = walk(word);
        return node != null && node.endOfWord;
    }

    public boolean startsWith(String prefix) {
        return walk(prefix) != null; // 前缀不要求正好结束
    }

    // 沿前缀走到对应节点；中途断了返回 null
    private Trie walk(String s) {
        Trie node = this;
        for (char c : s.toCharArray()) {
            int i = c - 'a';
            if (node.children[i] == null) {
                return null;
            }
            node = node.children[i];
        }
        return node;
    }
}

逐点讲：插入与查询都是 O(L)（L 为单词长度），空间 O(总字符数)。相比哈希，Trie 天然支持前缀枚举（搜索联想），且大量单词共享前缀时更省空间；search 与 startsWith 只差一个结束标记的判断。

讲清楚要点

1. 图遍历的第一件事是判重：visited / map 保证每个节点只处理一次，无向图和含环有向图没有它会无限循环。
2. 网格图不需要真建邻接表：四个方向的偏移就是隐式边，边界检查代替了「邻居是否存在」。
3. 克隆图的 map 一身二任：访问集合 + 旧→新映射，先登记后递归是破环关键。
4. Trie 节点的核心是「子槽 + 结束标记」：节点本身不存字符，字符由父节点槽位的下标隐含。
5. DFS 省代码、BFS 省栈且天然求最短步数：迷宫最少步数类问题（LeetCode 994 腐烂橘子）直接 BFS。

你可能会懵的地方

• 图题什么时候必须用 BFS 而不能用 DFS？ 求「无权图最短步数 / 层数」时 BFS 最直接（首次到达即最短）；DFS 也能做但要遍历所有路径取最小。只问可达性、连通分量时两者等价。

• 岛屿题为什么可以直接改原网格？不怕破坏输入吗？ LeetCode 函数内修改入参是允许的，相当于用输入本身做 visited，省一块 O(RC) 内存。工程代码若调用方还要用该网格，就不能这么做，要另开标记数组。

• 克隆图为什么要在递归邻居之前就 put 进 map？ 若递归完再 put，遇到环时第二次进入同一节点发现 map 里还没有，又从头复制，无限递归。先 put 让「未来的自己」能找到替身。

• Trie 相比 HashMap 存单词到底强在哪？ 三点：前缀查询（给 "app" 列出所有以此开头的词）、按字典序遍历、共享前缀省空间。精确匹配单个词，HashMap 期望 O(1) 更快，所以按需求选。

• 递归 DFS 在大网格上栈溢出怎么办？ 改显式栈（ArrayDeque 压坐标）或队列 BFS，内存走堆不受线程栈限制，和树的迭代化同一个道理。

错法对照

错法	问题	正解
图 DFS 不标记访问	无向图来回弹、永不返回	进节点先标记
岛屿标记只在当前格不递归四周	每块陆地各算一座岛	DFS 淹没整片连通陆地
克隆图递归完邻居才登记 map	含环时无限递归	先 put 副本再处理边
Trie 查询把「路径存在」当「单词存在」	如插入 apple 却搜 app 判真	还要看 endOfWord
邻居入队/入栈不判边界	数组越界	先校验行列范围

卡点急救

1. 网格 DFS 越界异常不断：把边界检查写成一行统一拦在函数开头（r/c 出界直接 return），后续逻辑只面对合法格子。
2. 克隆结果节点数对但邻居关系错：确认每个邻居 add 的都是「cloneGraph 返回的替身」而不是原节点，深拷贝才算完成。
3. Trie 分不清 search 和 startsWith：它们共用同一条路径遍历，区别只在最后是否要求 endOfWord，抽一个 walk 公共方法即可。

面试常问

• 如何求网格中岛屿的最大面积（LeetCode 695）？ 同一套 DFS，函数返回本次淹没的格子数（1 + 四个方向递归之和），遍历中维护最大值。岛屿数量的一行改造，常作为 200 的追问。

• 社交 App 的「可能认识的人」（二度好友）怎么算？ 从用户节点做两层 BFS：一层取直接好友，二层取好友的好友，排除自己和一度好友，按共同好友数排序。规模大时用图数据库（Neo4j）或分布式图计算，单机思路就是 BFS。

• 搜索框输入联想功能怎么实现？ Trie 存热词，沿输入前缀走到节点后，DFS 收集该子树下结束标记对应的词，再按热度截断；超大规模可在各节点缓存 Top 联想词。敏感词过滤则用 Trie 的变体 AC 自动机，一次扫描文本匹配多词。

自测三问

1. 图遍历相比树遍历，为什么必须有访问标记？
2. 克隆图中 map 的两个作用是什么？为什么登记顺序不能后置？
3. Trie 的 search 与 startsWith 差异在哪？它相对哈希解决了什么独有问题？

小结一句话

图题 = DFS/BFS 加访问纪律：网格用四向隐边、克隆用 map 破环、Trie 用子槽与结束标记把前缀查询压到单词长度。

延伸

• 巩固练习：LeetCode 695 岛屿的最大面积、LeetCode 994 腐烂的橘子、LeetCode 212 单词搜索 II
• 在本站在线判题平台提交，试试空图、单节点无邻居、全是水的网格
• 下一课预告（收官）：动态规划入门——爬楼梯、背包、最长递增子序列、编辑距离，学会「记住算过的结果」