Foundation / Graph
Knowledge boundary
范围限定为有向、无权、普通图；不进入加权图和高级图算法。
邻接表用切片保存，并不自动决定重复项有没有业务意义。先确定它代表集合、顺序序列，还是允许重边的多重集合。
B, B, X 与 B, X 表达相同的可达关系。
迭代顺序会影响展开轨迹，以及多条等长路径中先选到哪一条。
两条 A → B 是两条独立边，数量可能承载容量或计数。
重复边：A ──▶ B A ──▶ B 合流： B ──▶ D ◀── C
重复边来自同一来源和目标；合流来自不同来源。前者可以按普通图契约归一化，后者是图结构本身。
Stack 是后进先出，倾向沿一条路深入；Queue 是先进先出，倾向先处理离起点近的层。手写容器不是重点，frontier 的推进规则才是。
Queue：入队 A, B, C ──▶ 取出顺序 A, B, C Stack：入栈 A, B, C ──▶ 取出顺序 C, B, A
纸笔推演时固定记录：取出前 frontier、本次取出、新发现节点、取出后 frontier。不要只在脑中移动节点。
visited 不是天然精确的名字。它可以表示“已经进入过 frontier”，也可以表示“已经正式展开过”。两种定义会产生不同的队列形态，前驱记录必须与所选定义保持一致。
第 0 层：起点 第 1 层：经过 1 条边能到达 第 2 层：经过 2 条边能到达 第 3 层：经过 3 条边能到达
无权图里的距离是边数。需要自己说明：为什么 FIFO 会让较浅层先处理，以及第一次有效接纳一个节点时，为什么不会遗漏更短的未处理路径。边有权重后，这个结论不再直接成立。
返回布尔值只需要证明目标是否出现；返回完整路径还要保留证据。原图中的节点可以有多个来路，一次具体搜索只需形成一条可复核的证据链。
每个节点保留一个来路，从目标反向追到起点，再翻转结果。
frontier 项直接带路径，直观，但复制和内存开销更大。
先保留距离，再按距离约束重新寻找，用计算换部分存储。
搜索选出的前驱关系是一棵搜索树，不等于原图天然给每个节点安排了唯一父节点。
| 类别 | 要确认的事实 | 典型结构 |
|---|---|---|
| 起点即目标 | 零条边是否是一条有效路径 | A → A |
| 链与不可达 | 基本推进和 frontier 耗尽 | A → B → C |
| 不同长度分支 | 结果是否按边数最短 | 一条 2 步，一条 3 步 |
| 合流 | 同一节点从不同父节点抵达 | B → D ← C |
| 环与自环 | 旧节点再次出现时是否终止 | A → B → A |
| 重复边 | 输入归一化与搜索状态是否一致 | A: [B, X, B] |
| 多条等长路 | 是否允许返回任意一条最短证据 | A → B/C → D |
| 缺失 key | 当作叶子还是判为非法输入 | 邻居出现，映射中没有定义 |
回到实现前，先写清五句话：输入图的契约、邻接顺序是否有意义、状态表表示哪个阶段、前驱何时成立、重复抵达时已经确定了什么。