Weighted Quick Union with Path Compression (WQUPC)

在WQU基础上,添加一步路径压缩.

前面的优化都是在union,路径压缩是在find上面做文章.

这里的路径压缩我还没完全搞明白,之后不断再来的,不管是理解还是博文编排素材之类的.

说是加一步压缩是确实只在find里增加了一个步骤,而这里ALGS4官方又有两个版本,由于我现在没有把问题规模化,只是简单的实例化增加几个连接,

还不能很好的理解两者优劣,就都贴上来吧.

 1 class WeightedQuickUnion():
 2     __count = int()     #number of components
 3     __parent = list()   #__parent[i] parent of i
 4     __size = list()     #size[i] number of sites in subtree rooted at i
 5     #Each site is initially in its own component
 6     def __init__(self, N):
 7         self.__count = N
 8         for i in range(0, self.__count):
 9             self.__parent.append(i)
10             self.__size.append(1)
11     #Return the component identifier for the component containing site
12     def find(self, p):
13         self.validate(p)
14         root = p
15         #find root identifier
16         while (root != self.__parent[root]):
17             root = self.__parent[root]
18         #merge the component containing site
19         #***question:the loop ?
20         while (p != root):
21             newp = self.__parent[p]
22             self.__parent[p] = root
23             p = newp
24         return p
25 
26     def connected(self, p, q):
27         return self.find(p) == self.find(q)
28     #Merges the component containig site p with
29     #the component containing site q
30     def union(self, p, q):
31         rootP=self.find(p)
32         rootQ=self.find(q)
33         if (rootP == rootQ):
34             return
35         if (self.__size[rootP] < self.__size[rootQ]):
36             self.__parent[rootP] = rootQ
37             self.__size[rootQ] += self.__size[rootP]
38         else:
39             self.__parent[rootQ] = rootP
40             self.__size[rootP] += self.__size[rootQ]
41         self.__count-=1
42     def validate(self, p):
43         n = len(self.__parent)
44         if (p < 0 or p >= n):
45             raise ValueError("index", p, "is not between 0 and", (n - 1))
46     def traversal(self):
47         for i in self.__parent:
48             print(i, end=' ')
49 WQU = WeightedQuickUnion(12)
50 WQU.union(0, 1)
51 WQU.union(1, 2)
52 WQU.union(3, 4)
53 WQU.union(4, 5)
54 WQU.union(5, 2)
55 WQU.union(6, 7)
56 WQU.union(7, 8)
57 WQU.union(9, 10)
58 WQU.union(10, 11)
59 WQU.union(11, 8)
60 WQU.union(11, 2)
61 print(WQU.connected(2, 8))
62 WQU.traversal()

1 def find(self,p):
2     self.validate(p)
3     while p != self.__parent[p]:
4         self.__parent[p] = self.__parent[__self.parent[p]]
5         p = self.__parent[p]
6     return p

上面单独给出了另一种写法,就是网课里面那么写的,课程可能是以前录制好的,多次播放.然后他们的程序不断更新了.

先出现的那种写法:

        root = p
        #find root identifier
        while (root != self.__parent[root]):
            root = self.__parent[root]

先找到根节点,

        while (p != root):
            newp = self.__parent[p]
            self.__parent[p] = root
            p = newp
        return p

(假设p不等于root)

然后先取出p的parent,然后把p的parent移接到根结点上,最后p赋值为p原先的parent也就是刚刚接到根结点的那个结点.

下一次迭代的时候p!=root,取出p的parent,这里已经取出root了,然后进行一次root赋值root冗余操作,最后p赋值为root,

再下一次迭代p==root,循环退出,返回p的root.

整个过程会移动p的parent位置,且一次性移动到根节点,循环会执行两次,第二次只是为了移动p的值,以便退出循环.

所查结点和其parent以及其grandparent会形成三层结构,(不考虑以当前结点为parent的结点,实际上这些结点会跟着移动位置的)

之后那种方法:

(也假设p!=root)

第一次p!=root,将p的panrent移动到p的grandparent,(当前循环次数的),p赋值为原p的grandparent.

假设第二次p!=root,(树很高:>)那么还会进行一次前面的操作,进一步压缩路径,可以看出中间会跳过一个结点

假设第三次p成为了root的直接后继,那么parent[p]和parent[parent[p]]都是取root的值,可以退出循环了.(下一次编辑一定会加上图的2333)

这个同上一种方法不同的是可能会移动很多次结点,如果树很高的话.

但是不用先迭代来寻找root.这两种方法都会修改结点位置,但是都已经破坏了其size,如不维护size,那么再union的时候就会出问题了.

还有不明白这个find会调用多少次?如果调用多次显然新版的程序更好,

之后肯定要写每次课程的作业,

记得视频中用蒙特卡洛方法计算percolation的概率,不去实现真的存在很多问题,现在