网站如何集成微信支付,中国建设银行人才招聘网站,wordpress切换城市插件,网站关键词分析工具一些应用涉及 将n个不同的元素分成一组不相交的集合。寻找包含给定元素的唯一集合 和 合并两个集合
1、不相交集合的操作
1、一个不相交集合 数据结构 维持了 一个不相交动态集的集合 S {S_1, S_2,…, S_n}。用一个代表 来标识每个集合#xff0c;它是这个集合的某个成员。…一些应用涉及 将n个不同的元素分成一组不相交的集合。寻找包含给定元素的唯一集合 和 合并两个集合
1、不相交集合的操作
1、一个不相交集合 数据结构 维持了 一个不相交动态集的集合 S {S_1, S_2,…, S_n}。用一个代表 来标识每个集合它是这个集合的某个成员。在一些应用中不关心 哪个成员被用来作为代表仅仅关心的是 重复两次查询动态集合的代表中如果 这两次查询 没有修改动态集合则两次查询 应该得到相同的结果。其他一些应用 可能会需要一个预先说好的规则 来选择代表比如 选择这个集合中最小的成员
2、用一个对象 表示一个集合的每个元素。设 x 表示一个对象希望支持以下三个操作
MAKE-SET(x): 建立 一个新的集合它的唯一成员 (因而为代表) 是 x。因为各个集合是不相交的故 x 不会出现在 别的某个集合中UNION(x, y): 将包含 x 和 y 的两个动态集合 (分别表示为S_x和S_y) 合成一个新的集合即这两个集合的并集。虽然 UNION 的很多实现中 特别地选择 S_x 或 S_y 的代表作为新的代表然而结果集的代表 可以是S_x∪S_y 的任何成员。由于 要求各个集合不相交故要 “消除” 原有的集合 S_x 和 S_y即 将它们从 S 中删除。实际上经常把 其中一个集合的元素 并入另一个集合中来代替删除操作FIND-SET(x): 返回一个指针这个指针 指向包含 x 的(唯一)集合的代表
使用两个参数 来分析 不相交集合数据结构的运行时间: 一个参数是 n表示 MAKES-SET 操作的次数另一个是m表示 MAKE-SET、UNION 和 FIND-SET 操作的总次数
每个 UNION 操作减少一个集合因此n - 1 次 UNION 操作后只有一个集合留了下来。也就是说UNION 操作的次数 至多是 n - 1。由于 MAKE-SET 操作 被包含在总操作次数 m 中因此有 m ≥ n。假定 n 个 MAKE-SET 操作总是最先执行
1.1 不相交集合数据结构的一个应用
确定无向图的连通分量
下面的 CONNECTED-COMPONENTS 过程使用 不相交集合操作 计算一个图的连通分量。一旦 SAME-COMPONENTS 预处理了该图过程 SAME-COMPONENT 就回答两个顶点是否在 同一个连通分量的询问图G的顶点集用 G.V 表示边集用 G.E 表示
图21-1(b)展示了 CONNECTED-COMPONENTS 如何计算不相交集合
CONNECTED-COMPONENTS(G)
1 for each vertex v ∈ G.V
2 MAKE-SET(v)
3 for each edge (u, v) ∈ G.E
4 if FIND-SET(u) ≠ FIND-SET(v)
5 UNION(u, v)SAME-COMPONENT(u,v)
1 if FIND-SET(u) FIND-SET(v)
2 return TRUE
3 else return FALSE处理完所有的边之后两个顶点在相同的连通分量 当且仅当 与之对应的对象在相同的集合中 一个表示顶点的对象会包含一个指向与之对应的不相交集合对象的指针 2、不相交集合的链表表示
实现 不相交集合数据结构 的简单方法每个集合 用一个自己的链表来表示。每个集合的对象 包含 head 属性和 tail 属性head 属性 指向链表的第一个对象tail 属性 指向链表的最后一个对象。链表中的每个对象 都包含一个集合成员一个指向链表中 下一个对象的指针 和 一个指回到集合对象的指针。在每个链表中对象可以 以任意的次序出现。代表是 链表中第一个对象的集合成员
MAKE-SET 操作 和 FIND-SET 操作 是非常方便的只需 O(1) 的时间
要执行 MAKE-SET(x) 操作需要创建一个 只有 x 对象的新链表。对于 FIND-SET(x)仅沿着指针 x 对象的返回指针 返回到集合对象然后返回 head 指向对象的成员
2.1 合并的一个简单实现
UNION 操作 通过把 y 所在的链表 拼接到 x 所在的链表 实现了 UNION (x, y)。x 所在的链表的代表 成为结果集的代表。利用 x 所在链表的 tail 指针可以迅速地找到 拼接 y 所在的链表的位置
对于 y 所在链表的每个对象必须更新 指向集合对象的指针这将花费的时间 与 y 所在链表长度 呈线性关系
构建一个在 n 个对象上需要 Θ(n2) 时间的 m 个操作序列。假设 有对象 x1, x2, …, xm执行 n 个 MAKE-SET 操作后面跟着 n-1 个 UNION 操作。因而有 m 2n - 1。执行 n 个 MAKE-SET 操作 需要 Θ(n) 时间。由于第 i 个 UNION 操作更新 i 个对象参数中 右侧 插在 左侧的集合后面
因此所有的 n-1 个 UNION 操作更新的对象的总数为 总的操作数为 2n-1这样每个操作 平均需要 Θ(n) 的时间。也就是说一个操作的摊还时间为 Θ(n)
2.2 一种加权合并的启发式策略
1、在最坏情况下上面给出的 UNION 过程的每次调用 平均需要 Θ(n) 的时间这是因为 需要把一个较长的表 接到 一个较短的表上此时 必须对较长表的每个成员 更新其指向集合对象的指针
加权合并启发式策略假使 表中包含了 表的长度易于维护以及 拼接次序 可以任意的话总是 把较短的链表 拼接到较长的表中
2、使用不相交集合的链表表示 加权合并启发式策略一个具有 m 个 MAKE-SET, UNION 和 FIND-SET 操作的序列其中有 n 个是 MAKE-SET 操作需要的时间为 O(m nlg n)
证明由于每个UNION操作 合并两个不相交集因此总共至多执行 n-1 个UNION操作。现在来确定 由这些 UNION 操作所花费时间的上界。首先 确定每个对象指向它的集合对象的指针 被更新次数的上界。每次 x 的指针被更新x 一定先在一个规模较小的集合中。因此第一次 x 的指针被更新时结果集 一定至少有 2 个成员类似地下次 x 的指针 被更新时 结果集至少有4个成员。一直继续下去注意到 对于任意的 k ≤ n在 x 的指针被更新 ⌈lg k⌉ 次后结果集 一定至少有 k 个成员。因为 最大集合 至多包含 n 个成员所以 每个对象的指针在所有的 UNION 操作中最多被更新 ⌈lg n⌉ 次。当然也必须考虑 tail 指针 和 表长度的更新而它们在每个 UNION 操作中只花费 Θ(1) 时间。所以 总共花在 UNION 操作上的时间为 O(nlg n)
每个 MAKE-SET 和 FIND-SET 操作需要 O(1) 时间它们的总数为 O(m)。所以整个序列的总时间是 O(mnlg n)
3、使用链表表示 和 加权合并启发式策略写出 MAKE-SET、FIND-SET 和 UNION 操作的伪代码并指定 在集合对象和表对象中所使用的属性
MAKE-SET(x)
// Assume x is a pointer to a node contains .key .set .nextCreate a node S contains .head .tail .sizex.set Sx.next NILS.head xS.tail xS.size 1return SFIND-SET(x)return x.set.headUNION(x, y)S1 x.setS2 y.setif S1.size S2.sizeS1.tail.next S2.headz S2.headwhile z ! NIL // 把S2中所有元素都改成S1的z.set S1z z.nextS1.tail S2.tailS1.size S1.size S2.size // Update the size of setreturn S1elsesame procedure as abovechange x to ychange S1 to S23、不相交集合森林
在一个 不相交集合 更快的实现中使用有根树 来表示集合树中的每个节点 包含一个成员每棵树 代表一个集合。在一个 不相交集合森林中如图所示每个成员仅指向它的父结点每棵树的根节点 包含集合的代表。每个树中的每个成员都是它所在集合的成员同时其根节点表示该集合的代表并且是指向代表的根节点。我们可以在树根节点中做任何操作来执行FIND-SET虽然树根节点可能处于集合森林的不同位置但是结果总是同样的成员代表。随着进一步的优化和策略“按秩合并”union by rank我们能得到一个渐近更优的不相交集合数据结构
MAKE-SET 操作 简单地创建一棵 只有一个结点的树FIND-SET 操作 通过沿着指向父结点的指针 找到树的根。这一通向 根结点的简单路径上所访问的结点 构成了 查找路径。UNION 操作 使得一棵树的根 指向另外一棵树的根
3.1 改进运行时间的启发式策略
第一种启发式策略是 按秩合并它类似于 链表表示中 使用的 加权合并启发式策略。使具有较少节点的树的根 指向具有较多的树的根。不显式地记录 每个结点为根的子树的大小而是采用 一种易于分析的方法。对于每个结点维护一个秩该秩表示 该结点高度的一上界。使用按秩合并策略的 UNION 操作中可以让 具有较小秩的根指向具有较大秩的根
第二种启发式策略是 路径压缩在 FIND-SET 操作中使用这种策略 可以使查找路径中的每个结点 直接指向根。路径压缩 并不改变任何结点的秩
注意三角形是一棵树而不是 结点
3.2 实现不相交集合森林的伪代码
为了使用 按秩合并的启发式策略 实现一个不相交集合森林必须记录下 秩 的变化情况。对于每个结点 x维护一个整数值 x.rank它代表 x 的高度 (从 x 到某一后代叶结点的 最长简单路径上 边的数量) 的一个上界。当 MAKE-SET 创建 一个单元素集合时这个树上的单结点 有一个为0的初始秩。每一个 FIND-SET 操作 不改变任何秩
UNION 操作有 两种情况取决于 两棵树的根是否有相同的秩。如果 根没有相同的秩就 让较大秩的根 成为较小秩的根的父结点因为 FIND-SET 复杂度是高度但秩本身保持不变。另一种情况是 两个根有相同的秩时任意选择两个根中的一个 作为父结点并使它的秩加1
用 x.p 代表结点 x 的父结点
MAKESET(x)
1 x.p x
2 x.rank 0UNION(x, y)
1 LINK(FIND-SET(x), FIND-SET(y))LINK(x, y)
1 if x.rank y.rank
2 y.p x
3 else x.p y
4 if x.rank y.rank
5 y.rank y.rank 1带有路径压缩的 FIND-SET 过程
FIND-SET(x)
1 if x ! x.p
2 x.p FIND-SET(x.p) // 使 x 到根路径上的所有结点的父结点 为根结点
3 return x.pFIND-SET 过程是一种两趟方法当它递归时第一趟 沿着查找路径向上 直到找到根当递归回溯时第二趟沿着搜索树向下 更新到 结点 x 路径中的每个结点使其直接指向根。FIND-SET(x) 的每次调用 在第3行返回 x.p
如果 x 是根那么 FIND-SET 跳过第2行并返回 x.p也就是x这是递归到原点的情形。否则第2行执行并且参数为 x.p 的递归调用 返回一个指向根的指针。第2行 更新结点 x 并让其直接指向根结点然后第3行 返回这个指针
3.3 启发式策略对运行时间的影响
单独使用按秩合并 或 路径压缩每个都能改善 不相交集合森林上 操作的运行时间而两者结合在一起 效果更好。单独来看路径压缩产生的运行时间上限为 O(m lg n)并且这是个界是紧确的
对于一个具有 n 个 MAKE-SET 操作因此最多有 n-1 个UNION操作和 f 个 FIND-SET 操作的操作序列单独使用 路径压缩启发式策略的 最坏情况下的 运行时间为 Θ(n f*(1 log(2f/n)n))
当同时使用 按秩合并与路径压缩时最坏情况下的运行时间为 O(mα(n))这里 α(n) 是一个增长非常慢的函数在任何一个 可以想到的 不相交集合数据结构的应用中α(n) 都 ≤ 4
21.3-1 用按秩合并 与 路径压缩启发式策略 的不相交集合森林 完成
1 for i 1 to 16
2 MAKE-SET(x_i)
3 for i 1 to 15 by 2
4 UNION(x_i, x_{i1})
5 for i 1 to 13 by 4
6 UNION(x_i, x_{i2})
7 UNION(x_1, x_5)
8 UNION(x_9, x_13)
9 UNION(x_1, x_9)假定如果集合x_i 和x_j 的集合有相同的大小则 UNION(x_i, x_j) 表示将x_j 所在的表链接到x_i 所在的表后 21.3-2 将递归版本的 FIND-SET带路径压缩改为非递归版本。
为了实现非递归的 FIND-SET假设我们在元素 x 上调用该函数。创建一个链表 A其中包含指向 x 的指针。每次我们 向树的上层移动一个元素时将指向该元素的指针 插入链表 A 中。一旦找到根节点 r使用该链表找到从根节点到 x 的路径上的每个节点并将这些节点的父节点更新为 r
21.3-3 给出一个包含n个 MAKE-SET、UNION 和 FIND-SET 操作的序列其中有 n 个是 MAKE-SET 操作)当仅使用按秩合并时需要 Ω(m lg n) 的时间
