图论-并查集算法解决有传递性关系的问题-白红宇

图论-并查集算法解决有传递性关系的问题

阅读量：2095 次

发布时间：2019-04-29

本文共 4749 字，大约阅读时间需要 15 分钟。

本篇由力扣第399题引出，部分描述来自官方题解。

399. 除法求值

给你一个变量对数组 equations 和一个实数值数组 values 作为已知条件，其中 equations[i] = [Ai, Bi] 和 values[i] 共同表示等式 Ai / Bi = values[i] 。每个 Ai 或 Bi 是一个表示单个变量的字符串。

另有一些以数组 queries 表示的问题，其中 queries[j] = [Cj, Dj] 表示第 j 个问题，请你根据已知条件找出 Cj / Dj = ? 的结果作为答案。

返回所有问题的答案。如果存在某个无法确定的答案，则用 -1.0 替代这个答案。如果问题中出现了给定的已知条件中没有出现的字符串，也需要用 -1.0 替代这个答案。

注意： 输入总是有效的。你可以假设除法运算中不会出现除数为 0 的情况，且不存在任何矛盾的结果。

示例：

输入：equations = [["a","b"],["b","c"]], values = [2.0,3.0],      queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]输出：[6.00000,0.50000,-1.00000,1.00000,-1.00000]解释：条件：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 ]

分析

由于变量之间的倍数关系具有传递性，处理有传递性关系的问题，可以使用「并查集」，我们需要在并查集的「合并」与「查询」操作中维护这些变量之间的倍数关系。

说明： 请大家注意看一下题目中的「注意」和「数据范围」，例如：每个 Ai 或 Bi 是一个表示单个变量的字符串。所以用例 equation = [“ab”, “cd”] ，这里的 ab 视为一个变量，不表示 a * b。如果面试中遇到这样的问题，一定要和面试官确认清楚题目的条件。还有 1 <= equations.length <= 20 和 values[i] > 0.0 可以避免一些特殊情况的讨论。

分析示例 1：

$a / b = 2.0$ 说明 $a = 2 b a = 2 b$ ， a 和 b 在同一个集合中；

$b / c = 3.0$ 说明 $b = 3 c b = 3 c$ ，b 和 c 在同一个集合中。

求 $\cfrac{a}{c}$ ，可以把 $a = 2 b$ ， $b = 3 c$ 依次代入，得到 $\cfrac{a}{c} = \cfrac{2b} {c} = \cfrac{2 \cdot 3c} {c} = 6.0$ ；

求

\cfrac{b}{a}

，很显然根据

a = 2 b

，知道

\cfrac{b}{a} = 0.5

，也可以把 b 和 a 都转换成为 c 的倍数，

\cfrac{b}{a} = \cfrac{b} {2b} = \cfrac{3c} {6c} = \cfrac{1}{2} = 0.5

；

我们计算了两个结果，不难知道：可以将题目给出的 equation 中的两个变量所在的集合进行「合并」，同在一个集合中的两个变量就可以通过某种方式计算出它们的比值。具体来说，可以把不同的变量的比值转换成为相同的变量的比值，这样在做除法的时候就可以消去相同的变量，然后再计算转换成相同变量以后的系数的比值，就是题目要求的结果。统一了比较的标准，可以以 O(1) 的时间复杂度完成计算。

如果两个变量不在同一个集合中，返回 -1.0。并且根据题目的意思，如果两个变量中至少有一个变量没有出现在所有 equations 出现的字符集合中，也返回−1.0。

构建有向图

通过例 1 的分析，我们就知道了，题目给出的 equations 和 values 可以表示成一个图，equations 中出现的变量就是图的顶点，「分子」于「分母」的比值可以表示成一个有向关系（因为「分子」和「分母」是有序的，不可以对换），并且这个图是一个带权图，values 就是对应的有向边的权值。例 1 中给出的 equations 和 values 表示的「图形表示」、「数学表示」和「代码表示」如下表所示。其中 $p a r e n t [a] = b$ 表示：结点 a 的（直接）父亲结点是 b，与之对应的有向边的权重，记为 $w e i g h t [a] = 2.0$ ，即 weight[a] 表示结点 a 到它的直接父亲结点的有向边的权重。

「统一变量」与「路径压缩」的关系

刚刚在分析例 1 的过程中，提到了：可以把一个一个 query 中的不同变量转换成同一个变量，这样在计算 query 的时候就可以以 O(1) 的时间复杂度计算出结果，在「并查集」的一个优化技巧中，「路径压缩」就恰好符合了这样的应用场景。

为了避免并查集所表示的树形结构高度过高，影响查询性能。「路径压缩」就是针对树的高度的优化。「路径压缩」的效果是：在查询一个结点 a 的根结点同时，把结点 a 到根结点的沿途所有结点的父亲结点都指向根结点。如下图所示，除了根结点以外，所有的结点的父亲结点都指向了根结点。特别地，也可以认为根结点的父亲结点就是根结点自己。如下图所示：路径压缩前后，并查集所表示的两棵树形结构等价，路径压缩以后的树的高度为 2，查询性能最好。

由于有「路径压缩」的优化，两个同在一个连通分量中的不同的变量，它们分别到根结点（父亲结点）的权值的比值，就是题目的要求的结果。

如何在「查询」操作的「路径压缩」优化中维护权值变化

如下图所示，我们在结点 a 执行一次「查询」操作。路径压缩会先一层一层向上先找到根结点 d，然后依次把 c、b 、a 的父亲结点指向根结点 d。

c 的父亲结点已经是根结点了，它的权值不用更改；

b 的父亲结点要修改成根结点，它的权值就是从当前结点到根结点经过的所有有向边的权值的乘积，因此是 3.0 乘以4.0 也就是 12.0；

a 的父亲结点要修改成根结点，它的权值就是依然是从当前结点到根结点经过的所有有向边的权值的乘积，但是我们没有必要把这三条有向边的权值乘起来，这是因为 b 到 c，c 到 d 这两条有向边的权值的乘积，我们在把 b 指向 d 的时候已经计算出来了。因此，a 到根结点的权值就等于 b 到根结点 d 的新的权值乘以 a 到 b 的原来的有向边的权值。

如何在「合并」操作中维护权值的变化

「合并」操作基于这样一个很重要的前提：我们将要合并的两棵树的高度最多为 22，换句话说两棵树都必需是「路径压缩」以后的效果，两棵树的叶子结点到根结点最多只需要经过一条有向边。

例如已知 $\cfrac{a}{b} = 3.0$ ， $\cfrac{d}{c} = 4.0$ ，又已知 $\cfrac{a}{d} = 6.0$ ，现在合并结点 a 和 d 所在的集合，其实就是把 a 的根结点 b 指向 d 的根结 c，那么如何计算 b 指向 c 的这条有向边的权重呢？

根据 a 经过 b 可以到达 c，a 经过 d 也可以到达 c，因此两条路径上的有向边的权值的乘积是一定相等的。设 b 到 c 的权值为 x，那么 $3.0 \cdot x = 6.0 \cdot 4.0$ ，得 $x = 8.0$ 。

一个容易忽略的细节

接下来还有一个小的细节问题：在合并以后，产生了一棵高度为 3 的树，那么我们在执行查询的时候，例如下图展示的绿色结点和黄色结点，绿色结点并不直接指向根结点，在计算这两个变量的比值的时候，计算边的权值的比值得到的结果是不对的。

但其实不用担心这个问题，并查集的「查询」操作会执行「路径压缩」，所以真正在计算两个变量的权值的时候，绿色结点已经指向了根结点，和黄色结点的根结点相同。因此可以用它们指向根结点的有向边的权值的比值作为两个变量的比值。

通过这个细节可以看出：一边查询一边修改结点指向是并查集的特色。

参考代码：

代码可能有点长，但真正理解后其实并不难。

class Solution {
       public double[] calcEquation(List
   
    
     > equations, double[] values, List
     
      
       > queries) {
           int size=equations.size();               int id=0;        UnionFind uf=new UnionFind(2*size);         HashMap
       
        map=new HashMap<>();        //初始化uf和map，将字符映射为int类型的值，便于后续的查询和对比        for(int i=0;i

说明： 代码 $w e i g h t [r o o t X] = w e i g h t [y] * v a l u e / w e i g h t [x];$ 的推导过程，主要需要明白各个变量的含义，由两条路径有向边的权值乘积相等得到相等关系，然后做等价变换即可。

从上述代码可以看出，并查类中主要实现三个方法，即union、find和isConnected，其中union负责设置图中各结点的初始状态，find负责查询各个结点的根结点，同时在查询过程中对该图进行压缩，最终将查询结点的父结点指向能够到达的根结点为止；isConnected负责在最终解答时查询两个结点是否可达，或者说是否指向同一个根结点。

于是整个流程就很清晰了，我们用一个 parents[] 数组记录图中每个结点的父结点，用一个 weights[] 数组记录图中每条边的权重，然后遍历已知条件，对每个条件执行union操作，最后遍历问题集合，对每个问题执行isConnected操作即可。

使用以上方法解答力扣第399题结果如下：