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

用户11147438

发布于 2024-08-09 11:23:13

4660

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

引言

并查集是一种用于管理一组不相交集合的数据结构，常用于解决连通性问题。在并查集中，路径压缩是一种重要的优化技术，它能够显著提高查找操作的效率。本文将深入探讨并查集路径压缩的基本原理，并通过具体的Java代码详细说明如何实现高效的路径压缩。

一、并查集的基本概念

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

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

二、并查集路径压缩的方法

路径压缩是通过在查找操作中将路径上的每个节点的父节点直接指向根节点来减少查找操作的深度。这种方法能够显著减少未来查找操作的时间复杂度。

三、并查集路径压缩的实现

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

1. 并查集节点类

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

public class DisjointSet {
    private int[] parent;

    public DisjointSet(int size) {
        parent = new int[size];

        // 初始化每个元素的父节点为其自身
        for (int i = 0; i < size; i++) {
            parent[i] = i;
        }
    }

    public int find(int x) {
        // 路径压缩
        if (parent[x] != x) {
            parent[x] = find(parent[x]);  // Path compression
        }
        return parent[x];
    }

    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX != rootY) {
            parent[rootY] = rootX;  // Merge by setting one root as the parent of another
        }
    }

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