第11章不相交集.pptVIP

Find函数的实现 关键问题：如何在查找的过程中改变结点的父结点？ int DisjointSet::Find(int x) { if (parent[x] 0) return x; return parent[x] = Find(parent[x]); //利用递归函数调用时的回溯过程，将根结点的下标赋给路径上的各个结点 } Union函数的实现 void DisjointSet::Union(int root1, int root2) { if (root1 == root2) return; //为同一棵树，直接返回 if (parent[root1] parent[root2]) //值为负数 { parent[root2] += parent[root1]; parent[root1] = root2;} //将规模小的树作为规模大的树的子树 else { parent[root1] += parent[root2]; parent[root2] = root1;} } 第11章 不相交集合类 主要用来解决等价问题 等价关系与等价类 不相交集 不相交集的实现 不相交集类的实现 不相交集的应用 不相交集的应用 迷宫问题 最近共同祖先问题 其它 Games (Go, Hex). Dynamic connectivity. Equivalence of finite state automata. Hoshen-Kopelman algorithm in physics. Compiling equivalence statements in Fortran. Morphological attribute openings and closings. Matlabs bwlabel() function in image processing. 应用—迷宫问题 把迷宫看成由M×N个矩形单元组成，入口在左上角，出口在右下角。左上角的单元与右下角的单元是连通的，单元之间用墙隔开。 一个5×5的迷宫 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 生成迷宫的算法 开始时假设所有的地方都有墙（除了入口和出口），所有的单元都不连通。 我们不断地随机选择一堵墙，如果由该墙分割的单元互相之间没有连通，则把墙拆除。 重复上述过程，直到连通了入口和出口，就得到了一个迷宫。 继续拆墙直到从每一个单元都能到达其他任一单元当然更好，因为这样做会在迷宫中生成更多的错误路径 算法实现 连通关系是一个等价关系。 迷宫问题转化成等价类的归并问题。 开始时，每个单元是一个等价类。 选择相邻两个单元，判别是否在一个等价类。如果不是，敲开两个单元之间的墙，使之连通。归并两个等价类。 重复上述过程，直到所有单元都在一个等价类中。 初始的配置 某些墙已经被拆除。此时，如果我们随机选择8和13之间的墙，这堵墙不用拆掉，因为8和13已经连通 我们随机选择了18和13之间的墙；因为18和13没有连通，这堵墙被拆除 void createPuzzle(int size) //size为迷宫的规模 { int num1, num2; DisjointSet ds(size*size); //不相交集有size*size个单元 srand(time(0)); //初始化随机数发生器 while (ds.Find(0) != ds.Find(size*size-1)) { //入口和出口不在一个集合则循环 while (true) { //选择两个相邻的不连通单元num1, num2 num1 = rand() * size * size / (RAND_MAX + 1); //随机选择一个单元， num2 = num1-size; //检查上方的单元 if (num2 = 0) if (ds.Find(num1) != ds.Find(num2)) break; num2 = num1 - 1; //检查左边的单元 if (num1 % size != 0) if (ds.Find(num1) != ds.Find(num2)) break; num2 = num1 + size; //检查下方的单元 if (num2 size * size) if (ds.Find(num1) != ds.Find(num2)) break; num2 = num1 + 1;