时间戳

首页 > 解决方案 > 有人能解释一下 root 函数在这个快速联合实现中是如何工作的吗？

python - 有人能解释一下 root 函数在这个快速联合实现中是如何工作的吗？

问题描述

我正在尝试实现快速联合算法，其中节点的 id 是它们的根节点。

id 是这样实现的：

self.id = []
for i in range(N)
    self.id.append(i)

其中存储节点 0 到 N - 1 的索引

这是我无法理解的代码：

def root(self, i):
    while(i != self.id[i]):
    i = self.id[i]
    return i

怎么了？“我”是什么？它如何指向根节点？

我理解联合方法：

def union(self, p, q):
    i = self.root(p)
    j = self.root(q)
    self.id[i] = j

这意味着类似：将值是 p 的根的 id 更改为 q 的根，对吗？

标签： pythonalgorithm

解决方案

id[i]指向第 i 个元素的父元素。如果此元素不是根（根id指向自身），则代码移动到父元素，然后移动到父元素的父元素，依此类推，直到到达根。

示例：我们想找到第 0 个元素的根

i   0   1   2   3
    \/ ----->
id  2   1   1   3

id[0]不等于0，所以这个元素是叶子，我们向它的父元素2迈出一步

i   0   1   2   3
        <---\/
id  2   1   1   3

id[2]不等于2，所以这个元素是叶子，我们向它的父元素1迈出一步

i   0   1   2   3
       \/   
id  2   1   1   3

id[1]等于 1，所以我们找到了第 0 个元素的根

存储在该数组中的树：

 1          3
 /  
2
\
 0

推荐阅读