xml地图|网站地图|网站标签 [设为首页] [加入收藏]

python实现一个简单的并查集的示例代码,动态连

来源:http://www.ccidsi.com 作者:最新解决方案 人气:100 发布时间:2019-12-16
摘要:python实现一个粗略的并查集的示范代码,python完成示例代码 并查集是生机勃勃种树型的数据布局,用于拍卖部分不相交集合的合并及查询难题。平日在应用中以森林来表示。 并查集有

python实现一个粗略的并查集的示范代码,python完成示例代码

并查集是生机勃勃种树型的数据布局,用于拍卖部分不相交集合的合并及查询难题。平日在应用中以森林来表示。

并查集有两种基本操作,得到根节点,判定两节点是不是衔接,甚至将两不接入的节点相连(相当于将两节点各自的汇聚合併)

用UnionFind类来代表三个并查集,在布局函数中,初步化三个数组parent,parent[i]表示的意义为,索引为i的节点,它的直接父节点为parent[i]。发轫化时种种节点都不随处,因而初阶化parent[i]=i,让投机成为团结的父节点,进而达成各节点不互连。

  def __init__(self, n):
    self.parent = list(range(n))

由于parent[i]仅表示友好的第一手父节点,查询多少个节点是还是不是相交需求比较它们的根节点是不是相同。由此要卷入一个查询自身根节点的办法。

  def get_root(self, i):
    while i != self.parent[i]:
      i = self.parent[i]

    return i

接下去能够通过来对比根节点是或不是相像来判别两节点是还是不是衔接。

  def is_connected(self, i, j):
    return self.get_root(i) == self.get_root(j)

当要连通三个节点时,大家要将里面一个节点的根节点的parent,设置为另二个节点的根节点。注意,连通八个节点实际不是单纯让两节点本人不断,实际上是让它们所属的汇集达成归拢。

  def union(self, i, j):
    i_root = self.get_root(i)
    j_root = self.get_root(j)
    self.parent[i_root] = j_root

接下去大家做七个小优化。

是因为调用get_root时索要经过不断找本人的直白父节点,来搜寻根节点,借使那棵树的层级过深,会招致品质受到严重影响。由此大家须求在union时,尽只怕的减削合并后的树的莫斯中国科学技术大学学。

在构造函数中新建三个数组rank,rank[i]表示节点i所在的聚合的树的莫斯中国科学技术大学学。

故此,当合併树时,分别收获节点i和节点j的root i_root和j_root之后,我们因此拜见rank[i_root]和rank[j_root]来相比较两棵树的冲天,将中度比较小的那棵连到高度较高的那棵上。假如高度相等,则能够不管,并将rank值加豆蔻梢头。

  def union(self, i, j):
    i_root = self.get_root(i)
    j_root = self.get_root(j)

    if self.rank[i_root] == self.rank[j_root]:
      self.parent[i_root] = j_root
      self.rank[j_root]  = 1
    elif self.rank[i_root] > self.rank[j_root]:
      self.parent[j_root] = i_root
    else:
      self.parent[i_root] = j_root

通过对union操作的改善可防止范树的万丈过高。大家还足以对get_root操作本人进行优化。

当下每一回实施get_root时,须求意气风发层意气风发层的找到本人的父节点,很为难。由于根节点未有父节点,何况小说开首处涉及过假诺一个节点没有父节点,那么它的父节点正是和煦,因而得以说除非根节点的父节点是仁慈自己。未来大家增加二个料定,判断当前节点的父节点是否为根节点,假设不为根节点,就递归地将自身的父节点设置为根节点,最终回到本人的父节点。

  def get_root(self, i):
    if self.parent[i] != self.parent[self.parent[i]]:
      self.parent[i] = self.get_root(self.parent[i])
    return self.parent[i]

如上是python实现三个简约的并查集的艺术。希望对我们的上学抱有利于,也冀望我们多多指教帮客之家。

并查集是风姿浪漫种树型的数据布局,用于拍卖局地不相交集结的合并及查询难题。常...

1. 前言

并查集(Union Find Set),也称为不相交集数据布局(Disjointed Set Data Structure),五个名字分别回顾了那意气风发数据构造的局地特征。轻松地讲,并查集维护了一列互不相交的集结S1、S2、S3、…,帮协助调查找(find)与联合(union)三种操作。

  • find
    找到成分所在的联谊,常常重临该集结的代表元(representative)
    成分a与成分b是或不是归属同三个集中,只要剖断find(a)与find(b)是或不是等于
  • union
    将多少个聚众归拢为二个集合
    将成分a与成分b所在的联谊合併为贰个会合,使用union(a,b)

本人的实今后这里

2. 原理

2.1 功底算法

UnionFindSet用树表示集合,所谓维护一列互不相交的集中约等于有过多棵树。每棵树的成分归属叁个会面,树根的因素正是聚众的代表元,所以UnionFindSet实际上维护了贰个多棵树构成的森林。

  • find(x卡塔尔国正是找x所在的树的根须
  • union(x, y卡塔尔(英语:State of Qatar)正是合併x和y所在的树

来看UnionFindSet的定义:

class UnionFindSet {
    public:
        UnionFindSet(int n);
        int Find(int x);
        void Union(int x, int y);
    private:
        std::vector<int> parent;
};

与大面积的树形数据构造分裂,并查集的链接关系不是从parent指向child而是从child指向parent,这一个链接新闻保存在parent数组里。

  1. 若parent[x] == x,则x正是x所在树的树根
  2. 若parent[x] != x,则x是parent[x]的子节点

降解完parent的含义,Find的完成格局也就绘身绘色了。

int UnionFindSet::Find(int x) {
    if (parent[x] == x)
        return x;
    else
        return Find(parent[x]);
}

布局函数UnionFindSet(int n卡塔尔国表示最早有n个互不相交的集纳,代表元分别为0、1、2、…(n-1卡塔尔(قطر‎。

UnionFindSet::UnionFindSet(int n) {
    parent.resize(n);
    for (int i = 0; i < n;   i) {
        parent[i] = i;
    }
}

要联合两棵树,只要把生龙活虎棵根节点的parent设为另风度翩翩棵树的根节点。

void UnionFindSet::Union(int x, int y) {
    int root_x = Find(x);
    int root_y = Find(y);
    if (root_x == root_y)
        return;
    parent[root_y] = root_x;
}

用图片解释find和union中parent的作用,此中child在下层,parent在上层。
3的parent是2,那么调用find(3卡塔尔时:

  • parent[3] = 2,调用find(2)
  • parent[2] = 2,返回2

图片 1

调用find(3)

调用union(1, 3)时:

  • 调用find(1),得到root_x = 0
  • 调用find(3),得到root_y = 2
  • parent[2] = 0

图片 2

调用union(1, 3)

2.2 优化合并

并查集正是大器晚成组树构成的老林,与多如牛毛的搜寻树相比较只是链接关系从parent->child产生了child->parent,所以也会现出搜索树中的难题。极端气象下n个节点像链表这样构成n层,对于最尾部的节点,find复杂度自然是O(n卡塔尔(قطر‎,而union由于调用find复杂度也会形成O(n卡塔尔(英语:State of Qatar)。
既然树的高度影响功效,那么能够想尽幸免高树出现,也正是本小节的优化归并;也足以主张把高树变矮,也便是下一小节的路线压缩。

优化合併就是优化union操作,简单无情地讲,便是统临时长久把矮树作为高树的子树。剖断哪棵树相当矮有union-by-size和union-by-height三种做法,union-by-height是在类中增多height数组记录每一种节点的莫大,union-by-size是在类中增多size数组记录种种节点的子节点数量,两个效果完全雷同。小编使用union-by-height,感兴趣union-by-size的能够看这里

在类中增加height数组:

class UnionFindSet {
    public:
        UnionFindSet(int n);
        int Find(int x);
        void Union(int x, int y);
        void Display(void);
    private:
        std::vector<int> parent;
        std::vector<int> height;
};

改进布局函数UnionFindSet(int n卡塔尔:

UnionFindSet::UnionFindSet(int n) {
    parent.resize(n);
    height.resize(n);

    for (int i = 0; i < n;   i) {
        parent[i] = i;
        height[i] = 0;
    }
}

新的union算法:

void UnionFindSet::Union(int x, int y) {
    int root_x = Find(x);
    int root_y = Find(y);

    if (root_x == root_y)
        return;

    if (height[root_x] > height[root_y]) {
        parent[root_y] = root_x;
    } else if (height[root_x] < height[root_y]) {
        parent[root_x] = root_y;
    } else {
        parent[root_y] = root_x;
          height[root_x];
    }
}

只顾唯有根节点高度相像有时间必要更新height,因为两棵树中度不等于时矮的那棵最少比高的矮生机勃勃层。因而对于有n个节点的并查集,height的最大值为lgn,所以find和union的算法复杂度都至多为O(lgn卡塔尔国。

本文由68399皇家赌场发布于最新解决方案,转载请注明出处:python实现一个简单的并查集的示例代码,动态连

关键词: 68399皇家赌场 IT共论 Algorithms

上一篇:10信号量与管程,RTX操作系统

下一篇:没有了

最火资讯