深度优先搜索（DFS）解题思路解析：如何通过图论计算除法求值

深度优先搜索（DFS）解题思路解析：如何通过图论计算除法求值

我们需要处理一组等式和一组查询。等式给出了变量之间的比例关系，而查询则要求我们根据这些等式找出新的比例。如果查询中的变量不存在于等式中，或者无法通过已知的等式得到结果，则返回 -1.0。

399. 除法求值 - 力扣（LeetCode）

这是一个典型的图论问题，我们可以将变量看作是图中的节点，而等式则可以视为连接两个节点的边。边的权重表示变量之间的比值关系。通过构建这样的图，我们可以利用深度优先搜索（DFS）或广度优先搜索（BFS）来查找查询中变量之间的路径，并计算结果。

解题思路：

1. 图的表示：

   • 我们将每个变量视为图中的一个节点，而等式则成为连接节点的边，边的权重为变量之间的比值。例如，A / B = value 可以表示为一条从 A 到 B 的边，权重为 value，同时还可以表示一条从 B 到 A 的边，权重为 1 / value。

   • 这种图的表示方法使我们能够使用 DFS 或 BFS 在图中查找查询中变量的路径，并计算比例。

2. 图的构建：

   • 我们使用一个哈希表（字典）来存储图。对于每个变量 A，我们会记录与 A 相连的所有变量以及相应的比值关系。这个结构可以看作是邻接表（Adjacency List）的形式。

   • 对于给定的等式 A / B = value，我们会将 A 连接到 B，权重为 value，同时将 B 连接到 A，权重为 1 / value。

3. 处理查询：

   • 对于每个查询（例如，查询 C / D 的结果），我们可以在图中搜索从 C 到 D 的路径，并在路径上累计比值。可以通过 DFS 或 BFS 来进行路径搜索，如果找到了从 C 到 D 的路径，则计算并返回比值；如果没有路径，则返回 -1.0。

4. 边界情况：

   • 如果查询中的变量在图中不存在，或者没有办法通过图中的边找到从 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; // 未找到路径
}

代码逻辑逐步解析

1. 起始条件：

   • 如果当前节点（src）是目标节点（dst），则返回比例 1.0，因为任何变量与自身的比值都是 1。

2. 标记访问：

   • 将当前节点添加到 visited 集合中，防止重复访问，避免死循环。

3. 遍历邻居：

   • 对于每个邻居（即与当前变量相连的变量），检查它是否已被访问。
   • 如果未访问，进行递归调用 DFS 以探索邻居。

4. 计算比例：

   • 如果递归调用返回的结果不为 -1.0（表示找到了路径），则计算当前比例（result * neighbor.second），并返回。

5. 未找到路径：

   • 如果遍历完所有邻居仍未找到目标，返回 -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

1. 调用 DFS:

   dfs("a", "c", visited);
   

2. 第一层：

   • src 是 "a"，dst 是 "c"。
   • src != dst，继续查找。
   • 访问 "a"，邻居是 b，开始递归：

   dfs("b", "c", visited);
   

3. 第二层：

   • src 是 "b"，dst 是 "c"。
   • 访问 b，邻居是 a 和 c。
   • 先检查 a（已访问，跳过）。
   • 然后访问 c，发现 src == dst，返回 1.0。

4. 返回计算：

   • 返回 1.0 给上层，乘以从 b 到 c 的比例 3.0：

   return 1.0 * 3.0; // 结果是 3.0
   

5. 回到第一层：

   • 计算 a / c 的比例：

   return 2.0 * 3.0 = 6.0;
   

查询分析：b / a

1. 调用 DFS:

   dfs("b", "a", visited);
   

2. 第一层：

   • src 是 "b"，dst 是 "a"。
   • src != dst，访问 b，邻居是 a 和 c。
   • 访问 a，发现 src == dst，返回 1.0。

3. 返回计算：

   • 计算 b / a 的比例：

   return 1.0 * 0.5; // 结果是 0.5
   

查询分析：a / e

1. 调用 DFS:

   dfs("a", "e", visited);
   

2. 判断是否存在：

   • 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 来解决除法求值问题，能够高效处理多个查询。在解决此类问题时，图论的表示和搜索算法是非常直观且有效的选择。