java – 支持删除的不相交集数据结构
发布时间：2020-12-15 00:56:21 所属栏目：Java 来源：网络整理
导读：假设我们有一组n个不相交的节点{node1,node1,…,noden} 以下3个操作的最快数据结构和算法是什么： Union(x,y)：在nodex和nodey之间添加一个非定向边,两个节点之间最多只能有一条边. IsConnected(x,y)：如果nodex和nodey直接或间接连接,则返回true,即nodex和n
|
假设我们有一组n个不相交的节点{node1,node1,…,noden}
以下3个操作的最快数据结构和算法是什么： > Union(x,y)：在nodex和nodey之间添加一个非定向边,两个节点之间最多只能有一条边. Disjoint-set是前两个操作的完美数据结构,但它不能直接支持第3个操作.有什么选择？ 如果我们模拟过程,第一个和第三个操作可以在O(1)中实现,但第二个操作是O(n),所以我想看看是否可以在O(logn)时间运行所有三个操作或更少. 解决方法
Link/cut tree可以在O(log N)时间内执行这3个操作.
您可以在本书中阅读有关链接/剪切树和相关数据结构的信息：“Handbook of Data Structures and Applications”(第35章). 链接/剪切树不允许在已经(间接)连接的节点之间添加边缘.如果您需要“Union(x,y)”操作来支持此操作,则问题会变得更加复杂,您可以将其解决为无向图中的动态连接问题. (见同一本书或第this pdf章第36.4章).在这种情况下,插入/删除复杂性增加到O(log2 N). （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |