Quick Find
顾名思义就是快速查找,构建一个数组,通过下标即可迅速查找其id
Union and Find:构建一个数组,下标为索引,数组元素的值为其id,初始id和索引相同
Union(p,q):每连接一对,就遍历一遍数组,凡是和p有相同id的元素,把他们的id都改成q的id
Find(i):直接返回下标为i的id值
class QuickFind():
#define a arr
__id=[]
def __init__(self,N):
for i in range(0,int(N)):
#initial the id arr
self.__id.append(i)
def find(self,i):
#quick find:use i to index it's id in the arr
return self.__id[i]
def connected(self,p,q):
#if they got same id,then they are connected
return self.__id[p]==self.__id[q]
#union p,q;change p's id to q 's one
def union(self,p,q):
#firstly,get the value of __id[p] and __id[q]
pid=self.__id[p]
qid=self.__id[q]
for i in range(0,len(self.__id)):
#change all element's __id to q's one
#which are same with previous p
if self.__id[i]==pid:
self.__id[i]=qid
def traversal(self):
for i in self.__id:
print(i,end=' ')
UF = QuickFind(8)
UF.union(0,1)
UF.union(0,4)
UF.union(3,5)
print(UF.connected(1,4))
UF.traversal()
实例中构建了长度为8的数组,依次连接了0-1,0-4,3-5
然后检查1-4是否连接,并遍历了数组值
下面是输出:
True
4 4 2 5 4 5 6 7
可以看见0-1-4具有相同id且是4的id, 3-5同为5的id.
Q:
原版java实现中有这样一句:
The mistake we might make is to put ID of P here rather than first picking out, that value. And you can think about the implications of that.
就是针对
int pid=id[p];
这一句,为什么一定要先取出他的值,而不是直接一直用id[p] ???
A:
假设p为0,且id[0]和id[1]相等,
在循环里,假设上一次恰好修改了id[0]的值,下一次轮到id[1]和id[p]比较,
此时id[p]即id[0]已经更改为新值,不再和id[1]相等,所以要先取出它的值.
这里我起先也没看懂,等动手验证的时候就明白了