JavaScript 并查集 (Union-Find)

并查集是一种数据结构，主要用于处理一些不相交集合的合并及查询问题。它支持两种操作：查找和合并。查找操作用于判断两个元素是否属于同一个集合，而合并操作则将两个集合合并为一个。

并查集的基本概念

集合与元素

在并查集中，我们通常会有一个或多个不相交的集合，每个集合由若干个元素组成。这些元素可以是数字、字符串或其他类型的数据。

查找操作

查找操作用于判断两个元素是否属于同一个集合。如果两个元素属于同一个集合，则它们的根节点相同；否则，它们属于不同的集合。

合并操作

合并操作用于将两个集合合并为一个集合。这通常通过将一个集合的根节点指向另一个集合的根节点来实现。

并查集的数据结构

并查集通常使用数组或对象来存储每个元素的信息。数组中的每个元素表示该元素的父节点，根节点的父节点指向自身。

数组实现

在数组实现中，数组的索引表示元素，值表示父节点。例如，对于一个包含三个元素的集合，数组可能如下所示：

let parent = [0, 1, 2]; // 初始状态，每个元素都是自己的父节点

对象实现

在对象实现中，对象的键表示元素，值表示父节点。例如，对于一个包含三个元素的集合，对象可能如下所示：

let parent = {0: 0, 1: 1, 2: 2}; // 初始状态，每个元素都是自己的父节点

并查集的操作

初始化操作

初始化操作用于创建一个新的并查集，并将每个元素初始化为其自身的父节点。

function makeSet(n) {
    let parent = {};
    for (let i = 0; i < n; i++) {
        parent[i] = i;
    }
    return parent;
}

查找操作

查找操作用于找到某个元素的根节点。为了提高效率，可以采用路径压缩技术，即将查找过程中经过的所有节点直接连接到根节点上。

function find(parent, x) {
    if (parent[x] !== x) {
        parent[x] = find(parent, parent[x]); // 路径压缩
    }
    return parent[x];
}

合并操作

合并操作用于将两个集合合并为一个集合。为了减少树的高度，可以采用按秩合并技术，即将较低的树连接到较高的树上。

// www.javascriptcn.com code example
function union(parent, rank, x, y) {
    let rootX = find(parent, x);
    let rootY = find(parent, 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] += 1;
        }
    }
}

并查集的应用场景

并查集广泛应用于各种需要快速处理不相交集合的问题，常见的应用场景包括：

• 图的连通性检测：判断一个图是否连通，或者判断两个节点是否连通。
• 最小生成树算法：Kruskal 算法在构建最小生成树时需要用到并查集来避免环的形成。
• 网络连通性问题：在计算机网络中，判断两个节点是否属于同一个网络段。

示例代码

以下是一个完整的示例代码，展示了如何使用并查集来解决图的连通性问题。

// www.javascriptcn.com code example
function makeSet(n) {
    let parent = {};
    let rank = {};

    for (let i = 0; i < n; i++) {
        parent[i] = i;
        rank[i] = 0;
    }

    return { parent, rank };
}

function find(parent, x) {
    if (parent[x] !== x) {
        parent[x] = find(parent, parent[x]); // 路径压缩
    }
    return parent[x];
}

function union(parent, rank, x, y) {
    let rootX = find(parent, x);
    let rootY = find(parent, 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] += 1;
        }
    }
}

// 示例：判断图的连通性
function isConnected(edges, n) {
    let { parent, rank } = makeSet(n);

    for (let edge of edges) {
        let [u, v] = edge;
        union(parent, rank, u, v);
    }

    let root = find(parent, 0);
    for (let i = 1; i < n; i++) {
        if (find(parent, i) !== root) {
            return false;
        }
    }
    return true;
}

let edges = [[0, 1], [1, 2], [2, 3]];
let n = 4;

console.log(isConnected(edges, n)); // 输出 true

总结

并查集是一种非常高效的数据结构，适用于处理不相交集合的合并和查询问题。通过路径压缩和按秩合并技术，可以极大地提高并查集的性能。在实际应用中，我们可以根据具体需求选择合适的实现方式，并利用并查集解决各种复杂的问题。