给一个集合T,如何来写出的它的等价关系?比如{1,3,4}，怎么来下手_百度作业帮
拍照搜题，秒出答案
给一个集合T,如何来写出的它的等价关系?比如{1,3,4}，怎么来下手
给一个集合T,如何来写出的它的等价关系?比如{1,3,4}，怎么来下手
集合上的等价关系有很多啊,我认为比较简单的写出一个集合上的等价关系是这样的：例如集合A={1,2,3,4},则关系R={}就是集合A上的一个等价关系.
1.2属于T且3.4属于T等价类和并查集 - yx的专栏
- 博客频道 - CSDN.NET
1399人阅读
7.2 等价类和并查集
7.2.1 等价关系与等价类
１、在求解实际应用问题时常会遇到等价类的问题。
２、 从数学上看，等价类是一个对象(或成员)的集合，在此集合中的所有对象应满足等价关系。
３、 若用符号&&&表示集合上的等价关系，那么对于该集合中的任意对象x, y, z，下列性质成立：
（１）自反性：x & x (即等于自身)。
（２）对称性：若 x & y, 则 y & x。
（３）传递性：若 x & y且 y & z, 则 x & z。
４、 因此，等价关系是集合上的一个自反、对称、传递的关系。
５、&相等&(=)就是一种等价关系，它满足上述的三个特性。
６、一个集合 S 中的所有对象可以通过等价关系划分为若干个互不相交的子集 S1, S2, S3, &，它们的并就是 S。这些子集即为等价类。
确定等价类的方法 ：（分两步走）
第一步，读入并存储所有的等价对( i, j )；
第二步，标记和输出所有的等价类。
void equivalence ( ) {
　while 等价对未处理完
　{ 读入下一个等价对 ( i, j );
　　存储这个等价对 ; }
　输出初始化;
　for ( 尚未输出的每个对象 )
　　输出包含这个对象的等价类 ;
给定集合 S = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 },
及如下等价对: 0 & 4, 3 & 1, 6 & 10, 8 & 9, 7 & 4, 6 & 8, 3 & 5, 2 & 11, 11 & 0
初始 {0}, {1}, {2}, {3}, {4}, {5}, {6}, {7}, {8}, {9}, {10}, {11}
0 & 4 {0, 4}, {1}, {2}, {3}, {5}, {6}, {7}, {8}, {9}, {10}, {11}
3 & 1 {0, 4}, {1, 3}, {2}, {5}, {6}, {7}, {8}, {9}, {10}, {11}
6 & 10{0, 4}, {1, 3}, {2}, {5}, {6, 10}, {7}, {8}, {9}, {11}
8 & 9 {0, 4}, {1, 3}, {2}, {5}, {6, 10}, {7}, {8, 9}, {11}
7 & 4 {0, 4, 7}, {1, 3}, {2}, {5}, {6, 10}, {8, 9}, {11}
6 & 8 {0, 4, 7}, {1, 3}, {2}, {5}, {6, 8, 9, 10}, {11}
3 & 5 {0, 4, 7}, {1, 3, 5}, {2}, {6, 8, 9, 10}, {11}
2 & 11{0, 4, 7}, {1, 3, 5}, {2, 11}, {6, 8, 9, 10}
11 & 0{0, 2, 4, 7, 11}, {1, 3, 5}, {6, 8, 9, 10}
7.2.2 确定等价类的链表方法
１、设等价对个数为m，对象个数为n。一种可选的存储表示为单链表。
２、 可为集合的每一个对象建立一个带表头结点的单链表，并建立一个一维的指针数组 seq[n] 作为各单链表的表头结点向量。 seq[i]是第 i 个单链表的表头结点，第 i 个单链表中所有结点的data域存放的是在等价对中与 i 等价的对象编号。
３、当输入了一个等价对( i, j )后，就将集合元素 i 链入第 j 个单链表，且将集合元素 j 链入第 i 个单链表。在输出时，设置一个布尔型数组 out[n]，用 out[i] 标记第 i 个单链表是否已经输出。
void equivalence ( ) {
　将 seq 初始化为 0 且将 out 初始化为 F
　while等价对未处理完 {
　　读入下一个等价对( i, j );
　　将 j 链入 seq[i]链表;
　　将 i 链入 seq[j]链表;
　for ( i = 0; i & i++ ) //检测所有对象
　　if ( out[i] == False ) { //若对象i未输出
　　　out[i] = T
//对象i做输出标志输出包含对象 i 的等价类;
１、算法的输出从编号 i = 0 的对象开始，对所有的对象进行检测。
２、在 i = 0 时，循第0个单链表先找出形式为( 0, j )的等价对，把 0 和 j 作为同一个等价类输出。再根据等价关系的传递性，找所有形式为( j, k )的等价对，把 k 也纳入包含 0 的等价类中输出。如此继续，直到包含 0 的等价类完全输出为止。
３、接下来再找一个未被标记的编号，如 i = 1，该对象将属于一个新的等价类，我们再用上述方法划分、标记和输出这个等价类。
４、在算法中使用了一个栈。每次输出一个对象编号时，都要把这个编号进栈，记下以后还要检测输出的等价对象的单链表。
输入所有等价对后的seq数组及各单链表的内容：
等价类链表的定义
enum Boolean { False, True };class ListNode { //定义链表结点类friend void equivalence ( );private:　int //结点数据 　ListNode * //结点链指针 　ListNode ( int d ) {　data = link = NULL; } }; typedef ListNode *ListNodeP //建立等价类算法 (输入等价对并输出等价类) 每当一个对象的单链表//检测完，就需要从栈中退出一个指针，以便继续输出等价类中的其它对//象。如果栈空，说明该等价类所有对象编号都已输出，再找一个使得//out[i] == False的最小的i，标记并输出下一个等价类。void equivalence ( ) { 　ifstream inFile ( &equiv.in&, ios::in ); //输入文件 　if ( !inFile ) { 　　cout && &不能打开输入文件& && 　　exit (1); 　} 　int i, j,　inFile && //读入对象个数　seq = new ListNodePtr[n];　out = new Boolean[n]; //初始化seq和out 　for (i = 0; i & i++) { 　　seq[i] = 0; 　　out[i] = F　} 　inFile && i && //输入等价对 ( i, j )　while ( inFile.good ( ) ) { //输入文件结束转出循环 　　x = new ListNode ( j ); //创建结点 j 　　x&link = seq[i]; 　　seq[i] = //链入第i个链表 　　y = new ListNode ( i ); //创建结点i　　y&link = seq[j]; 　　seq[j] = //链入第j个链表 　　inFile && i && //输入下一个等价对 　} 　for ( i =0; i &n; i++ ) if ( out[i] == False ) { //未输出, 需要输出 　　cout&& endl && &A new class: & && //输出 　　out[i] = T //作输出标记 　　ListNode *x = seq[i]; //取第i链表头指针 　　ListNode *top = NULL; //栈初始化 　　while (1) { //找类的其它成员 　　　while ( x ) { //处理链表,直到 x=0 　　　　j = x& //成员j 　　　　if ( out[j] == False ) { //未输出, 输出 　　　　　cout && &,& &&　　　　　out[j]=T 　　　　　ListNode *y = x&　　　　　x&link =　　　　　top = //结点x进栈 　　　　　x = //x进到链表下一个结点　　　　}　　　　else x = x& //已输出过,跳过　　　} 　　　if ( top == NULL )　　　　 //栈空退出循环 　　　else { 　　　　x = seq[top&data];　　　　top = top&　　　} 　　　//栈不空, 退栈, x是根据结点编号回溯的另一个链表的头指针　　}　}　　delete [ ] 　delete [ ]}
7.2.3 并查集
１、建立等价类的另一种解决方案是先把每一个对象看作是一个单元素集合，然后按一定顺序将属于同一等价类的元素所在的集合合并。
２、在此过程中将反复地使用一个搜索运算，确定一个元素在哪一个集合中。
３、 能够完成这种功能的集合就是并查集。它支持以下三种操作：Union (Root1, Root2) //并操作；Find (x) //搜索操作；UFSets (s) //构造函数。
４、一般情形，并查集主要涉及两种数据类型：集合名类型和集合元素的类型。
５、对于并查集来说，每个集合用一棵树表示。
６、 集合中每个元素的元素名分别存放在树的结点中，此外，树的每一个结点还有一个指向其双亲结点的指针。
７、为此，需要有两个映射： 集合元素到存放该元素名的树结点间的对应；集合名到表示该集合的树的根结点间的对应。
８、设 S1= {0, 6, 7, 8 }，S2= { 1, 4, 9 }，S3= { 2, 3, 5 }
利用并查集来解决等价问题的步骤如下：
(1)利用UFSets操作, 建立UFSets型集合this, 集合中每一个元素初始化为0，各自形成一个单元素子集合, i =1, 2, &, n。n是集合中元素个数。 (2)重复以下步骤, 直到所有等价对读入并处理完为止。 读入一个等价对[i][j]; 用Find(i), Find(j)搜索 i、j 所属子集合的名 字x和y; 若x && y. 用 Union(x,y) 或 Union(y,x) 将它们合并, 前者的根在 x；后者的根在 y。 (3)为简化讨论，忽略实际的集合名，仅用表示集合的树的根来标识集合。(4) 如果我们确定了元素 i 在根为 j 的树中，而且j有一个指向集合名字表中第 k 项的指针，则集合名即为 name[k]。 (5) 为此，采用树的双亲表示作为集合存储表示。集合元素的编号从0到 n-1。其中 n 是最大元素个数。在双亲表示中，第 i 个数组元素代表包含集合元素 i 的树结点。根结点的双亲为-1，表示集合中的元素个数。为了区别双亲指针信息( &= 0 )，集合元素个数信息用负数表示。
s1Ｕs2的可能的表示方法：
并查集的类定义 :
const int DefaultSize = 10; class UFSets { //并查集的类定义public:　UFSets ( int s = DefaultSize ); 　~UFSets ( ) { delete [ ] } 　const UFSets & operator = ( UFSets const & Value ); 　void Union ( int Root1, int Root2 ); 　int Find ( int x ); 　void UnionByHeight ( int Root1, int Root2 );private:　int *　int };
UFSets::UFSets ( int s ) { //构造函数　size =　parent = new int [size+1]; 　for ( int i = 0; i &= i++ ) 　　parent[i] = -1; }
unsigned int UFSets::Find ( int x ) { //搜索操作　if ( parent[x] &= 0 )　　return 　else 　　return Find ( parent[x] );}
void UFSets::Union ( int Root1, int Root2 ) { //并　parent[Root2] = Root1; //Root2指向Root1} Find和Union操作性能不好。假设最初 n 个元素构成 n 棵树组成的森林，parent[i] = -1。做处理Union(0, 1), Union(1, 2), &, Union(n-2, n-1)后，将产生如图所示的退化的树。执行一次Union操作所需时间是O(1)， n-1次Union操作所需时间是O(n)。若再执行Find(0), Find(1), &, Find(n-1), 若被搜索的元素为i，完成Find(i)操作需要时间为O(i)，完成 n 次搜索需要的总时间将达到
退化的树 ：
Union操作的加权规则：
为避免产生退化的树，改进方法是先判断两集合中元素的个数，如果以 i 为根的树中的结点个数少于以 j 为根的树中的结点个数，即parent[i] & parent[j]，则让 j 成为 i 的双亲，否则，让i成为j的双亲。此即Union的加权规则。
void UFSets::WeightedUnion(int Root1, int Root2) { //按Union的加权规则改进的算法　int temp = parent[Root1] + parent[Root2];　if ( parent[Root2] & parent[Root1] ) { 　　parent[Root1] = Root2; //Root2中结点数多　　parent[Root2] = //Root1指向Root2　} 　else { 　　parent[Root2] = Root1; //Root1中结点数多 　　parent[Root1] = //Root2指向Root1　} }
使用加权规则得到的树 ：
使用并查集处理等价对，形成等价类的过程：
　　Union操作的折叠规则
为进一步改进树的性能，可以使用如下的折叠规则来&压缩路径&。即：如果 j 是从 i 到根的路径上的一个结点，并且 parent[j] & root[j]， 则把 parent[j] 置为 root[i]。　　　　　　　　　　
int UFSets::CollapsingFind ( int i ) { //使用折叠规则的搜索算法　for ( int j = parent[j] &= 0; j = parent[j]); //让 j 循双亲指针走到根 　　while ( i != j ) {//换 parent[i] 到 j　　　int temp = parent[i];　　parent[i] = 　　i = 　} 　return }
使用折叠规则完成单个搜索，所需时间大约增加一倍。但是，它能减少在最坏情况下完成一系列搜索操作所需的时间。
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：15905次
排名：千里之外
转载：16篇
(1)(5)(9)(2) 上传我的文档
 下载
 收藏
所有文档均可在线免费浏览，需要的朋友请看好是否是自己需要的文档。所有资料来源于网络,仅供大家参考学习,版权归原作者。若有侵权，敬请及时告知，本人会及时删除侵权文档,竭诚全力为您服务！！！
 下载此文档
正在努力加载中...
例：设整数集I上的模2同余关系为R,这是I上的等价关系。在...【精选-PPT】
下载积分：1446
内容提示：例：设整数集I上的模2同余关系为R,这是I上的等价关系。在...【精选-PPT】
文档格式：PPT|
浏览次数：51|
上传日期： 23:21:49|
文档星级：
该用户还上传了这些文档
例：设整数集I上的模2同余关系为R,这是I上的等价关系。在...【精选-PPT】.PPT
官方公共微信等价关系与集合的分类 内容详尽，但请以实际操作为准，欢迎下载使用
扫扫二维码，随身浏览文档
手机或平板扫扫即可继续访问
等价关系与集合的分类
举报该文档为侵权文档。
举报该文档含有违规或不良信息。
反馈该文档无法正常浏览。
举报该文档为重复文档。
推荐理由：
将文档分享至：
分享完整地址
文档地址：
粘贴到BBS或博客
flash地址：
支持嵌入FLASH地址的网站使用
html代码：
&embed src='/DocinViewer-4.swf' width='100%' height='600' type=application/x-shockwave-flash ALLOWFULLSCREEN='true' ALLOWSCRIPTACCESS='always'&&/embed&
450px*300px480px*400px650px*490px
支持嵌入HTML代码的网站使用
您的内容已经提交成功
您所提交的内容需要审核后才能发布，请您等待！
3秒自动关闭窗口 上传我的文档
 下载
 收藏
该文档贡献者很忙，什么也没留下。
 下载此文档
正在努力加载中...
等价类划分问题 - 算法与数据结构
下载积分：500
内容提示：等价类划分问题 - 算法与数据结构
文档格式：PDF|
浏览次数：12|
上传日期： 11:58:28|
文档星级：
该用户还上传了这些文档
等价类划分问题 - 算法与数据结构.PDF
官方公共微信