06数据结构---集合与字典

1 .第六章 集合与字典 东南大学计算机学院 方效林 方效林 本课件借鉴了清华大学殷人昆老师 和哈尔滨工业大学张岩老师的课件 

2 . 本章主要内容  并查集 2 

3 . 并查集  互不相交的集合 ( 等价类的划分 )  需要经常合并集合 ( 等价类的合并 )  需要经常查找元素属于哪个集合 3 

4 . 并查集  并查集支持以下操作  初始化 UFSets(s): 将 s 中每个元素自成一个集合  合并 Union(Root1,Root2): 集合 Root2 并入 Root1  查找 Find(x): 查找元素 x 属于哪个集合 4 

5 . 并查集  用树表示集合  初始化时，每个元素自成为一棵树 0 1 2 3 4 5 6 7 8 9 全集合 S 初始化时形成的森林 负数表示没有父结点 -1 表示树中有 1 个结点 -2 表示有 2 个结点， 以此类推 下标 0 1 2 3 4 5 6 7 8 9 父指针 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 初始化时形成的父指针表示 5 

6 . 并查集  用树表示集合  假设经过若干合并后有 3 个集合 {0,6,7,8} ， {1,4,9} {2,3,5} 0 1 2 6 7 8 4 9 3 5 集合的树形表示 下标 0 1 2 3 4 5 6 7 8 9 父指针 -4 -3 -3 2 1 2 0 0 0 1 6 集合的父指针表示 

7 . 并查集 0  用树表示集合  合并 s1={0,6,7,8}  s2={1,4,9} 6 7 8 1  s2 作为 s1 根的子树，或相反 4 9 0 1  第一种合并方式 6 7 8 4 9 1 合并集合 下标 0 1 2 3 4 5 6 7 8 9 0 4 9 父指针 -7 0 -3 2 0 2 0 0 0 0 6 7 8 第二种合并方式 7 第一种合并的父指针表示 

8 . 并查集 0  用树表示集合  合并 s1={0,6,7,8}  s2={1,4,9} 6 7 8 1  s2 作为 s1 根的子树，或相反 4 9  哪一种合并方式好？ 第一种合并方式  先介绍查找 Find 操作  Find(4) 表示 4 所属集合，返回值 0 号结点 ( 即根结点 )  Find 操作时间相当于结点到根路径长度 1 0 4 9 第一种方式好：查找时间更优 合并方式： 6 7 8 将结点数更少的集合作为结点数更多的集合的根的子树 第二种合并方式 8