LeetCode 399中等图 · 带权路径
除法求值 图解题解
这道题到底在问什么
给若干等式 a/b=value，让你回答一串查询 x/y 等于多少；查不到就返回 -1。
- equations
- a/b=2，b/c=3
- 查询
- a/c = ?
- 输出
- 6.0（因为 a/c = a/b × b/c = 2×3）
先想最直接的笨办法
笨办法：把每个查询都去等式列表里硬凑乘除，凑不出就放弃——但 a/c 在等式里根本没直接给，硬凑会漏掉「a→b→c」这种间接链。我们需要一个能自动沿着关系链走下去的结构，那就是图。（动画第 3 步）
最优解：一步一步想明白
- 3笨办法：把每个查询都去等式列表里硬凑乘除，凑不出就放弃——但 a/c 在等式里根本没直接给，硬凑会漏掉「a→b→c」这种间接链。我们需要一个能自动沿着关系链走下去的结构，那就是图。
- 4a/b=2 意味着：从 a 到 b 比值是 2（a→b 权 2），反过来从 b 到 a 就是 1/2（b→a 权 1/2）。只建单向会漏查询——所以每条等式都要正反各建一条边。后面图里把这对正反比值合写成「2 ⇄ 1/2」标在同一条线上。
- 5读 a/b=2，建边：a 到 b 是 2，b 回到 a 是 1/2第一条等式 a/b=2 落地。一条等式同时给了两个方向：a→b 是 2、b→a 是 1/2，互为倒数。边上的「2 ⇄ 1/2」一眼标出这对正反比值。
- 6读 b/c=3，建边：b 到 c 是 3，c 回到 b 是 1/3，图建完第二条等式 b/c=3 落地，标「3 ⇄ 1/3」。现在两条关系都在：a–b 是 2 ⇄ 1/2、b–c 是 3 ⇄ 1/3，每条线都同时带着正反两个互为倒数的比值——注意 a 和 c 之间没有直接边。
- 7查 a/c：从 a 起步，累乘 prod = 1，目标是走到 c查询 a/c 开始：站在起点 a，手里的累乘乘积 prod 初始为 1。a 和 c 不直接相连，得靠 DFS 一步步往 c 探。
- 8沿 a→b（权 2）：prod = 1 × 2 = 2，当前到 b从 a 看邻居，挑 a→b 这个方向、取正向比值 2，踩上去：prod = 1 × 2 = 2。现在站在 b，把 a 标记成已访问，免得待会儿沿 b→a 又绕回去。
- 9沿 b→c（权 3）：prod = 2 × 3 = 6，当前到 c在 b 看邻居：a 已访问跳过，挑 b→c 方向、取正向比值 3，踩上去：prod = 2 × 3 = 6。当前站在 c——正是要找的目标。
- 10当前点 c 等于目标 c → 命中，返回累乘结果 6.0当前点 c 就是目标 c，DFS 命中！把路径上的比值乘起来：2 × 3 = 6.0，这就是 a/c 的答案。整条链 a→b→c 沿途累乘，间接关系被算出来了。
- 11查 a/x：x 没建过，直接返回 -1如果查询里出现没建过的变量（比如 x），或者两点不连通，DFS 走遍邻居也到不了目标。这种查不到的情况，统一返回 -1.0。
- 14一句话本质：把除法等式连成带权图，未知的比值就是图上一条路径的权重乘积。
- 16查 c/a：只建了正边，c 没有出边，误判 -1故意只建正边演示后果：箭头只朝右，没有反向的「⇄ 1/v」。查 c/a 时站在 c，c 一条出边都没有，DFS 立刻返回 -1。但真实答案是 1/6——漏建反边就会错。这就是为什么每条等式必须正反各建一条。
- 22练熟这题，去同类迁移：把比值换成距离/汇率/概率（如最大概率路径 1514）就是同一套带权图 DFS/BFS。点开右侧图论专题，或问小欧「这题还能怎么优化」继续深挖。
⚠️ 容易写错的地方
✗ 错：只建 a→b 权 v
✓ 对：同时建 b→a 权 1/v
查询 b/a、或路径需要反向走时，没有反边就走不通、错判 -1
✗ 错：查询变量没出现过也硬跑 DFS
✓ 对：先判 x、y 是否都在图里，否则直接 -1
x/x 看似该返回 1，但若 x 从没出现在等式里，按题意必须返回 -1
✗ 错：DFS 不记 seen，沿反边绕回去
✓ 对：进入节点先加入 seen，邻居在 seen 里就跳过
正反边构成环（a↔b），不挡就会无限递归爆栈
完整代码（Python / C++ / Java）
Python
class Solution:
def calcEquation(self, equations, values, queries):
g = {} # 邻接表 g[节点]=[(邻居, 比值)]
for (a, b), v in zip(equations, values):
g.setdefault(a, []).append((b, v)) # a→b 权 v
g.setdefault(b, []).append((a, 1 / v)) # b→a 权 1/v
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 nei, w in g[x]: # 看每个邻居
if nei not in seen:
sub = dfs(nei, y, seen)
if sub != -1.0: # 邻居那条路通
return w * sub # 累乘比值
return -1.0 # 所有邻居都不通
return [dfs(a, b, set()) for a, b in queries]C++
class Solution {
public:
unordered_map<string, vector<pair<string,double>>> g;
vector<double> calcEquation(
vector<vector<string>>& equations,
vector<double>& values,
vector<vector<string>>& queries) {
for (int i = 0; i < equations.size(); ++i) {
string a = equations[i][0], b = equations[i][1];
g[a].push_back({b, values[i]}); // a->b 权 v
g[b].push_back({a, 1.0 / values[i]}); // b->a 权 1/v
}
vector<double> res;
for (auto& q : queries) {
unordered_set<string> seen;
res.push_back(dfs(q[0], q[1], seen));
}
return res;
}
double dfs(string x, string y, unordered_set<string>& seen) {
if (!g.count(x) || !g.count(y)) return -1.0; // 变量没出现过
if (x == y) return 1.0; // 走到目标
seen.insert(x);
for (auto& [nei, w] : g[x]) { // 看每个邻居
if (seen.count(nei)) continue;
double sub = dfs(nei, y, seen);
if (sub != -1.0) return w * sub; // 累乘比值
}
return -1.0; // 所有邻居都不通
}
};Java
class Solution {
// 一张表搞定：每个节点存它的边列表 (邻居, 权值)
Map<String, List<Edge>> g = new HashMap<>();
static class Edge { String nei; double w;
Edge(String nei, double w){ this.nei = nei; this.w = w; } }
public double[] calcEquation(List<List<String>> equations,
double[] values, List<List<String>> queries) {
for (int i = 0; i < equations.size(); i++) {
String a = equations.get(i).get(0), b = equations.get(i).get(1);
g.computeIfAbsent(a, k -> new ArrayList<>())
.add(new Edge(b, values[i])); // a->b 权 v
g.computeIfAbsent(b, k -> new ArrayList<>())
.add(new Edge(a, 1.0 / values[i])); // b->a 权 1/v
}
double[] res = new double[queries.size()];
for (int i = 0; i < queries.size(); i++) {
res[i] = dfs(queries.get(i).get(0), queries.get(i).get(1),
new HashSet<>());
}
return res;
}
double dfs(String x, String y, Set<String> seen) {
if (!g.containsKey(x) || !g.containsKey(y)) return -1.0; // 变量没出现过
if (x.equals(y)) return 1.0; // 走到目标
seen.add(x);
for (Edge e : g.get(x)) { // 看每个邻居
String nei = e.nei; double w = e.w;
if (seen.contains(nei)) continue;
double sub = dfs(nei, y, seen);
if (sub != -1.0) return w * sub; // 累乘比值
}
return -1.0; // 所有邻居都不通
}
}套路模板 · 带权图 DFS 累乘（挖空骨架）
# 1) 一条带权关系 → 正反两条边
for (a, b), v in zip(relations, values):
g.setdefault(a, []).append((b, v)) # 正向
g.setdefault(b, []).append((a, 1 / v)) # 反向取倒数
# 2) DFS 沿路累乘，三个出口
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 nei, w in g[x]:
if nei in seen: continue # 防环
sub = dfs(nei, y, seen)
if sub != -1.0: return w * sub # 累乘并上抛
return -1.0 # 出口③走不通// 关键三步，自己补全省略号
for (int i = 0; i < rel.size(); ++i) {
g[rel[i][0]].push_back({rel[i][1], values[i]}); // 正向
g[rel[i][1]].push_back({rel[i][0], 1.0/values[i]}); // 反向
}
double dfs(string x, string y, unordered_set<string>& seen){
if (!g.count(x) || !g.count(y)) return -1.0; // 出口①
if (x == y) return 1.0; // 出口②
seen.insert(x);
for (auto& [nei, w] : g[x]) {
if (seen.count(nei)) continue; // 防环
double sub = dfs(nei, y, seen);
if (sub != -1.0) return w * sub; // 累乘
}
return -1.0; // 出口③
}// 建图：一条关系两条边
addEdge(a, b, v); // 正向 权 v
addEdge(b, a, 1.0 / v); // 反向 权 1/v
double dfs(String x, String y, Set<String> seen){
if (!g.containsKey(x) || !g.containsKey(y)) return -1.0; // 出口①
if (x.equals(y)) return 1.0; // 出口②
seen.add(x);
for (邻居 nei, 权 w : g.get(x)) { // 自己补遍历
if (seen.contains(nei)) continue; // 防环
double sub = dfs(nei, y, seen);
if (sub != -1.0) return w * sub; // 累乘
}
return -1.0; // 出口③
}复杂度
建图
O(E)
E 条等式，每条建正反两条边，一次遍历搞定
时间复杂度
O(Q · (V+E))
Q 个查询，每个查询最坏要 DFS 遍历整张图：V 个点、E 条边各访问一次
空间复杂度
O(V + E)
邻接表存 V 个点、2E 条边；外加 DFS 递归栈和 seen 集合最深 O(V)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 除法求值 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
除了 DFS，还能怎么做？+
并查集（带权）：每个变量记录它到根的比值，合并时按比例更新，查询时两点同根就用各自到根的比值相除。预处理后单次查询接近 O(1)，查询特别多时更划算。
查询非常多时怎么优化？+
DFS 每次都从头遍历是 O(Q·(V+E))。可以用 Floyd 预处理所有点对比值 O(V³) 一次建好，之后每个查询 O(1) 直接查表；或用带权并查集。
为什么不用担心浮点精度爆掉？+
题目数据规模小（变量、等式都不多），路径短，连乘几次不会显著累积误差。比较时用 -1.0 判断是否查到，而不是和某个比值做相等判断，所以稳妥。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。