题目

难度：★★★★☆
类型：图
方法：深度优先搜索

力扣链接请移步本题传送门
更多力扣中等题的解决方案请移步力扣中等题目录

给出方程式 A / B = k, 其中 A 和 B 均为用字符串表示的变量， k 是一个浮点型数字。根据已知方程式求解问题，并返回计算结果。如果结果不存在，则返回 -1.0。

示例 :

给定 a / b = 2.0, b / c = 3.0
问题: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ?
返回 [6.0, 0.5, -1.0, 1.0, -1.0 ]

输入为: vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries(方程式，方程式结果，问题方程式)， 其中 equations.size() == values.size()，即方程式的长度与方程式结果长度相等（程式与结果一一对应），并且结果值均为正数。以上为方程式的描述。 返回vector<double>类型。

基于上述例子，输入如下：

equations(方程式) = [ ["a", "b"], ["b", "c"] ],
values(方程式结果) = [2.0, 3.0],
queries(问题方程式) = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ].
输入总是有效的。你可以假设除法运算中不会出现除数为0的情况，且不存在任何矛盾的结果。

解答

从题目中的要求，是需要求变量与变量之间的关系，而给出的已知信息是变量与大量中间变量之间的关系，因此本题适合用图这种数据结构来做。

图的构建。为了便于表示，这里使用字典来构建图。构建图需要两个主要的信息，即节点与节点之间的关系，函数的输入“equations”就是节点，“values”就是节点之间的关系。为了便于搜索，我们把图构建成双向的，也就是节点与节点之前可以双向到达，对于每一个样本组，即（节点1，节点2，连接权重），可以使用嵌套字典{节点1：{节点2：连接权重}}和{节点2：{节点1：连接权重的倒数}}进行表达。

图的深度优先搜索。本题的要求实际上是求取从源节点到目标节点的路径，并沿着该方向将路径上的所有权重相乘，如果找不到该路径，返回-1。深度优先搜索很适合这类工作，但要注意通过剪枝来控制搜索范围，并且构建足迹集合来避免重复搜索。实现上，首先判断特殊情况，如果源节点或目标节点不在图中，直接返回-1，如果源节点就是目标节点，返回1，其他情况，遍历源节点的相邻节点，如果相邻节点中出现目标节点，说明找到路径，返回连接权重，否则，遍历没有出现在足迹集合的所有相邻节点，通过递归调用探索有没有相邻节点与目标节点之间存在连接。这里注意足迹集合的及时更新，以及最终情况的处理。

class Graph:
    def __init__(self, node_pairs, relations):
        """
        图的初始化，用于构建图中节点与节点中的连接
        :param node_pairs: 图的节点对
        :param relations: 图的节点对之前的关系（权重）
        """
        self.value = dict()
        self.visited = set()    # 用于遍历过程
        for (node1, node2), relationship in zip(node_pairs, relations):
            self.add_node_pair(node1, node2, relationship)

    def refresh(self):
        """
        每次搜寻，需要更新一下
        :return:
        """
        self.visited = set()

    def add_node_pair(self, node1, node2, weight):
        """
        将两个相邻的节点注册在图中，注意节点与节点之间是双向的。
        :param node1: 第一个节点
        :param node2: 第二个节点
        :param weight: 两个节点的关系
        :return:
        """
        def register_nodes(n1, n2, w):
            if n1 in self.value:
                self.value[n1][n2] = w
            else:
                self.value[n1] = {n2: w}

        register_nodes(node1, node2, weight)        # 从节点1到节点2的关系
        register_nodes(node2, node1, 1 / weight)    # 从节点2到节点1的关系

    def search_path(self, source, target):
        """
        寻找从源节点到目标节点的路径
        :param source: 源节点
        :param target: 目标节点
        :return: 如果找到，返回该路径上所有权重的乘积，如果找不到一条路径，返回-1
        """
        if source not in self.value or target not in self.value:        # 如果源节点或者目标节点不在图中，直接返回-1
            return -1
        if source == target:                                            # 如果源节点就是目标节点，返回1
            return 1
        for node in self.value[source].keys():                          # 搜索与当前节点相邻的所有节点
            source2node = self.value[source][node]                      # 获取相邻关系
            if node == target:                                          # 如果相邻节点就是目标节点，说明找到
                return source2node                                      # 返回与源节点的关系
            if node not in self.visited:                                # 如果相邻节点还没有在程序运行过程中遍历过
                self.visited.add(node)                                  # 添加该节点到历史记录
                result = self.search_path(source=node, target=target)   # 通过深度优先搜索，寻找这个相邻节点与目标节点之前的关系
                if result != -1:                                        # 如果成功找到
                    return source2node * result                         # 建立连接
        return -1                                                       # 如果没有找到它们之前的关系，返回-1


class Solution:
    def calcEquation(self, equations, values, queries):
        graph = Graph(node_pairs=equations, relations=values)
        res = []
        for s, t in queries:
            graph.refresh()
            res.append(graph.search_path(s, t))
        return res


if __name__ == "__main__":
    s = Solution()
    print(s.calcEquation([ ["a", "b"], ["b", "c"] ], [2.0, 3.0], [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ]))

如有疑问或建议，欢迎评论区留言~

有关更多力扣中等题的python解决方案，请移步力扣中等题解析