黑马程序员技术交流社区

标题: 【上海校区】PHP 实现并查集 [打印本页]

作者: 不二晨 时间: 2018-11-12 09:52
标题: 【上海校区】PHP 实现并查集
今天复习了一下数据结构中的并查集，并且尝试着使用PHP来实现了一下，下面是具体的实现过程。

首先，我们需要先了解一下并查集的概念，很简单，下面是百度百科的定义，大家先看一下：并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。
根据上面的定义我们可以知道并查集是用来处理集合的，其在计算机世界中被广泛的用于处理网络连接的问题(PS:这里所说的网络连接问题并不是仅仅是计算机网络)。其至少支持两种操作---合并(Join)以及查询(Find)操作。一个集合中存在一个或者多个元素，为了描述多个元素属于同一个集合，我们一般规定，集合中的每一个元素都含有一个指针用于指向其父节点，依此类推，那么一个集合中必定含有一个根节点，该节点的指针指向自身，也就是说如果一个节点的指针指向自身，那么该节点就是该集合的根节点。
根据上面的描述，我们可以使用数组来描述并查集这种数据结构，我们可以让每一个key=>value键值对来描述集合中的每一个元素，其中key表示该元素所代表的元素，value表示该元素所指向的父节点的key。

OK,话不多说，直接看代码：
1：初始化并查集
我们使用数组的key来表示数据本身，value表示该数据所指向的父节点的key,初始状态下，每一个节点都是一个独立的集合，每一个节点的value都指向其自身。
<?phpfunction union_init(){ $array = []; for($i=0;$i<100;$i++){       $array[] = $i; } return $array;}?>复制代码2：并查集中元素的查找(也就是上面提到的Find操作)
并查集中元素的查找，就是返回该元素所处集合中的根节点的key。如果该节点的key和其value是相同的，那么该节点就是根节点。如果不是根节点，就进行迭代处理，直到找到key==value的节点(根节点)为止。
<?phpfunction union_find($item,$array){ //如果该节点的key==value,就表示该节点是根节点，直接返回key if($key == $array[$key]){       return $key; } //如果该节点不是根节点，那么其value的值就对应的其父节点的value //进行迭代处理 while($key != $array[$key]){       $key = $array[$key]; } return $key;} ?>复制代码3：将两个集合进行合并操作(也就是上面提到的Join操作)
根据传入的两个节点的key,获取两个节点各自所属集合的根节点的value，如果value相同，就表示这两个节点属于同一个集合，就不需要进行合并操作了。如果不属于同一个集合，那我们就得到了两个集合，我们分别称之为集合A/集合B，那么我们可以将集合B中的所有的节点的value修改为集合A中的根节点的value，那么集合B中的所有的节点所指向的父节点都是集合A中的根节点，这也就实现了两个结合的合并。
<?phpfunction union_join($x,$y,&$array){ if($array[$x] == $array[$y]){    return; } //获取$x,$y所对应的集合编号 $find_x = union_find($x,$array); $find_y = union_find($y,$array); //进行循环遍历，将集合编号为$find_x的所有元素编号都修改为$find_y //时间复杂度为O(N) //所以进行合并操作的时候，效率很低，需要进行优化 for($i=0;$i<count($array);$i++){    if($array[$i] == $find_x){          $array[$i] = $find_y;    } }}?>复制代码上面我们就完成了并查集的初始化，Find，Join操作。除了上面的问题，我们还可以进行功能的扩展，比如说，判断两个节点是否属于同一个集合。
4：判断两个节点是否属于同一个集合
根据传入的两个节点的key,分别使用Find操作，查询两个节点各自的根节点的value,如果得到的两个value一致，就表示这两个节点属于同一个集合，否则就不属于同一个集合。
<?php//判断两个key是否在一个集合中function is_connected($x,$y,$array){ //查找$x,$y所指向的根节点 $find_x = union_find($x,$array); $find_y = union_find($y,$array); return $find_x == $find_y;}?>复制代码OK,上面我们就完成了并查集相关的操作，下面，我们就针对Find操作以及Join操作进行优化，提高数据的处理效率。
5：对Join操作进行基本的优化
针对上面的Join操作，我们是遍历集合A或者集合B中所有的节点，然后依次修改各个节点的value值，从而实现两个集合的合并，但是正因为使用的是遍历的方式，所以这种Join方式效率很低，我们需要进行优化。我们都知道，每一个集合就是一棵树，每一个集合都有一个根节点，那么如果我们在进行Join操作的时候，不修改某个集合中所有节点的value值，而是采用将集合的根节点的value修改为另一个集合的根节点的value,那么就实现了两个集合的合并。
<?phpfunction union_join($x,$y,$array){ //查找$x,$y所指向的根节点 $find_x = union_find($x,$array); $find_y = union_find($y,$array); if($find_x == $find_y){       return; } //修改根节点的指向 $array[$x] = $find_y;}?>复制代码6：基于size对Join操作进行优化
上面的Join操作，我们是直接修改两个集合中任意一个集合的根节点的value值，提升了Join操作的效率，但是上面的修改方式还是存在问题。来看下面的情况，我们在遍历循环查询一个集合的根节点的时候，如果描述集合的元素很多，那么我们查询根节点的Find操作就会消耗很多的资源。所以在修改某个集合的根节点的时候，需要比较两个集合元素的大小，我们要对元素少的集合进行Find操作，并修改该集合的根节点的value。为了能够比较各个集合的节点数量，我们在初始化的时候，设置一个size_array,用来记录各个集合的节点数量，初始值都为1。当进行了Join操作的时候，在维护各个集合的size大小。
<?php$array = [];$size_array = [];function union_init(&$array,&$size_array){ $array = []; for($i=0;$i<100;$i++){       $array[] = $i;       $size_array[] = 1;  //初始化状态下，每棵树的元素数量都为1 }}//将两个元素进行join操作function union_join($x,$y,$array,$size_array){ //查找$x,$y所指向的根节点 $find_x = union_find($x,$array); $find_y = union_find($y,$array); if($find_x == $find_y){       return; } /*    *  原先的一棵树，结构如下：1->2->3(根节点)    *  存在另外一棵树，结构如下: 4(根节点)    *  现在有两种方式: (1): 1->2->3->4  (2): 1->2->3 4->3    * */ //修改根节点的指向 if($size_array[$x] < $size_array[$y]){       $array[$x] = $find_y;       $size_array[$x] += $size_array[$y]; }else{       $array[$y] = $find_x;       $size_array[$y] += $size_array[$x]; }}?>复制代码7：基于rank对Join操作继续优化
上面的优化方式是根据集合元素的大小作为比较对象的，但是这种比较方式仍然不能够非常准确的描述Find操作的速度。我们知道，集合就是一棵树，影响Find操作速度的是根本因素是这棵树的高度，而不是这棵树的节点数量多少，因为存在着数量多，高度低的情况。所以，进一步的优化，我们可以记录各个集合的树的高度，Find操作的时候先比较树的高度，使的Find操作执行在高度较低的树上。
<?php//初始化操作//每一个元素的key,value在初始化状态下都是相等的//value用来表示集合编号$array = [];$level_array = [];function union_init(&$array,&$size_array){ $array = []; for($i=0;$i<100;$i++){       $array[] = $i;       $level_array[] = 1;  //初始化状态下，每棵树的高度都为1 }}//将两个元素进行join操作function union_join($x,$y,$array,$level_array){ //查找$x,$y所指向的根节点 $find_x = union_find($x,$array); $find_y = union_find($y,$array); if($find_x == $find_y){       return; } //修改根节点的指向 if($level_array[$x] < $level_array[$y]){       $array[$x] = $find_y; }elseif($level_array[$x] > $level_array[$y]){       $array[$y] = $find_x; }else{       $array[$y] = $find_x;       $level_array[$y] += 1; //高度加1 }}?>复制代码8：路径压缩
ok,说完了上面针对Join操作的优化，下面说一下大名鼎鼎的路径压缩的实现。其实路径压缩的实现也是对并查集的一种优化，与上面不同的是，路径压缩是针对Find操作的优化，不是针对Join操作的优化。路径压缩的原理是在Find操作的时候，修改集合中各个节点的value,使得每一个子节点都指向该集合的根节点，而不再是子节点指向父节点，父节点再指向其父节点....,再指向根节点的方式，这样就可以大大降低树的高度。使用递归可以很方便的实现，下面看代码：
<?phpfunction union_find($key,&$array){ //如果该节点不是根节点，那么其value的值就对应的其父节点的value while($key != $array[$key]){       $array[$key] = union_find($array[$key],$array); } return $array[$key];}?>

【转载】
作者：codefly
链接：https://juejin.im/post/586f559eb123db005ba9ae5c

作者: 不二晨 时间: 2018-11-14 15:24

~(｡≧3≦)ﾉ⌒☆

作者: 梦缠绕的时候 时间: 2018-11-15 14:57

作者: 魔都黑马少年梦 时间: 2018-11-15 16:33

作者: 小影姐姐 时间: 2018-11-15 17:15
奈斯~

作者: 魔都黑马少年梦 时间: 2018-11-22 16:59

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2