Quick Union
quick union就是快速连接
和quick find相同,也是构建一个数组id[],不过存的值换一种理解:
每个数组内的元素看做一个结点,结点内的值即id[i]看做i的前驱结点.
初始化时将每个元素的前驱结点赋值为其下标,即id[]={0,1,2,3...,N-1}.
认为前驱结点和本身相同的结点为根结点,所以以上初始化就是将每个元素的根节点初始化为自己
对于某个结点,迭代的寻找其前驱结点,最终当某一结点找到的前驱结点和自身相同时,该结点即为以根结点,
某对结点,若他们的根相同,即认为相连(connnected)
class QuickUnion():
#pre define a array
__id = []
def __init__(self,N):
for i in range(0,N):
#initial the list:
#the __id[i] save i's root
#so, default to itself
self.__id.append(i)
#locate i's root
def root(self,i):
#locate from bottom to top
while i != self.__id[i]:
i = self.__id[i]
return i
def connected(self,p,q):
return self.root(p) == self.root(q)
def union(self,p,q):
i = self.root(p)
j = self.root(q)
self.__id[i] = j
def traversal(self):
for i in self.__id:
print(i,end=' ') Qu = QuickUnion(8)
Qu.union(0,1)
Qu.union(2,1)
Qu.union(2,4)
Qu.union(3,7)
print(Qu.connected(0,4))
Qu.traversal()
实例连接了0-1-2-4 3-7,并调用connected()方法验证0-4是否连接,
最后遍历一遍,查询所有元素的前驱结点
以下为输出:
True
1 4 1 7 4 5 6 7
根据输出可汇出树状图表示:
4 5 6 7
| |
1 3
/ \
0 2