数据结构 - 并查集基础

💝💝💝首先，欢迎各位来到我的博客，很高兴能够在这里和您见面！希望您在这里不仅可以有所收获，同时也能感受到一份轻松欢乐的氛围，祝你生活愉快！

文章目录

• • • 引言
    • 一、并查集的基本概念
    • 二、并查集的操作
    • 三、并查集的实现
    • • 1. 并查集节点类
      • 2. Java 示例代码
    • 四、总结

引言

并查集是一种数据结构，用于处理一些不交集的合并及查询问题。它常被用来解决连通性问题，如判断两个元素是否属于同一个集合，或者合并两个集合等。并查集的主要操作包括查找和合并。本文将深入探讨并查集的基本原理，并通过具体的Java代码详细说明并查集的实现步骤。

一、并查集的基本概念

并查集是一种用于管理一组不相交集合的数据结构。它的主要特点如下：

1. 查找操作（Find）：确定一个元素所在的集合。
2. 合并操作（Union）：将两个集合合并成一个集合。
3. 路径压缩：一种优化技术，用于提高查找操作的效率。
4. 按秩合并：另一种优化技术，用于平衡树的高度，减少合并操作的深度。

二、并查集的操作

并查集支持以下主要操作：

1. 初始化：创建一个空的并查集。
2. 查找：查找某个元素所属的集合。
3. 合并：将两个集合合并成一个集合。
   

三、并查集的实现

接下来，我们将通过一个示例来详细了解并查集的实现步骤。

1. 并查集节点类

定义并查集的节点类，用于存储每个元素的父节点和秩：

public class DisjointSet {     private int[] parent;     private int[] rank;      public DisjointSet(int size) {         parent = new int[size];         rank = new int[size];          // 初始化每个元素的父节点为其自身         for (int i = 0; i < size; i++) {             parent[i] = i;             rank[i] = 0;         }     }      public int find(int x) {         // 路径压缩         if (parent[x] != x) {             parent[x] = find(parent[x]);         }         return parent[x];     }      public void union(int x, int y) {         int rootX = find(x);         int rootY = find(y);          if (rootX != rootY) {             if (rank[rootX] > rank[rootY]) {                 parent[rootY] = rootX;             } else if (rank[rootX] < rank[rootY]) {                 parent[rootX] = rootY;             } else {                 parent[rootY] = rootX;                 rank[rootX]++;             }         }     }      public boolean isConnected(int x, int y) {         return find(x) == find(y);     } } 

2. Java 示例代码

创建并查集并执行操作：

public class Main {     public static void main(String[] args) {         DisjointSet dsu = new DisjointSet(10);          // 连接元素         dsu.union(1, 2);         dsu.union(2, 3);         dsu.union(4, 5);         dsu.union(6, 7);         dsu.union(7, 8);          // 检查连接性         System.out.println("Is 1 connected to 3? " + dsu.isConnected(1, 3));         System.out.println("Is 4 connected to 5? " + dsu.isConnected(4, 5));         System.out.println("Is 1 connected to 4? " + dsu.isConnected(1, 4));          // 连接更多元素         dsu.union(3, 5);          // 再次检查连接性         System.out.println("Is 1 connected to 5 after union? " + dsu.isConnected(1, 5));     } } 

四、总结

并查集是一种非常实用的数据结构，尤其适用于需要频繁进行集合合并和查询的应用场景。在实际编程中，并查集可以用于解决各种连通性问题，例如在图论、网络设计等领域有着广泛的应用。

喜欢博主的同学，请给博主一丢丢打赏吧↓↓↓您的支持是我不断创作的最大动力哟！感谢您的支持哦😘😘😘

💝💝💝如有需要请大家订阅我的专栏【数据结构与算法】哟！我会定期更新相关系列的文章
💝💝💝关注！关注！！请关注！！！请大家关注下博主，您的支持是我不断创作的最大动力！！！

❤️❤️❤️觉得有用的话点个赞 👍🏻 呗。
❤️❤️❤️本人水平有限，如有纰漏，欢迎各位大佬评论批评指正！😄😄😄
💘💘💘如果觉得这篇文对你有帮助的话，也请给个点赞、收藏下吧，非常感谢!👍 👍 👍
🔥🔥🔥Stay Hungry Stay Foolish 道阻且长,行则将至,让我们一起加油吧！🌙🌙🌙