使用数组而不是 Kruskals 算法的不相交集来加快合并和查找时间
Using array instead of disjoint-set for Kruskals Algorithm for faster merge and find times
所以刚刚了解了 Kruskals 的最小生成树算法。所以这是我的理解：
初始化一个包含所有顶点V的不相交集数据结构
在 |E|log|E| 中按权重对边进行排序后时间或|E|时间使用计数排序（如果权重允许），Kruskals 算法迭代排序的边，如果节点 u 和 v 不属于不相交集合中的同一集合，则将边 (u,v) 添加到最小生成树structure.Wikipedia 表示此不相交集结构中的查找和搜索时间是 a(V)，其中 a 是阿克曼函数的反函数。
我觉得可以加快查找速度，但不能 100% 确定复杂性。这是我的建议：
对于图中的每个顶点，为其分配一个从 0 到 |V|-1 的值，这些数字现在是它们的索引。初始化一个大小为 |V| 的数组所有值都设置为 0。
当遍历我们的边 (u,v) 时，我们可以在 O(1) 时间内在数组中查找它们的索引，如果这些数组值中的任何一个为 0，则我们将它们都设置为 1 并添加此边缘到我们的最小生成树。
感觉就像这样做，我们可以用 O(V) 时间比 O(a(V)) 更好地查找和合并 Kruskals 算法中的集合，代价是 |V| space 因为我们需要为每个顶点存储一个额外的值。
这看起来是否正确，或者我只是对数组访问时间产生了错觉？
你的算法对于 A--1--B--3--C--2--D 失败（字母是顶点，数字是权重）。
但是请注意，您可以只使用一个数组来实现一个完整的不相交集数据结构，而且实际上经常这样做。我使用这样的表示：
- 每个顶点在数组中都有一个索引（就像你的一样）
- 将所有数组元素初始化为-1。数组值 < 0 表示一个集合的根，其值的否定给出了它的大小或等级。所有顶点都以它们自己的大小为 1 的集合开始。
- 如果数组值 >=0，则表示一个集合链接到该索引处的父集合。合并两个集合时，将较小集合的值设置为较大集合的索引，并在必要时调整较大集合的大小。覆盖较小集合的大小并不重要。它永远不会是根，所以您再也不需要这个尺寸了。
所以刚刚了解了 Kruskals 的最小生成树算法。所以这是我的理解：
初始化一个包含所有顶点V的不相交集数据结构
在 |E|log|E| 中按权重对边进行排序后时间或|E|时间使用计数排序（如果权重允许），Kruskals 算法迭代排序的边，如果节点 u 和 v 不属于不相交集合中的同一集合，则将边 (u,v) 添加到最小生成树structure.Wikipedia 表示此不相交集结构中的查找和搜索时间是 a(V)，其中 a 是阿克曼函数的反函数。
我觉得可以加快查找速度，但不能 100% 确定复杂性。这是我的建议：
对于图中的每个顶点，为其分配一个从 0 到 |V|-1 的值，这些数字现在是它们的索引。初始化一个大小为 |V| 的数组所有值都设置为 0。
当遍历我们的边 (u,v) 时，我们可以在 O(1) 时间内在数组中查找它们的索引，如果这些数组值中的任何一个为 0，则我们将它们都设置为 1 并添加此边缘到我们的最小生成树。
感觉就像这样做，我们可以用 O(V) 时间比 O(a(V)) 更好地查找和合并 Kruskals 算法中的集合，代价是 |V| space 因为我们需要为每个顶点存储一个额外的值。
这看起来是否正确，或者我只是对数组访问时间产生了错觉？
你的算法对于 A--1--B--3--C--2--D 失败（字母是顶点，数字是权重）。
但是请注意，您可以只使用一个数组来实现一个完整的不相交集数据结构，而且实际上经常这样做。我使用这样的表示：
- 每个顶点在数组中都有一个索引（就像你的一样）
- 将所有数组元素初始化为-1。数组值 < 0 表示一个集合的根，其值的否定给出了它的大小或等级。所有顶点都以它们自己的大小为 1 的集合开始。
- 如果数组值 >=0，则表示一个集合链接到该索引处的父集合。合并两个集合时，将较小集合的值设置为较大集合的索引，并在必要时调整较大集合的大小。覆盖较小集合的大小并不重要。它永远不会是根，所以您再也不需要这个尺寸了。