发布asp.net网站到虚拟主机,广州网站建设的地方推荐,一团网站建设,网站建设与开发专业【0】README
0.1#xff09;本文总结于 数据结构与算法分析#xff0c; 旨在分享 不相交集ADT的相关概念#xff1b; 0.2#xff09; 不相交集ADT 的知识涉及到#xff1a; 等价关系、动态等价关系、不相交集ADT相关操作及其数据结构 #xff0c;还有我们最后分享的 不…【0】README
0.1本文总结于 数据结构与算法分析 旨在分享 不相交集ADT的相关概念 0.2 不相交集ADT 的知识涉及到 等价关系、动态等价关系、不相交集ADT相关操作及其数据结构 还有我们最后分享的 不相交集ADT的应用 0.3 关于不相交集ADT的求并操作find union参见 http://blog.csdn.net/pacosonswjtu/article/details/49717009 0.4 关于不相交集求并后的 路径压缩操作源代码参见 http://blog.csdn.net/PacosonSWJTU/article/details/49717109 0.5 注意本文给出的 联机算法 脱机算法 的定义 【1】 等价关系
1.1若对于每一对元素ab a, b ∈S aRb 或者为true或者为false则称在集合S上定义关系 R 如果aRb 是 true 我们说 a 与 b 是有关系的 1.2等价关系是满足下列三个性质的关系 R
自反性 对于所有的 a ∈S aRa对称性 aRb当且仅当 bRa传递性若aRb且 bRC 则 aRc 【2】 动态等价关系
2.1给定一个等价关系“~” 一个自然问题是对任意的 a和b 确定是否 a~b
看个荔枝 设在5个元素的集合 {a1, a2, a3, a4, a5} 上定义了一个等价关系 此时存在25对元素 它们的每一对有关系或者没有关系
2.2等价类一个元素a∈S 的等价类是S 的一个子集 它包含所有与a 有关系的元素注意等价类形成了对S 的一个划分S的每一个成员恰好出现在了 一个等价类中 2.3为了确定是否 a~b 我们只需要验证 a和b 是否都在同一个等价类中就可以了 2.4不相交初始数据最初是N个集合的类每个集合一个元素初始描述的是所有关系均为 false
2.4.1此时有两种运算可以进行 find操作Find算法它返回包含给定元素的集合等价类的名字添加关系合并操作Union算法如果我们想要添加关系a~b 那么我们首先要看是否a和b已经有关系。这可以通过对a 和 b执行 find 操作来检验它们是否在同一个等价类中来完成如果他们不再同一个类中 那么我们使用 求并运算 Union 吧含有a 和b 的两个等价类合并成一个新的等价类
2.5不相交集合的 Union/Find 算法从集合观点来看 U的结果是建立一个新集合 SkSi U Sj 去掉原来两个集合而保持所有的集合的不相交性由于这个原因 我们把这个工作的算法叫做 不相交集合的 Union/Find 算法 2.6该算法是动态的因为在算法执行过程中 集合可以通过 Union 操作而发生改变 2.7联机算法 脱机算法
2.7.1联机算法这个算法是联机算法当Find执行时 它必须给出答案算法才能继续进行2.7.2脱机算法该算法需要观察全部的Union 和 Find 序列 它对每个Find给出的答案必须和所有执行到该Find的Union一致 而该算法在看到所有的问题以后再给出它的所有答案2.7.3联机和脱机算法的举例说明 这种差别类似于参加一次笔试它一般是脱机的 你只能在规定时间内做完 和一次口试 因为你必须回答当前的问题 然后才能继续下一个问题
2.8解决动态等价问题的方法有两种
2.8.1保证指令 Find 能够以常数最坏情况运行时间执行2.8.2保证指令Union 能够以常数最坏运行时间执行 但以上二者不能同时做到 【3】 基本数据结构
3.1我们的问题不要求 Find 操作返回任何特定的名字而只是要求 当且仅当两个元素属于相同的集合时 作用在这两个元素上的 Find 返回相同的名字 3.2对UnionXY 和 FindX操作的约定
3.2.1我们采纳了在 UnionXY后的新的根是 X 的约定3.2.2对元素X 的一次FindX通过返回包含 X 的树的根而完成执行这次操作花费的时间与表示X 的节点的深度成正比3.2.3通过以上所定义的操作 能够建立一颗深度为 N-1 的树使得一次 Find的最坏情形运行时间为 ONM次连续操作在最坏情形下可能花费 OMN时间
3.3对一些列操作的二次运行时间一般是不可接受的 有幸的是 有几种方法容易保证这样的运行时间不会出现 【4】 一个应用
4.1出现的问题 我们有一个计算机网络和一个双向连接表每一个连接可将文件从一台计算机传送到另一台计算机。那么能否将一个文件从网络上的任意一台计算机发送到任意的另一台计算机上去呢 一个附加的限制是要求该问题必须联机解决因此这个连接表要一次一个地给出而该算法那则必须能够在任一时刻给出答案 4.2解决方法
4.2.1我们要求两台计算机可以传输文件当且仅当他们在同一个集合中可以看出传输文件的能力形成一个等价关系。此时我们一次一个地读入连接。当我们读入某个连接如uv时 我们测试是否 u 和 v 在同一个集合中如果他们在同一个集合中则什么也不做如果不在的话那么将他们所在的两个集合合并4.2.2在算法的最后 所得到的图连通当且仅当恰好存在一个集合。 如果存在M个链接 和 N台 计算机 那么空间的需求则是 ON使用 按大小求并 和 路径压缩 的方法我们得到最坏运行时间为 OMαMN 因为存在2M次Find 和 至多N-1次Union 这个运行时间是线性的
