积分商城

最新搜索： stm32 jflash 人形机器人 CRC32校验工具 STC8H8K64S4U
您现在的位置是：首页 > 笔记 > 并查集的高效实现：路径压缩与按秩合并.docx
推荐星级：
  • 1
  • 2
  • 3
  • 4
  • 5

并查集的高效实现：路径压缩与按秩合并.docx

更新时间：2026-10-10 20:42:54 大小：39K 上传用户：江岚查看TA发布的资源 标签：并查集路径压缩按秩合并Union-FindDisjoint Set 下载积分：2分 评价赚积分 （如何评价?） 打赏 收藏 评论(0) 举报

资料介绍

并查集的高效实现：路径压缩与按秩合并

一、为什么需要优化

基础的并查集在最坏情况下（树退化为链表）查找时间复杂度为O(n)。通过路径压缩和按秩合并两种优化，可以将操作复杂度降为接近O(1)。

// 最坏情况：树退化为链表
1 → 2 → 3 → 4 → 5 → ... → n
find(n) 需要遍历n个节点，O(n)

二、路径压缩

2.1 原理

在查找过程中，将路径上所有节点直接指向根节点。这样不仅本次查找更快，后续查找也更快。

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

效果：

压缩前：1 → 2 → 3 → 4 → 5（根是5）
        find(1) 遍历4个节点
压缩后：1 → 5, 2 → 5, 3 → 5, 4 → 5（所有直接指向根）
        find(1) 只需1次跳转

2.2 递归与迭代实现

// 递归（简洁但可能栈溢出）
int findRecursive(int x) {
    if (parent[x] != x) {
        parent[x] = findRecursive(parent[x]);
    }


部分文件列表

文件名 大小
并查集的高效实现：路径压缩与按秩合并.docx 39K

相关下载

全部评论(0)

暂无评论
评论赚积分>>

上传资源 上传优质资源有赏金

热门标签

更多>>

最新上传

  • 打赏
  • 30日榜单

热门下载

资料专题

推荐下载

本站上的所有资源均为源于网上收集或者由用户自行上传，仅供学习和研究使用，无任何商业目的，版权归原作如有侵权，请 来信指出，本站将立即改正。

ICP许可证号：京ICP证070360号     21IC电子网 2000- 版权所有

京ICP备11013301号

京公网安备 11010802024343号