首页
学习
活动
专区
圈层
工具
发布
  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    数据结构之并查集

    并查集实际上是一种很不一样的树形结构,用于处理一些不相交集合(Disjoint Sets)的合并及查询问题。...之所以说并查集是一种“不一样”的树形结构,是因为一般的树形结构都是父节点指向子节点的,而并查集则是反过来,子节点指向父节点,并且这棵树会是一棵多叉树。...使用“Quick Union”思路实现并查集时,我们将每一个元素,看做是一个节点。但与普通的树形结构不同的是,并查集的树是子节点指向父节点的,在之前也提到过。如下: ?...我们使用数组来表示树形结构的并查集时,子节点指向父节点的指针实际就是存储父节点的数组索引。而且在初始化后,未进行合并操作时,每个元素都是自己成为一棵树的根节点,代表不同的集合。...也就是说此时会有多棵树,这种情况称之为森林结构,这也是为什么会存在合并两棵树的情况。如下所示: ? 对应的数组表示如下: ?

    1.4K20

    数据结构—并查集《上》

    这是无量测试之道的第175篇原创   今天主要介绍的是并查集这种数据结构。其本质上是解决某一些特定问题的而设计出的数据结构。大家可以了解下这种数据结构,作为自己知识的储备。...通过一个实际的问题引出并查集   假设有 n 个村庄,有些村庄之间有连接的路,有些村庄之间并没有连接的路 设计一个数据结构,能够快速执行 2 个操作: 查询 2 个村庄之间是否有连接的路 连接 2...并查集(Union Find) 并查集也叫作不相交集合(Disjoint Set) 并查集有2个核心操作: 查找(Find):查找元素所在的集合 (这里的集合并不是特指Set这种数据结构,是指广义的数据集合...数组索引代表元素值 索引对应的值代表这个元素的根节点 将{0,1,2,3,4,5,6,7}存储到数组中,如下图:   因此,并查集是可以用数组实现的树形结构(二叉堆、优先级队列也是可以用数组实现的树形结构...) 并查集数据结构的接口定义 /** * 查找v所属的集合(根结点) */ public abstract int find(int v); /** * 合并v1、v2所在的集合 */ public

    77910

    高阶数据结构-并查集

    树形结构展示 并查集的本质就是森林,森林就是很多棵树 森林指针数组展示 指针数组有两个特点: 1、一个位置的值是负数,那它就是树的根,这个负数的绝对值就是这棵树节点的个数 2、一个位置的值是正数,那它就是双亲的下标...回顾全文,并查集作为处理 “动态连通性” 问题的经典数据结构,其核心魅力在于用极简的数组模拟森林,通过高效操作实现集合的管理与查询。...统计集合总数,整个类结构简洁且逻辑闭环。...,真正实现了 “数据结构服务于实际需求”。​...最后想说,学习并查集的意义不仅在于掌握一种工具,更在于理解 “用简单结构解决复杂问题” 的思维:通过抽象元素关系(用数组代森林)、优化操作路径(路径压缩)、平衡结构形态(按大小合并),让看似繁琐的 “集合管理

    34710

    数据结构 - 并查集基础

    引言 并查集是一种数据结构,用于处理一些不交集的合并及查询问题。它常被用来解决连通性问题,如判断两个元素是否属于同一个集合,或者合并两个集合等。并查集的主要操作包括查找和合并。...本文将深入探讨并查集的基本原理,并通过具体的Java代码详细说明并查集的实现步骤。 一、并查集的基本概念 并查集是一种用于管理一组不相交集合的数据结构。...二、并查集的操作 并查集支持以下主要操作: 初始化:创建一个空的并查集。 查找:查找某个元素所属的集合。 合并:将两个集合合并成一个集合。...三、并查集的实现 接下来,我们将通过一个示例来详细了解并查集的实现步骤。 1...." + dsu.isConnected(1, 5)); } } 四、总结 并查集是一种非常实用的数据结构,尤其适用于需要频繁进行集合合并和查询的应用场景。

    48210

    数据结构 - 并查集路径压缩

    引言 并查集是一种用于管理一组不相交集合的数据结构,常用于解决连通性问题。在并查集中,路径压缩是一种重要的优化技术,它能够显著提高查找操作的效率。...本文将深入探讨并查集路径压缩的基本原理,并通过具体的Java代码详细说明如何实现高效的路径压缩。 一、并查集的基本概念 并查集是一种用于管理一组不相交集合的数据结构。...三、并查集路径压缩的实现 接下来,我们将通过一个示例来详细了解并查集路径压缩的实现步骤。 1....并查集节点类 定义并查集的节点类,用于存储每个元素的父节点: public class DisjointSet { private int[] parent; public DisjointSet...五、总结 并查集是一种非常实用的数据结构,尤其适用于需要频繁进行集合合并和查询的应用场景。在实际编程中,并查集可以用于解决各种连通性问题,例如在图论、网络设计等领域有着广泛的应用。

    64910

    Python笔记:并查集(DSU)结构简介

    并查集是什么 并查集(Disjoint Set Union)是一种常用的处理不相交集合间的合并与查找功能的树形结构,配合与之对应的联合-搜索算法(Union Find Algorithm),可以将不相交集合间的合并与查找功能的时间复杂度大幅缩减至...= y: self.root[y] = x return 上述代码即为最为一般性的并查集结构。 2....调整树形结构 为了更好地优化算法的效率,我们可以控制树形结构,使其尽可能地扁平化,避免出现链型结构导致深度过深,我们经常会通过记录树的深度的方式优化树形结构,从而优化算法效率。...Leetcode例题分析 下面,我们来通过一些leetcode中的例题来考察并查集结构的实际用法。 1. Leetcode 547....Friend Circles 这一题是最为典型的并查集使用场景,我们直接套用并查集结构就能解答这道题。

    4.6K31

    【数据结构】并查集(路径压缩)

    并查集 1.朴素版本 1. 并查集解决的是连通块的问题,常见操作有,判断两个元素是否在同一个连通块当中,两个非同一连通块的元素合并到一个连通块当中。...并查集和堆的结构类似,都是采用数组存储下一个节点的下标的方式来抽象成一棵树,只不过堆的数组对应的是一棵二叉树,而并查集的数组对应的是森林,可以抽象成很多的树,并且每棵树也不一定是二叉树,任意形状均可。...并查集合并算法的性能瓶颈其实是在找根的操作上,如果一棵树的高度是N,那么找根的时间复杂度其实就是O(N)了,这样的效率实际上是很低的,所以后面会进行三种方式的优化。...统计并查集中树的个数其实也比较简单,只需要统计根节点是自己的节点个数即可。...其实三种优化方式都是差不多的,因为题目所给数据构成的树可能不是很高,所以O(logN)渐进于O(1) 5.练习题 547.省份数量 该题给出了邻接矩阵,我们只需要遍历上半部分,将相连的城市合并到一个连通块当中,最后统计并查集中连通块的总数即为省份的数量

    80910
    领券