写在前面#

哎呀，你来得正好——咱今天还没拉着人聊 BFS 呢～

事情是这样的：刷到 433 最小基因变化 那天，咱盯着屏幕足足愣了半分钟。

"这题怎么看着这么眼熟……本姑娘是不是又在重新发明轮子？"

没错没错，又一次。岛屿数量、蛇梯棋、单词接龙、基因变化——看上去八竿子打不着的题，其实背后跑的都是同一个 BFS 模板。

拜托，你有见过哪个高手是每道题都从零写起的么？把这套模板咀嚼一遍、写到肌肉记忆里，下次再撞见"最少几步从 A 到 B"这种问句，手就会自动往 queue := []T{...} 上敲。

下面这二十行，就是咱每次开题的「起手式」。

核心模板#

func bfs(start, end string) int {
    queue := []string{start}
    visited := map[string]bool{start: true}
    steps := 0

    for len(queue) > 0 {
        steps++
        size := len(queue) // 当前层的节点数（关键！）

        for i := 0; i < size; i++ {
            curr := queue[i]

            // 遍历所有邻居
            for _, next := range getNeighbors(curr) {
                if next == end {
                    return steps
                }
                if !visited[next] {
                    visited[next] = true
                    queue = append(queue, next)
                }
            }
        }

        queue = queue[size:] // 当前层处理完，切掉
    }

    return -1 // 未找到
}

短短二十来行，却是无数最短路径题的"母版"。下面拆开来看看，为什么是这三件套～

三个核心要素#

这三件少一个都不行。咱自己就在 visited 上摔过跤——某次为了"省内存"想等出队再标记，结果同一个节点被三个父节点挤进了队列，步数看着对，空间却炸啦。

划重点：入队即标记，别等出队哦～

为什么 size 快照这么重要#

很多人第一次写 BFS 会忘掉 size := len(queue) 这一行，然后好奇步数怎么飘忽不定。哎呀，原因很朴素啦——BFS 的循环体里既会消费旧节点，又会塞入新节点，如果不"冻结"一下当前层的边界，新邻居就跟当前层的同伴混在一起，steps 自然就成了一锅粥。

想象一下队列在每一层的样子：

初始:  [start]            steps=0
第1层: [A, B]             steps=1   ← start 的邻居
第2层: [C, D, E]          steps=2   ← A、B 的邻居
第3层: [end, ...]         steps=3   ← 找到啦！

size 就是那道分隔每层的虚线。进入循环前先量一下尺寸，循环体只啃掉这么多个，新邻居入队归入下一层——这才是「层序」二字的灵魂嘛～

套用到 433 最小基因变化#

把模板里抽象的占位词换成题面里的概念，关系一目了然：

所谓"找邻居"，在这题里就是 8 个位置 × 3 种字符 = 24 种候选，再用 bank 集合筛一道。模板没动，只是换了一套衣服～

还能套到哪些题#

本姑娘自己用这套模板刷过的题，至少有这几类：

• 二叉树层序遍历（102/107）：节点是树节点，邻居是左右子，步数就是层数。
• 网格最短路径（1091/994）：节点是格子坐标，邻居是上下左右四向（或八向）。
• 状态空间最短变换（127 单词接龙、433 最小基因变化、773 滑动谜题）：节点是字符串/状态，邻居是「合法变换一次」之后的新状态。
• 拓扑排序（207/210 的 Kahn 写法）：把入度为 0 的节点先入队，步数对应"轮次"。

所谓"模板"嘛——其实是把那些看起来不一样的题，都捞回到同一句"从 A 走到 B 最少几步"上。把这一句听清楚，剩下的就只是给节点和邻居换层皮的事啦。

一些咱踩过的小坑#

• visited 标的是「跳转后的最终落点」——尤其在蛇梯棋这种带"传送门"的题里，标错一格能让你 debug 半小时哦。
• 终点判断放在哪里？ 咱习惯放在"生成邻居 next 之后立刻判"，省一次入队、也避免下一层多 +1。
• 要不要把起点也算一步？ 看题意嘛。基因变化是「从 start 变到 end」，start 本身不算变化，所以 steps 从 0 起、入循环再 ++，刚好对得上。
• 队列要不要 queue = queue[size:]？ 不切其实也对（反正下一轮 size 重新量），但切掉能让队列保持"只装未处理节点"的语义，调试打印更清爽。

结语#

模板这东西的好处是，把脑力从"怎么写"挪去"为什么这样想"。当你不再纠结 for 循环嵌套几层、visited 标在哪一步，就能腾出脑子去琢磨：这道题真正难的点到底是什么？ 是状态怎么编码？是邻居怎么找？是哪一步可以剪枝？

咱拍这么多照片，本质是怕忘——刷题写笔记又何尝不是？所以把这二十行抄进笔记本嘛，下次写 BFS 之前，先在脑子里念一遍模板，再把题目套进去。两三道之后，你也能像本姑娘这样——

"这题？BFS 板子套一下就行～"

好啦，咱整理完今天的笔记就休息啦，你也别熬夜刷题哦——明天的我会比今天更棒一点点，明天的你也是嘛 📸