在WQU基础上,添加一步路径压缩.
前面的优化都是在union,路径压缩是在find上面做文章.
这里的路径压缩我还没完全搞明白,之后不断再来的,不管是理解还是博文编排素材之类的.
说是加一步压缩是确实只在find里增加了一个步骤,而这里ALGS4官方又有两个版本,由于我现在没有把问题规模化,只是简单的实例化增加几个连接,
还不能很好的理解两者优劣,就都贴上来吧.
class WeightedQuickUnion():
__count = int() #number of components
__parent = list() #__parent[i] parent of i
__size = list() #size[i] number of sites in subtree rooted at i
#Each site is initially in its own component
def __init__(self, N):
self.__count = N
for i in range(0, self.__count):
self.__parent.append(i)
self.__size.append(1)
#Return the component identifier for the component containing site
def find(self, p):
self.validate(p)
root = p
#find root identifier
while (root != self.__parent[root]):
root = self.__parent[root]
#merge the component containing site
#***question:the loop ?
while (p != root):
newp = self.__parent[p]
self.__parent[p] = root
p = newp
return p def connected(self, p, q):
return self.find(p) == self.find(q)
#Merges the component containig site p with
#the component containing site q
def union(self, p, q):
rootP=self.find(p)
rootQ=self.find(q)
if (rootP == rootQ):
return
if (self.__size[rootP] < self.__size[rootQ]):
self.__parent[rootP] = rootQ
self.__size[rootQ] += self.__size[rootP]
else:
self.__parent[rootQ] = rootP
self.__size[rootP] += self.__size[rootQ]
self.__count-=1
def validate(self, p):
n = len(self.__parent)
if (p < 0 or p >= n):
raise ValueError("index", p, "is not between 0 and", (n - 1))
def traversal(self):
for i in self.__parent:
print(i, end=' ')
WQU = WeightedQuickUnion(12)
WQU.union(0, 1)
WQU.union(1, 2)
WQU.union(3, 4)
WQU.union(4, 5)
WQU.union(5, 2)
WQU.union(6, 7)
WQU.union(7, 8)
WQU.union(9, 10)
WQU.union(10, 11)
WQU.union(11, 8)
WQU.union(11, 2)
print(WQU.connected(2, 8))
WQU.traversal()
def find(self,p):
self.validate(p)
while p != self.__parent[p]:
self.__parent[p] = self.__parent[__self.parent[p]]
p = self.__parent[p]
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的概率,不去实现真的存在很多问题,现在