每日算法 — 使用java实现单词接龙：双向BFS与Trie邻接生成

单词接龙（Word Ladder）是一条「每步只改一个字母、每一步都必须是词典里的单词」的最短变换路径。它看起来像个文字游戏，本质却是无权图上的最短路问题：把每个单词当成图节点，把「差一个字母」当成边，问题就变成了标准 BFS。

难点不在 BFS 本身，而在两处：邻接怎么生成得快（1129 个四字母词的全对比较是 63 万次字符串比较），以及搜索空间怎么砍。本文用 Java 实现 Trie 词典、双向 BFS 与 A*，并给出实测的访问节点数对比——同一个 5 步问题，单向 BFS 要访问 450 个节点，双向 BFS 只要 22 个。

一、问题建模：从文字游戏到图论

规则：给定起点 from、终点 to 和一个等长单词词典，每次只能改一个字母，中间经过的每一个字符串都必须在词典里。求最短步数路径。

抽象成图：

• 节点 = 词典中的每个单词
• 边 = 两个单词恰好相差 1 个字母
• 边权 = 1（每次变换代价相同）

于是这就是一个无权无向图的最短路径问题。BFS 从起点按层扩展，第一次碰到终点时的层数就是最短步数——这一点由 BFS 的「层序性」保证。

以 cold → warm 为例，最短路径是 4 步：

cold → cord → word → worm → warm

每步恰好改一个字母，且全部在词典中。

二、邻接生成：为什么不能两两比较

最直观的做法是预先把所有单词两两比较，差一个字母就建边。代价是 O(N² × L)：1129 个词的词典就是 1129²/2 ≈ 63.7 万次比较，每次比较 4 个字符——在搜索前就要跑几十毫秒，而且词典一旦到 5 位数（如 5 字母的 8000+ 词、6 字母的两万多词），O(N²) 直接爆炸。

正确做法是「按需生成邻接」：给定一个词，枚举「替换第 i 个字母为 a~z」的 26 × L 个候选，逐个查词典是否存在。复杂度 O(26 × L)，与词典规模无关。

    /** 枚举单词 w 的所有单字母替换邻居（26 * L 次探测） */
    List<String> neighbors(String w) {
        List<String> out = new ArrayList<>();
        char[] buf = w.toCharArray();
        for (int i = 0; i < buf.length; i++) {
            char old = buf[i];
            for (char c = 'a'; c <= 'z'; c++) {
                if (c == old) continue;
                buf[i] = c;
                String cand = new String(buf);
                if (contains(cand)) out.add(cand);
            }
            buf[i] = old;
        }
        return out;
    }

四个字母时，每个词最多探测 26 × 4 = 104 次，其中 4 次是自己（跳过）。对比 O(N²) 的 63 万次，邻接生成从「预计算全局」变成「按需局部」，这是双向 BFS 能高效运行的前提。

注意 buf[i] = old 这行复位——忘了它会让后续位置的替换基于被污染的缓冲区，产生错误的邻居集合。这是字符串原地修改的经典陷阱。

Trie：把「查词典」变成逐字符剪枝

contains(cand) 每次用 HashSet 查一次，哈希计算本身要遍历 4 个字符。更快的方案是 Trie：边构造候选词边沿 Trie 下行，一旦某个前缀不存在就立刻放弃整批候选。

final class TrieNode {
    final Map<Character, TrieNode> children = new HashMap<>();
    boolean end;
}

    private void insert(String w) {
        TrieNode cur = root;
        for (char c : w.toCharArray()) {
            cur = cur.children.computeIfAbsent(c, k -> new TrieNode());
        }
        cur.end = true;   // 标记词尾
    }

在 neighbors 中，只需要在第 i 位替换时检查「前缀 w[0..i-1] 沿 Trie 是否可走」，若可走再拼完整词查一次。对于 4 字母词，Trie 带来的剪枝幅度有限（前缀太短），但对 6 字母以上的词能省掉大量无效候选。

工程上更实用的写法是：把 Trie 下行结果缓存成「前缀节点」，只对可通过的前缀做后续替换。下面是把两者结合后的邻接生成：

    /** 带 Trie 前缀剪枝的邻居生成 */
    List<String> neighbors(String w) {
        List<String> out = new ArrayList<>();
        char[] buf = w.toCharArray();
        for (int i = 0; i < buf.length; i++) {
            char old = buf[i];
            // 定位到第 i 位之前的 Trie 节点，前缀不可达则整位跳过
            TrieNode prefixNode = root;
            for (int k = 0; k < i; k++) {
                prefixNode = prefixNode.children.get(buf[k]);
                if (prefixNode == null) return out;
            }
            for (char c = 'a'; c <= 'z'; c++) {
                if (c == old) continue;
                TrieNode next = prefixNode.children.get(c);
                if (next == null) continue;          // 该前缀不存在，跳过
                buf[i] = c;
                String cand = new String(buf);
                if (words.contains(cand)) out.add(cand);
                buf[i] = old;
            }
        }
        return out;
    }

这里 next == null 的检查就是剪枝：如果「前 i-1 个字符 + 新字母」构不成任何词典词的前缀，后面 3 个字母的组合完全不必尝试。

三、双向 BFS：从两端同时对撞

单向 BFS 从起点向外扩张，每一层节点数按分支因子增长。单词接龙的分支因子约为 20~80（取决于词典稠密度），于是第 d 层的规模是 b^d——5 步的搜索要覆盖几万个节点。

双向 BFS 同时从起点和终点向外扩展，两侧在第 d/2 层附近相遇。总访问量从 O(b^d) 降到 O(b^{d/2} + b^{d/2}) = O(b^{d/2})，理论上直接省掉半个指数的规模。

关键实现细节：每次扩展「当前规模较小的那一侧」。这保证了两个搜索「波前」大致等速推进，相遇发生在中点附近，而不是一侧早早扑到终点附近才发现另一侧还很小。

    /** 双向 BFS：从两端同时扩展，交界即最短路 */
    List<String> bidirectionalBfs(Dictionary dict, String from, String to) {
        if (!dict.contains(from) || !dict.contains(to)) return null;
        if (from.equals(to)) return Arrays.asList(from);

        Map<String, String> parentF = new HashMap<>();
        Map<String, String> parentB = new HashMap<>();
        Deque<String> qf = new ArrayDeque<>();
        Deque<String> qb = new ArrayDeque<>();

        parentF.put(from, null);      // null 表示起点，用作路径回溯的终点
        parentB.put(to, null);
        qf.add(from);
        qb.add(to);

        while (!qf.isEmpty() && !qb.isEmpty()) {
            // 关键：每次扩展较小的一层，控制两侧规模平衡
            if (qf.size() <= qb.size()) {
                String meet = expand(dict, qf, parentF, parentB);
                if (meet != null) return buildPath(parentF, parentB, meet, from, to);
            } else {
                String meet = expand(dict, qb, parentB, parentF);
                if (meet != null) return buildPath(parentF, parentB, meet, from, to);
            }
        }
        return null;                  // 两侧都扩展完仍未相遇 → 不连通
    }

    /** 扩展一层，返回与另一侧相遇的节点 */
    private String expand(Dictionary dict, Deque<String> queue,
                          Map<String, String> mine, Map<String, String> other) {
        int size = queue.size();       // 锁住本层节点数，只扩这一层
        for (int k = 0; k < size; k++) {
            String cur = queue.poll();
            for (String nb : dict.neighbors(cur)) {
                if (mine.containsKey(nb)) continue;
                mine.put(nb, cur);
                if (other.containsKey(nb)) return nb;   // 撞上另一侧已访问节点
                queue.add(nb);
            }
        }
        return null;
    }

三个容易写错的点：

1. int size = queue.size() 必须提前锁住。如果写 for (int k = 0; k < queue.size(); k++)，循环条件会随队列增长而推后，导致「一层变两层」，最短路层数就不准了。
2. 相遇检测应在「加入自己已访问集合时」立即做，而不是等这一层扩展完。这样第一次相遇就是最短路径的相遇。
3. parent 用 ConcurrentHashMap 不需要：单线程 BFS 用 HashMap，null 值表示「起点」是合法用法（HashMap 允许 null value）。

路径回溯：两个方向拼接

parentF 从起点向相遇点回溯，parentB 从终点向相遇点回溯（注意反向链的方向），最后拼接：

    private List<String> buildPath(Map<String, String> pf, Map<String, String> pb,
                                   String meet, String from, String to) {
        // 前向半段：meet -> from 回溯后反转
        List<String> left = new ArrayList<>();
        for (String p = meet; p != null; p = pf.get(p)) left.add(p);
        java.util.Collections.reverse(left);

        // 后向半段：meet 的下一个节点（pb.get(meet)）一路回到 to
        List<String> right = new ArrayList<>();
        for (String p = pb.get(meet); p != null; p = pb.get(p)) right.add(p);

        List<String> all = new ArrayList<>(left);
        all.addAll(right);
        return all;
    }

注意 right 的循环起点是 pb.get(meet) 而不是 meet——否则 meet 会在路径中出现两次。

四、A*：给 BFS 加一个可采纳的启发式

BFS 是「盲目」的，它按层均匀扩张，不考虑「哪个方向更接近终点」。A 用一个可采纳（admissible，不高估真实代价）*的启发函数给节点排优先级：

f(n) = g(n) + h(n)
      g(n) = 从起点到 n 的实际步数
      h(n) = 从 n 到终点的代价下界估计

对单词接龙，最自然的启发式是字母差异数：

    private int h(String a, String b) {
        int diff = 0;
        for (int i = 0; i < a.length(); i++) {
            if (a.charAt(i) != b.charAt(i)) diff++;
        }
        return diff;
    }

为什么它可采纳？每次变换只能改 1 个字母，所以把 a 变成 b 至少需要 diff 步。这个下界绝不会高估真实代价，因此 A* 找到的解一定是最优解。

实现上，PriorityQueue 的比较器需要动态读取 g 值，所以把 g 存在外部 Map 里，用 (a, b) -> compare(g.get(a) + h(a, to), g.get(b) + h(b, to)) 做排序：

    /** A*：h = 与目标的字母差异数（可采纳，绝不低估） */
    List<String> aStar(Dictionary dict, String from, String to) {
        if (!dict.contains(from) || !dict.contains(to)) return null;
        Map<String, Integer> g = new HashMap<>();
        Map<String, String> parent = new HashMap<>();
        java.util.PriorityQueue<String> open = new java.util.PriorityQueue<>(
                (a, b) -> Integer.compare(g.get(a) + h(a, to), g.get(b) + h(b, to)));
        g.put(from, 0);
        parent.put(from, null);
        open.add(from);

        while (!open.isEmpty()) {
            String cur = open.poll();
            if (cur.equals(to)) {
                List<String> path = new ArrayList<>();
                for (String p = to; p != null; p = parent.get(p)) path.add(p);
                java.util.Collections.reverse(path);
                return path;
            }
            int gu = g.get(cur);
            for (String nb : dict.neighbors(cur)) {
                int ng = gu + 1;
                if (ng < g.getOrDefault(nb, Integer.MAX_VALUE)) {
                    g.put(nb, ng);
                    parent.put(nb, cur);
                    open.add(nb);
                }
            }
        }
        return null;
    }

一个必须知道的工程缺陷：这个朴素 A* 用的是「惰性删除」——不删队列里的旧条目，只在 poll 时若发现 g 值已更新就跳过。但上面的代码没有做这个检查，同一节点可能被重复处理。正确写法是在 poll 后比对：

            String cur = open.poll();
            // 惰性删除：若队列里的 g 已过期，丢弃这条记录
            if (g.containsKey(cur) && ... ) { /* 需要额外存 (node, gAtPush) */ }

为了简洁，也可以在 poll 后检查「该节点是否已作为当前最短被处理过」，用一个 closed 集合：

        Set<String> closed = new HashSet<>();
        while (!open.isEmpty()) {
            String cur = open.poll();
            if (!closed.add(cur)) continue;      // 已用最优 g 扩展过，跳过重复条目
            if (cur.equals(to)) { ... }
        }

对单词接龙这类所有边权都是 1 的问题，h 的区分度不高（很多词的字母差异数相同），A 的实际收益有限。它的价值在中长链上才显现：当 h 能明显区分「看起来更接近」的方向时，A 会显著少于 BFS 的扩展量。

五、实测：双向 BFS 到底能省多少

用 1129 个四字母英文词构成的词典，对若干词对分别跑「单向 BFS」与「双向 BFS」，统计访问节点数（即被 poll 出并处理的节点总数）：

这张表的三个结论：

• 15~20 倍是双向 BFS 的常态收益。5 步问题从 450 个节点降到 22 个，20 倍——这基本对应 b^{d/2} 与 b^d 的理论差距（分支因子约 20，20^{2.5} / 20^5 ≈ 1/20）。
• 步数越长，缩减比反而下降（8 步时是 10.9×）。原因是长链两端扩张到第 4 层后，图中可访问节点已被大量重复访问，visited 集合的「去重」先于「指数增长」生效。
• 无解情形的缩减比最夸张（513×）。单向 BFS 必须把「起点所在的整个连通分量」全部遍历完才能断定不连通（1027 个节点）；双向 BFS 只需两侧各扩 1~2 层，发现两侧连通分量互不相交就立刻停止（2 个节点）。这是双向搜索最被低估的价值：不连通判定从「穷尽一侧」变成「各探一层」。

实测运行环境：JDK 17，单核。1129 词词典的邻接生成（26 × 4 探测 + HashSet 查找）单次约 2~3 微秒，因此 22 个节点的双向 BFS 总耗时不到 0.1 毫秒。

六、复杂度分析

七、工程改进方向

1. 词典压缩为位集：把 HashSet<String> 换成「按长度分组的 BitSet」，用 26 进制编码把词映射到整数下标。查词典从哈希计算降为一次位测试，邻接生成能再快 3~5 倍。
2. 位掩码预筛：对每个词预先算「26 个字母的出现掩码」，两个词若不共享足够多字母，直接判为不可邻接，省掉 104 次字符串比较。
3. 双向 A*：两侧都跑 A*，用 h = max(h_forward, h_backward) 做剪枝，是长链问题的最优解。
4. 词典按「字母模式」索引：把每个词的所有「通配形式」预先注册（c_ld、co_d、col_），邻接查询变成一次哈希查表，O(L) 而非 O(26L)。代价是内存放大 L 倍——这是经典的空间换时间权衡。
5. 并行双向 BFS：两侧各用一个线程，用并发集合共享 visited，在 4 核以上能有近 2 倍加速。但要注意相遇检测的可见性问题，需要内存屏障。

八、小结

单词接龙的价值在于它把三个独立的技巧串成了一条清晰的优化链：

• 图建模：把「改一个字母」看成一条边，文字游戏立刻变成无权图最短路；
• 邻接生成策略：从 O(N²) 的两两比较转为 O(26L) 的按需探测，这是让算法在真实词典规模上可用的一步；
• 双向搜索：用 O(b^{d/2}) 换掉 O(b^d)，实测常态 15~20 倍缩减；而它在不连通判定上的 513 倍收益，是最容易被忽略的部分。

「每次扩展较小的一侧」这一行判断（if (qf.size() <= qb.size())）看似不起眼，却是双向搜索能否达到理论收益的关键——不做这个平衡，两侧波前会互相错过，收益直接腰斩。