Objective-C版UnionFind

这是一个实现并查集/不交集数据结构的微型库，具有以下功能：

• 节点：唯一的类型是UFDisjointSetNode。一个UFDisjointSetNode是某个隐式节点集合的成员。在任何给定时间，集合由其成员中的一些单个特定节点表示。集合永远不会部分重叠；要么是相同的集合，要么没有节点重叠。
• 并集：使用unionWith:将两个UFDisjointSetNode成员所在的集合合并为一个集合。
• 查找：使用isInSameSetAs:确定两个UFDisjointSetNode是否在同一集合中。使用currentRepresentative获取当前代表该接收节点所在集合的节点。节点属于同一集合当且仅当它们具有相同的代表。

安装

方法 #1: CocoaPods

1. 在您的Podfile中添加 pod 'UnionFind'
2. 请考虑版本号，例如：pod 'UnionFind', '~> 1.0'
3. 在您的项目目录中的终端运行pod install
4. #import "UnionFind.h" 以便在任何地方访问库的类型或方法

方法 #2: 手动

1. 下载版本之一，或克隆仓库
2. 将源文件从 src/ 文件夹复制到您的项目中
3. 启用ARC
4. #import "UnionFind.h" 以便在任何地方访问库的类型或方法

算法

该算法来源于维基百科中的不交集数据结构文章。操作时间几乎为常数时间的摊销时间。

用法

在您希望进行并查集操作的类中，添加一个类型为UFDisjointSetNode的字段。初始化节点，要么在类构造时懒惰地初始化，然后在需要时使用它，然后对该节点执行操作。

例如，假设我们有一个FancyGraphNode，可以向其中添加边但不能删除。我们希望跟踪节点是否在同一连通分量中。我们可以

1. 将字段@private UFDisjointSetNode* _ccNode添加到FancyGraphNode
2. 在init函数中初始化该字段：_ccNode = [UFDisjointSetNode new]。
3. 当添加边时，调用[edge.Node1._ccNode unionWith:edge.Node2._ccNode]。
4. 为了确定两个节点是否在同一组件中，请评估[node1._ccNode isInSameSetAs:node2._ccNode]。

在这篇关于增量循环检测的博客文章中讨论了应用示例。