数据结构 - 并查集基础

用户11147438

发布于 2024-08-09 11:20:49

1120

发布于 2024-08-09 11:20:49

文章被收录于专栏：Linux系列

引言

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

一、并查集的基本概念

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

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

二、并查集的操作

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

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

三、并查集的实现

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

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));
    }
}