问题标签 [disjoint-sets]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
c++ - 带链表的不相交集,C++ - Cormen
这是我根据 Cormen 实现的不相交集(算法简介 - 第 2 版第 21 章)。
删除对象(“~DisjointSet”析构函数)时出现问题。
这是因为“std::vector sets;”的寄存器。可能指向相同的“MetaSet*”。
boost - boost - 从不相交的集合中获取组件多图
我是 boost 库的新手。我在图上创建了一个不相交的集合结构,上面有一些分区,获得集合组件的多重图的最佳方法是什么?
algorithm - 在简化图中逐步查找不相交集的数量
我在图中找到不相交集的数量,G
然后删除图的一些顶点G
并制作图G'
,我想在其中找到不相交集的数量G'
,是否有任何好的算法不做与G'
我们一样的事情到G
?
algorithm - 确定两组数字是否不相交的有效算法
练习软件开发人员面试并被困在算法问题上。
algorithm - 有没有一个例子可以在Omega(q log n)中运行Union&find算法而无需按等级运行?
最近,我读到这篇文章,惊讶地发现,仅使用路径压缩的 union & find 算法的时间复杂度是O((m+n) log n)
,其中m
'find' 查询n
的数量是 'merge' 查询的数量。
我对这种复杂性很感兴趣,(因为我通常在没有秩的情况下实现这个算法,即使我按秩倒置应用联合,性能也不错!)并试图找到一个可以使时间复杂度提高的例子。但是因为路径压缩的威力很大,所以真的很难……
有没有可以实现的例子Omega((m+n) log n)
,或者这种复杂性只是理论上的,而不是实际的?
c++ - 如何从“不相交集”中获取所有元素的列表
在我的问题中,我有一堆元素(类元素)。假设我有 1000 个元素。这些元素最初是不相关的,这意味着它们在自己的集合中。
稍后我需要根据我的程序流程使用联合操作来合并其中的一些集合。我计划使用 boost 库的 disjoint_set ( http://www.boost.org/doc/libs/1_57_0/libs/disjoint_sets/disjoint_sets.html )
我的问题是如何在给定集合代表的情况下列出集合中的元素。
disjoint_set 是此类任务的最佳数据结构吗?那么我应该考虑使用其他东西吗?
c++ - 提升不相交集
我需要制作一个不相交的类型集dataum
。
我在向量中的所有数据如下
然后我创建 disjoint_set
这似乎不起作用。我错过了什么?我想用自定义数据类型创建一个不相交的集合。在这种情况下dataum
。最初,我的每个人dataums
都应该在不同的集合中。
python - 关于在python中实现不相交集数据结构的一些问题
所以我只是使用了这里提供的代码:http: //www.ics.uci.edu/~eppstein/PADS/UnionFind.py,但我遇到了一些关于代码的问题:
首先,方法iter是什么意思或做什么?
其次,假设我最初有以下代码:
那么,我怎样才能执行打印、添加等集合的常规操作呢?如果我写 print R,它只会给出 < main .UnionFind instance at 0x000000000A31F048>,这显然不是我想要的。如果我写 R.add('K') (将新元素 'K' 添加到集合 R),我会得到 'AttributeError: UnionFind instance has no attribute 'add''。这是否意味着我需要为“添加”定义一个属性?这个怎么做?
如果经过几次联合操作后,我将“A”、“B”、“C”分组到同一个集合中,那么如果我想知道“A”所在的集合内的所有元素(即“A”, 'B','C'),我该怎么办?
谢谢
python - 在 Python 中实现不相交集数据结构
我正在做一个涉及集群的小项目,我认为这里给出的代码https://www.ics.uci.edu/~eppstein/PADS/UnionFind.py可能是我工作的一个很好的起点。但是,在我的工作中实施它时遇到了一些困难:
如果我制作一个包含所有集群 cluster=set([0,1,2,3,4,...,99]) 的集合(有 100 个点,数字标记它们),那么我想分组将数字放入簇中,我是否只需编写 cluster=UnionFind()?现在集群的数据类型是什么?
如何在集群上执行常规操作?例如,我想读取集群中的所有点(可能已组合在一起),但键入 print cluster 会导致 < main .UnionFind instance at 0x00000000082F6408>。我还想不断向集群添加新元素,我该怎么做?UnionFind()的具体方法需要写吗?
我如何知道一个组的所有成员及其成员之一被调用?比如 0,1,3,4 组合在一起,那么如果我调用 3,我希望它打印 0,1,3,4,我该怎么做呢?
谢谢
complexity-theory - 证明任何求解不相交集的算法至少需要 nlog n
不相交集问题
让 A 和 B 成为两个集合,它们是不相交的吗?
问题
证明任何求解不相交集的算法至少需要O(nlog n)。
我想到的想法是证明排序可以简化为不相交集问题。
我怎么做 ?