1

我一直在使用 coursera 上的课程研究算法。在第一堂课中，正在讨论快速联合加权。我明白了它的作用，我已经使用他们的代码对其进行了测试，并为它编写了一个小测试。

一切都很清楚，只有一点：当您创建两个对象的并集时，它会将具有最小树的对象添加到较大的对象中。同时，较大树的大小将随着较小树的大小在一个单独的数组中递增，该数组用于确定哪棵树更大。由于数组以每个索引的值 1 启动（每个节点本身基本上是 1 个对象的树），为什么该索引的值不设置为 0 而不是保持为 1？

为了说明这一点：

// Quick Union Weighted
ID: 0 1 2 3 4 5 6 7 8 9 
SZ: 1 1 1 1 1 1 1 1 1 1 

quw.union(2, 4);
ID: 0 1 2 3 2 5 6 7 8 9 
SZ: 1 1 2 1 1 1 1 1 1 1 

quw.union(5, 4);
ID: 0 1 2 3 2 2 6 7 8 9 
SZ: 1 1 3 1 1 1 1 1 1 1 

quw.union(2, 7);
ID: 0 1 2 3 2 2 6 2 8 9 
SZ: 1 1 4 1 1 1 1 1 1 1 

// Whereas I would've expected to end up with this 
// to point out that the index is empty. 
SZ: 1 1 4 1 0 0 1 0 1 1

为什么合并索引的大小是 1 而不是 0？您可以在此处找到对其进行测试的代码。请注意，实现与讲师提供的示例相同，这就是为什么我假设我的代码是正确的。

4

1 回答 1

1

我认为这是因为节点本身的大小也是 1 并且没有任何子节点。但是它可以有孩子。我实际上对快速联合加权并不熟悉，但如果它有点像我见过的其他联合查找算法，你可以例如做

quw.union(0, 1);
ID: 0 0 2 3 2 2 6 2 8 9 
SZ: 1 1 4 1 1 1 1 1 1 1

quw.union(0, 2);
ID: 2 2 2 3 2 2 6 2 8 9 
SZ: 2 1 6 1 1 1 1 1 1 1

所以现在 0 和 1 已经合并，从 0 开始的整个树再次与 2 合并，仍然使从 0 开始的子树大小为 2。

就像我说的，我不确定在 Quick-Union Weighted 中是否可行，但“1”的原因仍然是因为它本身也是 1 号。

于 2013-02-06T11:54:11.480 回答