图论综合
本节目标
将关系图、隐式状态图、反向消除、结构中心与受限路径模型组合为可迁移的图论框架。
前五栏分别建立了图的表示、拓扑依赖、连通性、最短路和生成树。本栏面对的是“图仍然存在，但题面没有直接给出一张普通图”的情况：变量关系需要带权边，棋盘移动隐含状态图，安全状态从终点反向传播，树和账户把结构转成图，航班和高度路径再给边数或路径代价增加限制。
识别信号
- 变量比值、换算关系或可达关系需要沿边累乘或传递；
- 规则规定从一个状态能走到哪些状态，图由规则隐式生成；
- 目标是识别“最终一定到达终点”的点，可从终点反向消除；
- 无根树的中心、账户的共享字段需要先补成合适的图结构；
- 路径限制的是经过边数，或代价是路径上的最大边，而不是普通距离；
- 要恰好使用全部有向边并取得字典序最小的路径。
问题模型与核心不变量
关系图的边不仅表示能否到达，还带有权重：a / b = 2 同时给出 a -> b 权重 2 与反向权重 1/2，一条搜索路径的乘积就是查询结果。蛇梯棋把格子编号当作顶点，每次掷骰产生至多六条边；落点传送只发生一次，BFS 首次到达一个格子时的层数仍是最少步数。
最终安全状态的方向恰好相反：终点的出度为零，删除它们后，前驱若再无可去之处也安全。最小高度树不断删除叶子，账户合并通过共享邮箱连接账户，二者都在改变表示后利用结构不变量。有限中转航班要分层更新，最小体力路径最小化的是路径最大边，重新安排行程则要把每条边恰用一次。
通用模板
先确认图是怎样出现的：
关系是否需要带权双向边？
状态是否由规则按需生成？
能否从终点或叶子反向删除？
实体间是否要借共享字段或无向边补结构？
限制的是边数、瓶颈代价，还是每条边必须恰用一次？
确定模型后再选搜索。隐式无权状态图按层 BFS；带权关系图在访问集合中 DFS 并累乘；反向消除维护剩余出度；受限路径必须让状态携带轮数或当前瓶颈。不能只看题面里是否出现“图”字，而应先写清顶点、边和状态何时被确认。
模板变体
- 带权关系图：补双向倒数边，DFS 参数携带当前乘积。
- 隐式棋盘图：编号映射到坐标，骰子点数按需生成邻居，传送只改一次落点。
- 反向拓扑：建反图并维护原图出度，从出度为零的点开始删除。
- 结构中心：反复剥离叶子，最后一层就是无根树中心。
- 共享字段合并：账户与邮箱建立关联，再按连通块收集并排序邮箱。
- 受限与完整用边：按允许边数分层松弛；瓶颈路径用
max松弛；欧拉路径按后序收集边。
母题序列
按拓展顺序练习：
- 除法求值（拓展）：把比值关系变成带权双向边，沿搜索路径累乘。
- 蛇梯棋（拓展）：把棋盘规则转换成隐式无权图，再按层搜索。
- 找到最终的安全状态（拓展）：从终点反向减少前驱的剩余出度。
- 最小高度树（拓展）：反复删除叶子，保留树的结构中心。
- 账户合并（拓展）：以共享邮箱为边，合并同一连通块的账户。
- K 站中转内最便宜的航班（拓展）：用轮数隔离松弛，限制可用边数。
- 最小体力消耗路径（拓展）：将路径代价定义为最大边权，并最小化它。
- 重新安排行程（拓展）：在有向多重图中恰用每张机票一次。
常见误区
- 比值图只加正向边，或搜索时遗漏访问集合而在环中反复走。
- 蛇梯棋把传送目标继续连锁传送，偏离一次落点规则。
- 安全状态从环中正向猜测，忽略环外不能到达环的安全前驱。
- 叶子剥离只做一轮，或把最后一层中心提前删除。
- 受限航班在同一轮原地更新，偷偷使用了超过限制的边数。
- 把瓶颈路径当作普通边权和，或让欧拉路径遗漏重复边。
迁移方向
遇到新题时，先把自然语言规则翻译为顶点、边和状态，再决定信息该沿正向搜索、反向传播还是按层受限。带权状态、概率、多个资源限制或更复杂的连通结构会引入新的状态维度；此时应重新证明不变量，而不是把本栏模板机械拼接。