查找算法python,Python语言提供的查找算法包含下列哪些算法
并行集合，在一些n元素集合的应用问题中，我们通常是让每个元素在开始的时候形成一个单一的元素集合，然后把属于同一组的元素集合按照一定的顺序进行合并，期间我们要反复找出一个元素在哪个集合中。
一、并查集两个操作：
1.合并两组。
2.询问两个数是否在一个集合中。
二、基本原理：每个集合用一棵树表示。树的根的个数就是整个集合的个数。每个节点存储其父节点，p[x]表示x的父节点。
在这里，我们将每个集合的编号存储在根节点中，也称为yhdbks节点。很容易知道，开始时，每个元素都在一个集合中，此时每个元素都满足p[x]=x，但经过连续归并，只有每棵树的yhdbks节点的p[x]等于x(即根)。
上图中绿色字体是每个节点的父节点。
三、明确3个问题：
1.如何判断树的根：if(p[x]==x)
2.如何求x: while的集合数(p[x]！=x)x=p[x]；
沿着x的父节点向上，直到到达yhdbks节点，其中x被分配了yhdbks节点的编号，即集合的编号。
图中红色路径是求节点4的yhdbks节点，即求元素4的集合数。
3.如何合并两个集合：p[x]=y
即集合x的根节点直接连接到集合y的根节点，即集合x的根节点变成y，即p[x]=y(或者py可以连接到px，即p[y]=x)
四、路径压缩优化
还有一点就是在搜索一个节点的yhdbks节点时有一个路径压缩优化的编号(搜索集编号)，即在搜索X节点的yhdbks节点时，这条路径上所有经过的节点都指向yhdbks节点。
例如下图：搜索完节点6的yhdbks节点后，将此路径上的所有节点(节点2和4)直接指向yhdbks节点。这样，如果需要再次查找节点2和节点4的yhdbks节点，可以快速找到五、重点代码实现。
用递归实现yhdbks节点的路径压缩，整个代码的重点在find函数上。
Int find(int x) //返回x {if(p[x]！=x)p[x]=find(p[x])；//p[x]！=x，表示不是yhdbks节点返回p[x]；}如果你不明白这一点，看到别人拆这个模板就更好理解了。
int find (int x){ if(p[x]！=x){ int t=find(p[x])；//找到yhdbks的节点p[x]=t；//路径压缩}返回p[x]；}六、例题
AcWing 836。合并集题目描述
有n个数，从1到n编号，一开始，每个数都在一个集合里。
现在有m个操作要执行。有两种类型的操作：
“M a b”，它将两个数A和b的集合组合在一起，如果两个数已经在同一个集合中，则忽略此操作；
“Q a b”，问编号为A和B的两个数是否在同一个集合中；输入格式
在第一行输入整数n和m。
接下来的M行，每一行包含一个操作指令，是“M a b”或“Q a b”中的一个。
输出格式
对于每个查询指令“Q a b”，应该输出一个结果。如果A和B在同一个集合中，则输出“是”，否则输出“否”。
每个结果占一行。
数据范围
1n，m105
# includeiostreamusing命名空间stdconst int N=1e5 10int n，m；int p[N]；//p[N]表示每个节点的父节点intfind (intx)。//yhdbks节点路径优化x {if(p[x]！=x)p[x]=find(p[x])；return p[x]；} int main(){ cinnm；for(int I=1；I=n；I)p[I]=I；//开始时每个元素都在一个集合中，此时p[x]=x while(m-){所有元素的charopint a，b；cin执行部分a b；if(op== M )p[find(a)]=find(b)；//merge else//query { if(find(a)==find(b))cout yes endl；else cout No endl} }} AcWing 837。连接块中的点数题目描述
给定一个有n个点(从1到n编号)的无向图，图的开头没有边。
现在，有三个操作要执行：
“C a b”，连接A点和B点之间的一条边，A和B可能相等；
“Q1 a b”，询问A点和B点是否在同一个连通块中。a和B可以相等；
“Q2 a”，求A点所在的连通块中的点数；输入格式
在第一行输入整数n和m。
接下来的m行，每一行包含一个操作指令，是“C a b”、“Q1 a b”或“Q2 a”中的一个。
输出格式
对于每个查询指令“Q1 a b”，如果A和B在同一个连通块中，则输出“是”，否则输出“否”。
对于每个查询指令“Q2 a”，输出一个整数来表示点A所在的连通块中的点数。
每个结果占一行。
数据范围
1n，m105
# includeiostreamusing命名空间stdconst int N=1e5 10int n，m；int p[N]，size[N]；//p[N]存储每个节点的父节点，size[N]存储每个集合中的元素个数。//只有yhdbks节点的大小才有意义。int find(int x) //返回x {if(p[x]！=x)p[x]=find(p[x])；//p[x]！=x表示不是yhdbks节点的返回p[x];} int main(){ cinnm；for(int I=1；I=n；I){ p[I]=I；//开始时，每个元素都在一个集合中，此时，所有元素的p[x]=x size[I]=1；//一开始每个集合只有一个元素} while(m-){ charop[5]；int a，b；cinopif(op[0]== C )//Merge { cinab；if(find(a)==find(b))继续；//a和B已经在一个集合size[find(B)]=size[find(a)]；//合并后，b(size)=b(size)a(size)p[find(a)]=find(b)；}else if(op[1]==1) //查询是否在同一个集合{ cinabif(find(a)==find(b))cout yes endl；else cout No endl}else //查询集合{ cinacoutsize[find(a)]endl；} }返回0；}还有一道关于并查集的题：L2-010排座位(25分)并检查设置
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。