Quick Find (QF)

Quick Find

顾名思义就是快速查找,构建一个数组,通过下标即可迅速查找其id

Union and Find:构建一个数组,下标为索引,数组元素的值为其id,初始id和索引相同

Union(p,q):每连接一对,就遍历一遍数组,凡是和p有相同id的元素,把他们的id都改成q的id

Find(i):直接返回下标为i的id值

 1 class QuickFind():
 2     #define a arr
 3     __id=[]
 4     def __init__(self,N):
 5         for i in range(0,int(N)):
 6             #initial the id arr
 7             self.__id.append(i)
 8     def find(self,i):
 9         #quick find:use i to index it's id in the arr
10         return self.__id[i]
11     def connected(self,p,q):
12         #if they got same id,then they are connected
13         return self.__id[p]==self.__id[q]
14     #union p,q;change p's id to q 's one
15     def union(self,p,q):
16         #firstly,get the value of __id[p] and __id[q]
17         pid=self.__id[p]
18         qid=self.__id[q]
19         for i in range(0,len(self.__id)):
20             #change all element's __id to q's one
21             #which are same with previous p
22             if self.__id[i]==pid:
23                 self.__id[i]=qid
24     def traversal(self):
25         for i in self.__id:
26             print(i,end=' ')
27 UF = QuickFind(8)
28 UF.union(0,1)
29 UF.union(0,4)
30 UF.union(3,5)
31 print(UF.connected(1,4))
32 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.

原版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] ???

假设p为0,且id[0]和id[1]相等,

在循环里,假设上一次恰好修改了id[0]的值,下一次轮到id[1]和id[p]比较,

此时id[p]即id[0]已经更改为新值,不再和id[1]相等,所以要先取出它的值.

这里我起先也没看懂,等动手验证的时候就明白了