深度优先搜索（DFS）解题思路解析：如何通过图论计算除法求值
深度优先搜索（DFS）解题思路解析：如何通过图论计算除法求值
我们需要处理一组等式和一组查询。等式给出了变量之间的比例关系，而查询则要求我们根据这些等式找出新的比例。如果查询中的变量不存在于等式中，或者无法通过已知的等式得到结果，则返回 -1.0。
399. 除法求值 - 力扣（LeetCode）
这是一个典型的图论问题，我们可以将变量看作是图中的节点，而等式则可以视为连接两个节点的边。边的权重表示变量之间的比值关系。通过构建这样的图，我们可以利用深度优先搜索（DFS）或广度优先搜索（BFS）来查找查询中变量之间的路径，并计算结果。
解题思路：
-
图的表示：
-
我们将每个变量视为图中的一个节点，而等式则成为连接节点的边，边的权重为变量之间的比值。例如，
A / B = value可以表示为一条从A到B的边，权重为value，同时还可以表示一条从B到A的边，权重为1 / value。 -
这种图的表示方法使我们能够使用 DFS 或 BFS 在图中查找查询中变量的路径，并计算比例。
-
-
图的构建：
-
我们使用一个哈希表（字典）来存储图。对于每个变量
A，我们会记录与A相连的所有变量以及相应的比值关系。这个结构可以看作是邻接表（Adjacency List）的形式。 -
对于给定的等式
A / B = value，我们会将A连接到B，权重为value，同时将B连接到A，权重为1 / value。
-
-
处理查询：
- 对于每个查询（例如，查询
C / D的结果），我们可以在图中搜索从C到D的路径，并在路径上累计比值。可以通过 DFS 或 BFS 来进行路径搜索，如果找到了从C到D的路径，则计算并返回比值；如果没有路径，则返回 -1.0。
- 对于每个查询（例如，查询
-
边界情况：
- 如果查询中的变量在图中不存在，或者没有办法通过图中的边找到从
C到D的路径，则直接返回-1.0。
- 如果查询中的变量在图中不存在，或者没有办法通过图中的边找到从
具体步骤解析：
1. 图的构建：
遍历 equations 和 values，将变量及其对应的比值关系添加到图中。我们会对每一对等式建立双向边关系：对于 A / B = value，不仅会在图中添加 A -> B，还会添加 B -> A，并且前者的权重为 value，后者的权重为 1 / value。
2. 使用深度优先搜索（DFS）实现查询：
在进行查询时，对于每一个查询 C / D，我们使用 DFS 进行搜索：
- 如果
C == D，返回 1.0，因为任意变量除以自身的比值为 1。 - 如果在图中找不到
C或D，直接返回 -1.0。 - 如果能够找到从
C到D的路径，则沿着路径计算比值并返回结果。 - 如果无法找到从
C到D的路径，则返回 -1.0。
DFS 是一种经典的图搜索算法，适合用于查找从一个节点到另一个节点的路径问题。我们在 DFS 的过程中需要确保不重复访问节点，以避免陷入死循环，因此我们使用一个集合 visited 来记录已访问的节点。
DFS 详细解释
深度优先搜索（DFS） 是一种用于遍历或搜索树或图的算法。它从一个起始节点开始，尽可能深入地探索每一个分支，直到到达叶子节点或没有未访问的邻居为止。然后，它回溯到最近的分支点，继续探索其他分支。
在这个问题中，我们使用 DFS 来查找从变量 ( C ) 到 ( D ) 的路径，并在路径上计算比例。
DFS 函数分析
以下是 DFS 函数的关键部分：
double dfs(const string& src, const string& dst, unordered_set<string>& visited) {
if (src == dst) return 1.0; // 找到目标
visited.insert(src); // 标记为已访问
for (const auto& neighbor : graph[src]) {
if (visited.find(neighbor.first) == visited.end()) { // 未访问的邻居
double result = dfs(neighbor.first, dst, visited); // 递归调用
if (result != -1.0) {
return result * neighbor.second; // 计算并返回比例
}
}
}
return -1.0; // 未找到路径
}
代码逻辑逐步解析
-
起始条件：
- 如果当前节点（
src）是目标节点（dst），则返回比例 1.0，因为任何变量与自身的比值都是 1。
- 如果当前节点（
-
标记访问：
- 将当前节点添加到
visited集合中，防止重复访问，避免死循环。
- 将当前节点添加到
-
遍历邻居：
- 对于每个邻居（即与当前变量相连的变量），检查它是否已被访问。
- 如果未访问，进行递归调用 DFS 以探索邻居。
-
计算比例：
- 如果递归调用返回的结果不为 -1.0（表示找到了路径），则计算当前比例（
result * neighbor.second），并返回。
- 如果递归调用返回的结果不为 -1.0（表示找到了路径），则计算当前比例（
-
未找到路径：
- 如果遍历完所有邻居仍未找到目标，返回 -1.0。
实例解析
让我们通过一个具体示例来演示 DFS 的工作过程：
示例输入
equations = [["a","b"],["b","c"]];
values = [2.0, 3.0];
queries = [["a","c"],["b","a"],["a","e"]];
- 图构建：
a --(2.0)--> b b --(0.5)--> a b --(3.0)--> c c --(1/3.0)--> b
查询分析：a / c
-
调用 DFS:
dfs("a", "c", visited); -
第一层：
src是"a"，dst是"c"。src != dst，继续查找。- 访问
"a"，邻居是b，开始递归：
dfs("b", "c", visited); -
第二层：
src是"b"，dst是"c"。- 访问
b，邻居是a和c。 - 先检查
a（已访问，跳过）。 - 然后访问
c，发现src == dst，返回 1.0。
-
返回计算：
- 返回
1.0给上层，乘以从b到c的比例3.0：
return 1.0 * 3.0; // 结果是 3.0 - 返回
-
回到第一层：
- 计算
a / c的比例：
return 2.0 * 3.0 = 6.0; - 计算
查询分析：b / a
-
调用 DFS:
dfs("b", "a", visited); -
第一层：
src是"b"，dst是"a"。src != dst，访问b，邻居是a和c。- 访问
a，发现src == dst，返回 1.0。
-
返回计算：
- 计算
b / a的比例：
return 1.0 * 0.5; // 结果是 0.5 - 计算
查询分析：a / e
-
调用 DFS:
dfs("a", "e", visited); -
判断是否存在：
e不在图中，直接返回 -1.0。
代码实现：
以下是基于上述思路的 C
++ 代码实现：
#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <string>
using namespace std;
class Solution {
public:
unordered_map<string, unordered_map<string, double>> graph;
// 构建图函数
void addEquation(const string& A, const string& B, double value) {
graph[A][B] = value;
graph[B][A] = 1.0 / value;
}
// 深度优先搜索函数
double dfs(const string& src, const string& dst, unordered_set<string>& visited) {
if (src == dst) return 1.0; // 找到目标，返回1.0
visited.insert(src); // 标记当前节点为已访问
for (const auto& neighbor : graph[src]) {
if (visited.find(neighbor.first) == visited.end()) {
double result = dfs(neighbor.first, dst, visited);
if (result != -1.0) {
return result * neighbor.second; // 乘上比值，返回最终结果
}
}
}
return -1.0; // 如果未找到路径，返回-1.0
}
vector<double> calcEquation(vector<vector<string>>& equations, vector<double>& values, vector<vector<string>>& queries) {
// 构建图
for (int i = 0; i < equations.size(); ++i) {
addEquation(equations[i][0], equations[i][1], values[i]);
}
vector<double> results;
for (const auto& query : queries) {
const string& C = query[0];
const string& D = query[1];
if (graph.find(C) == graph.end() || graph.find(D) == graph.end()) {
results.push_back(-1.0); // 如果找不到节点，返回-1.0
} else {
unordered_set<string> visited;
results.push_back(dfs(C, D, visited));
}
}
return results;
}
};
int main() {
Solution sol;
vector<vector<string>> equations1 = {{"a","b"},{"b","c"}};
vector<double> values1 = {2.0, 3.0};
vector<vector<string>> queries1 = {{"a","c"},{"b","a"},{"a","e"},{"a","a"},{"x","x"}};
vector<double> result1 = sol.calcEquation(equations1, values1, queries1);
for (double res : result1) {
cout << res << " ";
}
cout << endl; // 输出: [6.00000, 0.50000, -1.00000, 1.00000, -1.00000]
vector<vector<string>> equations2 = {{"a","b"},{"b","c"},{"bc","cd"}};
vector<double> values2 = {1.5, 2.5, 5.0};
vector<vector<string>> queries2 = {{"a","c"},{"c","b"},{"bc","cd"},{"cd","bc"}};
vector<double> result2 = sol.calcEquation(equations2, values2, queries2);
for (double res : result2) {
cout << res << " ";
}
cout << endl; // 输出: [3.75000, 0.40000, 5.00000, 0.20000]
return 0;
}
总结：
通过构建图并利用 DFS 或 BFS 来解决除法求值问题，能够高效处理多个查询。在解决此类问题时，图论的表示和搜索算法是非常直观且有效的选择。