等价类的并查 ( UNION/FIND)算法 用树来表示等价类的并查 FIND ■“ UNION/FIND算法用一棵树代表一个集合 判斷两个结点是否在同一个集合中 集合用父结点代替 查找一个给定结点的根结点 如果两个结点在同一棵树中,则认为它们在同一个集合中 UNION 结点中仅需保存父指针信息 如果一个等价的两个元素不在同一棵树中 存储为一个以其结点为元亲的数组一静态 归并两个集合,这个归并过程常常被称 北大啦 机新有,食 大息单 张铭 有,盛 UNION/FIND算法示例()4UNN/FND算法示例(2) 例:10个结点A、B、C、D、E、F、G、H、J、K 首先对这5个等价对进行处理(AB)、(cK)、(F)、 和它们的等价关系(AB)、(cK)、,F)、 (HE)、(D,G) 后四个等价对处理同 (HE)、(D,G)、《KA)、(E,G)、(H刀) (AL B) (A, B)C,K, FXE,H)D, G) 1 D 如@@o23508① NBcK|GH可 北大位 张 新有,究 张铭鷾 叔有,印鱼究 UNION/FIND算法示例(2) 父指针表示法的树结点定义 然后对两个等价对(K,A)和(E,G)进行处理 template<class T> class harTree Node 己是根节点,A 以网属材罢合并 //树结点定义 4|5|6 /结点的值 ABCKDEFGHBOPG ParTreenode<T>* parent;//父結点指针 ncount//以此结点为根的子树的总结点个数 Par'TreeNodeO; /构造函数 virtual~ ParTreeNode(};//析构函数 新有,食邮岛究 张铭9 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 49 等价类的并查 （UNION/FIND）算法 „ FIND „ 判断两个结点是否在同一个集合中 „ 查找一个给定结点的根结点 „ UNION „ 如果一个等价的两个元素不在同一棵树中 „ 归并两个集合，这个归并过程常常被称为 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 50 用树来表示等价类的并查 „ “UNION/FIND”算法用一棵树代表一个集合 „ 集合用父结点代替 „ 如果两个结点在同一棵树中，则认为它们在同一个集合中 „ 树 „ 结点中仅需保存父指针信息 „ 存储为一个以其结点为元素的数组——静态指针数组 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 51 UNION/FIND算法示例(1) 例：10个结点A、B、C、D、E、F、G、H、J、K 和它们的等价关系(A,B)、(C,K) 、(J,F) 、 (H,E) 、(D,G) 、(K,A) 、(E,G) 、(H,J) A B C K D E F G H J 01 89 2 3 4 5 6 7 A B C K D E F G H J 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 52 UNION/FIND算法示例(2) 首先对这5个等价对进行处理 (A,B)、(C,K) 、(J,F) 、 (H,E) 、(D,G) A C F E D B K J H G (A,B) 01 89 2 3 4 5 6 7 A B C K D E F G H J 0 (C,K) 2 (J,F)(E,H)(D,G) 后四个等价对处理同 （A，B） 4 5 6 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 53 UNION/FIND算法示例(2) 然后对两个等价对（K，A）和（E，G）进行处理 A C F E D B K J H G 01 8 2 3 4 5 6 7 9 A B C K D E F G H J 0 2 4 5 6 K所在树的根为C，A自 (K,A) 己是根节点，A！=C, 所以两颗树要合并 (E,G) 同(K,A) 0 4 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 54 父指针表示法的树结点定义 template<class T> class ParTreeNode { //树结点定义 private: T value; //结点的值 ParTreeNode<T>* parent;//父结点指针 int nCount;//以此结点为根的子树的总结点个数 public: ParTreeNode(); //构造函数 virtual ~ParTreeNode(){}; //析构函数