不相交集类

不相交集的类架构

class DisjSets
{
public:
    explicit DisjSets(int numElement);
    int find (int x) const;
    int find (int x);
    void unionSets1(int root1,int root2);
    void unionSets2(int root1,int root2)
private:
    vector<int> s;

};
DisjSets::DisjSets(int numElement):s(numElement)
{
    for (int i=0;i<s.size();i++)
        s[i]=i;
    //不相交集的初始化例程
}

void DisjSets::unionSets1(int root1,int root2)
{
    s[root2]=root1;
}

int DisjSets::find(int x)const
{
    if(s[x]<0)
        return x;
    else
        return find(s[x]);
}
//按高度求并的程序
void DisjSets::unionSets2(int root1,int root2)
{
    if(s[root2]<s[root1])
        s[root1]=root2;
    else
    {
        if(s[root1]==s[root2])
            s[root1]--;
        s[root2] = root1;
    }
}
//路径压缩
int DisjSets::find(int x)
{
    if(s[x]<0)
        return x;
    else
        return s[x]=find(s[x]);
}
时间: 11-30

不相交集类的相关文章

数据结构与算法——不相交集类的C++实现

简介: 不相交集类是将一些元素合并为不相交的各个集合.在同一个集合中的元素两两等价,不同集合中的元素不等价. 1.等价关系 等价关系必须满足下面三个性质: (1):自反性,对于集合S中的任意元素a,a R a;(R为定义的关系,比如R为<=, >=等等) (2);对称性,a R b当且仅当b R a (3):传递性,若a R b且b R c,则a R c 2.动态等价性问题 集合S中元素a的等价类是集合S的一个子集,该等价类中包含所有与a有等价关系的元素.所以为确定a是否等价b,只需要验证a和

利用不相交集类制作迷宫游戏(数据结构课程设计——迷宫老鼠)

之前大一的时候有几天闲来无事,为了学习做了一个可以自动生成迷宫,可以寻找最短路径的小游戏,现在整理分享一下 简单介绍: 利用不相交集类考虑一个迷宫的生成,一个简单算法就是从各处的墙壁开始(除入口和出口之外).此时,不断地随机选择一面墙,如果被该墙分割的单元彼此不联通,那么就把这面墙拆掉.重复这个过程直到开始单元和终止单元联通,那么就得到一个迷宫.实际上不断的拆掉墙壁直到每个单元都可以从其他单元到达更好(这会使迷宫产生更多误导的路径). 整理一下迷宫的生成算法就是: (1)将迷宫初始时看成一个一个

不相交集类(并查集)

并查集 就是只有合并和 查找操作的一种数据结构  很简单,主要判断一个元素是否在一个集合里 主要应用在最小生成树(Kruskal算法),看到图的时候会将实现代码贴上 package chapter8; /** * 类名:DisjSets 说明:实现并查集 按高度求并,路径压缩 s[i]代表i的父节点 */ public class DisjSets { public DisjSets(int numElements) { s = new int[numElements]; for (int i

Union/find--不相交集类(并查集)

不相交集类 ,可以用来解决等价问题,实现起来简单,可以只使用一个数组. 用一个数组id[N]  记录N个触点,初始化Id[i] =i; 实现动态链接的时候,遍历这个数组,如果p和q的id[p] =id[q] 那么不用管,否则要将pq链接起来,使用uion方法,也就是将p的分量重命名为id[q]. 具体实现如下: package p2; import java.io.File; import java.io.FileNotFoundException; import java.util.Scann

算法之美_源代码发布(10)

本文辑录了<算法之美--隐匿在数据结构背后的语言>(电子工业出版社2016年出版)一书第10章后半部分之代码(P358~P374).全文目录."45个算法"目录."22个经典问题目录",以及有奖捉虫活动详情请见如下链接:http://blog.csdn.net/baimafujinji/article/details/50484348 附录中的经典笔试.面试问题参考答案请见: http://blog.csdn.net/baimafujinji/artic

数据结构——不相交集

在讨论不相交集数据结构之前,首先需要讨论等价关系.首先定义一下关系的概念:若对于每一对元素(a,b),a,bS,aRb或者为true或者为false,则称在集合S上定义关系R.如果aRb是true,那么a和b有关系.所谓的等价关系需要在关系的基础上满足下面三个性质: 1.(自反性)对于所有的aS,aRa. 2.(对称性)aRb当且仅当bRa. 3.(传递性)若aRb且bRc,则aRc. 基于上面的定义可知,相等关系是一个等价关系,小于等于或者大于等于不是等价关系,因为不满足对称性. 在等价关系基

jvm系列(一):java类的加载机制

java类的加载机制 原文:http://www.cnblogs.com/ityouknow/p/5603287.html 1.什么是类的加载 类的加载指的是将类的.class文件中的二进制数据读入到内存中,将其放在运行时数据区的方法区内,然后在堆区创建一个java.lang.Class对象,用来封装类在方法区内的数据结构.类的加载的最终产品是位于堆区中的Class对象,Class对象封装了类在方法区内的数据结构,并且向Java程序员提供了访问方法区内的数据结构的接口. 类加载器并不需要等到某个

iOS -- SKSpriteNode类

SKSpriteNode类 继承自 SKNode:UIResponder:NSObject 符合 NSCoding(SKNode)NSCopying(SKNode)NSObject(NSObject) 框架  /System/Library/Frameworks/SpriteKit.framework 可用性 可用于iOS 7.0或者更晚的版本 声明于 SKSpriteNode.h 参考指南 Sprite Kit Progamming Guide 概览 重要提示:这是一个初步的API或者开发技术

iOS -- SKScene类

SKScene类 继承自 SKEffectNode:SKNode:UIResponder:NSObject 符合 NSCoding(SKNode)NSCopying(SKNode)NSObject(NSObject) 框架  /System/Library/Frameworks/SpriteKit.framework 可用性 可用于iOS 7.0或者更晚的版本 声明于 SKScene.h 参考指南 Sprite Kit Progamming Guide 概览 重要提示:这是一个初步的API或者开