并查集(Union-Find Set)介绍

并查集是一种数据结构,用于处理一些不相交集合的合并及查询问题。主要操作包括:

  1. 初始化(Initial): 初始化并查集,使每个元素自成一个集合。
  2. 查找(Find): 查找某个元素所属的集合。
  3. 合并(Union): 将两个集合合并成一个集合。

并查集常用于解决图论中的连通性问题,例如判断图中两个节点是否在同一个连通分量内。

并查集的实现

以下是实现并查集的基本代码。

#include <stdio.h>
#define SIZE 100

int UFSets[SIZE];

// 初始化并查集
void Initial(int S[]) {
    for (int i = 0; i < SIZE; i++) {
        S[i] = -1;
    }
}

// 查找并返回x所属的集合的根
int Find(int S[], int x) {
    while (S[x] >= 0) {
        x = S[x];
    }
    return x;
}

// 合并两个集合
void Union(int S[], int Root1, int Root2) {
    if (Root1 == Root2)
        return;
    S[Root2] = Root1;
}

int main() {
    // 初始化并查集
    Initial(UFSets);

    // 示例操作:合并和查找
    Union(UFSets, Find(UFSets, 1), Find(UFSets, 2));
    printf("Root of 1: %d\n", Find(UFSets, 1));
    printf("Root of 2: %d\n", Find(UFSets, 2));

    return 0;
}

代码解释

  1. 初始化并查集
void Initial(int S[]) {
    for (int i = 0; i < SIZE; i++) {
        S[i] = -1;
    }
}

该函数将数组 S 的每个元素初始化为 -1,表示每个元素自成一个集合。

  1. 查找操作
int Find(int S[], int x) {
    while (S[x] >= 0) {
        x = S[x];
    }
    return x;
}

该函数通过迭代找到元素 x 所属集合的根节点(即根节点的值小于 0)。

  1. 合并操作
void Union(int S[], int Root1, int Root2) {
    if (Root1 == Root2)
        return;
    S[Root2] = Root1;
}

该函数将两个集合的根节点 Root1Root2 合并,将 Root2 连接到 Root1

示例操作

main 函数中,我们初始化并查集,然后进行合并和查找操作:

int main() {
    Initial(UFSets);

    // 合并1和2所在的集合
    Union(UFSets, Find(UFSets, 1), Find(UFSets, 2));
    
    // 查找1和2的根
    printf("Root of 1: %d\n", Find(UFSets, 1));
    printf("Root of 2: %d\n", Find(UFSets, 2));

    return 0;
}

通过这些操作,可以看到并查集的基本功能:初始化、查找和合并。实际应用中,通常还会进行路径压缩优化查找效率,按秩合并优化合并效率。

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部