我们能否使用单个数组在对数时间内执行图形查找(A 和 B 是否连接？)和连接(连接 A 和 B)？
我学习了一些算法，例如:
快速查找(连接中的线性时间和查找中的常数时间)- 单个数组
快速联合(恒定时间连接和查找中的平均 n/2)- 单个数组
加权联合(记录查找时间和恒定连接时间)但此算法需要 2 个数组，一个用于节点，另一个用于每个节点连接的节点数。
我只是出于好奇才问的。是否有可能使用单个数组获得加权并集的复杂性？
最佳答案
您可以使用 Disjoint-Set .它作为森林工作，但您始终可以使用一个数组来实现这个森林，使用一个 roots 数组，而不是每个节点的 root 字段。
此实现的智能化复杂度是次对数，通常标记为O(log*(n))
关于algorithm - 我们可以使用单个数组进行图形查找和连接操作来获得对数时间复杂度吗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/9521526/