题目描述
思路解析
一句话答案：LeetCode 399 除法求值的思路是把等式建成带权有向图：a/b=k 就从 a 到 b 连一条权为 k 的边，同时从 b 到 a 连权为 1/k 的反向边；查询 c/d 时在图上 DFS 找一条从 c 到 d 的路径，沿途边权连乘即答案，找不到路或变量没出现过返回 -1.0。每次查询最坏 O(V+E)，整体 O(Q·(V+E))。
除法求值这道题在问什么
输入一批已知等式，比如 a/b=2、b/c=3，再给一批查询，要求推出每个查询的比值，例如 a/c 是多少。变量的具体数值从头到尾都不知道，能依赖的只有比值之间的关系。推不出来的情况一律返回 -1.0，包括两种：查询里出现了等式中从没出现过的变量（哪怕是 x/x 也不行），或者两个变量之间没有任何比值链条能连通。
为什么除法求值要建成带权图
关键观察是除法关系可以传递：a/b 乘以 b/c，分子分母里的 b 约掉，正好得到 a/c。也就是说，只要存在一串首尾相接的已知比值，把它们连乘就能推出新比值。「首尾相接的一串关系」在数据结构里的标准形态就是图上的一条路径——于是把每个变量看作节点，把 a/b=k 看作从 a 到 b、权值为 k 的有向边，「求 c/d」就变成了「在图上找一条 c 到 d 的路径，把沿途边权乘起来」。
一旦完成这步转化，题目就从陌生的代数推理，落回熟悉的图遍历模板，这正是本题被归为图论题的原因。
为什么每个等式必须建正反两条边
a/b=k 蕴含 b/a=1/k，这条反向信息不建进图里就丢了。只加正向边的话，图上从 b 走不到 a，b/a 这类逆着问的查询会被误判成推不出而返回 -1.0。所以建图时每个等式落两条边：a 到 b 权 k，b 到 a 权 1/k。用哈希表套哈希表做邻接表，节点是变量名字符串，取边和查邻居都是平均 O(1)。
DFS 连乘为什么是对的，seen 集合防什么
搜索函数 dfs(x, y, seen) 回答「从 x 到 y 的比值是多少」。它枚举 x 的每个邻居 nxt：x 到 nxt 的边权是 x/nxt 的值，子问题递归解出 nxt/y，两数相乘时中间项 nxt 约掉，正好是 x/y——每一步的正确性都还原成那条约分恒等式。起点与终点相同时返回 1.0，因为任何数除以自己是 1；任一变量不在图里则直接返回 -1.0，这个存在性检查必须放在最前面。
seen 集合记录本次查询已经走过的节点，防的是死循环：正反两条边天然构成来回的环，不挡住回头路，递归会在 a、b 之间无限弹跳直到爆栈。每次新查询都换一个空的 seen，互不干扰。
复杂度与查询很多时的优化
建图 O(E)；每个查询一次 DFS，最坏把 V 个点、E 条边都摸一遍，Q 个查询整体 O(Q·(V+E))，空间 O(V+E) 花在邻接表、递归栈和 seen 上。
如果查询量远大于图的规模，可以把「现查」换成「预处理」：用 Floyd 一次算出所有点对的比值，预处理 O(V³) 之后每个查询 O(1)；或者用带权并查集，把比值压缩到每个节点相对根的倍率上，同一集合内任意两点的比值近 O(1) 可得。查询少时，朴素 DFS 就是性价比最高的写法。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这句，下面每一帧都在套它。
查询 a / c：从 a 出发，把 a/a=1 当起点（product=1），沿边往 c 找路。
走边 a→b（权 2，即 a/b=2）：product = 1 × 2 = 2。继续从 b 往下找。
走边 b→c（权 3，即 b/c=3）：product = 2 × 3 = 6。到达终点 c！
路径 a→b→c 上的边权连乘 = 6，这就是 a / c = 6。
查询 b / a：从 b 出发，把 b/b=1 当起点（product=1），沿边往 a 找路。
走边 b→a（权 0.5，即 b/a=0.5）：product = 1 × 0.5 = 0.5。到达终点 a！
路径 b→a 上的边权连乘 = 0.5，这就是 b / a = 0.5。
查询 a / d：从 a 出发，把 a/a=1 当起点（product=1），沿边往 d 找路。
走边 a→b（权 2，即 a/b=2）：product = 1 × 2 = 2。继续从 b 往下找。
走边 b→c（权 3，即 b/c=3）：product = 2 × 3 = 6。继续从 c 往下找。
走边 c→d（权 0.5，即 c/d=0.5）：product = 6 × 0.5 = 3。到达终点 d！
路径 a→b→c→d 上的边权连乘 = 3，这就是 a / d = 3。
查询 d / a：从 d 出发，把 d/d=1 当起点（product=1），沿边往 a 找路。
走边 d→c（权 2，即 d/c=2）：product = 1 × 2 = 2。继续从 c 往下找。
走边 c→b（权 0.3333，即 c/b=0.3333）：product = 2 × 0.3333 = 0.6667。继续从 b 往下找。
走边 b→a（权 0.5，即 b/a=0.5）：product = 0.6667 × 0.5 = 0.3333。到达终点 a！
路径 d→c→b→a 上的边权连乘 = 0.3333，这就是 d / a = 0.3333。
查询 c / a：从 c 出发，把 c/c=1 当起点（product=1），沿边往 a 找路。
走边 c→b（权 0.3333，即 c/b=0.3333）：product = 1 × 0.3333 = 0.3333。继续从 b 往下找。
走边 b→a（权 0.5，即 b/a=0.5）：product = 0.3333 × 0.5 = 0.1667。到达终点 a！
路径 c→b→a 上的边权连乘 = 0.1667，这就是 c / a = 0.1667。
查询 x / x：变量 x 根本没在图里出现过（没有任何方程提到它），无从计算 → 答案 -1。
查询 a / f：从 a 出发，把 a/a=1 当起点（product=1），沿边往 f 找路。
走边 a→b（权 2，即 a/b=2）：product = 1 × 2 = 2。继续从 b 往下找。
走边 b→c（权 3，即 b/c=3）：product = 2 × 3 = 6。继续从 c 往下找。
走边 c→d（权 0.5，即 c/d=0.5）：product = 6 × 0.5 = 3。继续从 d 往下找。
查询 a / f：从 a 怎么走都到不了 f（它们不在同一连通块里），无法换算 → 答案 -1。
边界先想清。
两个高频追问。
参考代码
def calcEquation(equations, values, queries): g = {} for (a, b), k in zip(equations, values): g.setdefault(a, {})[b] = k g.setdefault(b, {})[a] = 1.0 / k def dfs(x, y, seen): if x not in g or y not in g: return -1.0 if x == y: return 1.0 seen.add(x) for nxt, w in g[x].items(): if nxt in seen: continue r = dfs(nxt, y, seen) if r != -1.0: return w * r return -1.0 return [dfs(c, d, set()) for c, d in queries]复杂度
- 时间：O(Q·(V+E))，每个查询一次 DFS，最坏遍历整图
- 空间：O(V+E)，邻接表 + 递归栈 + visited
易错点
面试追问把动画讲成自己的话
追问查询非常多时怎么优化？
追问为什么沿路径连乘就是答案？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
删除无效的括号
LeetCode 301 · 困难 · 沿着 图 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题