数据结构-PHP 并查集(Union Find)

码农天地 - 2020-11-02 08:48:31

这篇文章主要介绍一下 并查集，并查集 支持合并（Union） 和 查询（Find）两种操作，其中 合并(Union) 表示把两个不相交的集合合并为一个集合，查询(Find) 表示查询两个元素是否在同一个集合中。

1.并查集(Union Find)示意图

并查集的特点是 儿子 节点指针指向父亲：

2.并查集(Union Find)合并

如下图所示，假设并查集中每个元素都不属于其他集合，下面给出初始指向示意图：

Tips：若要查找两个元素是否相连，可以找到两个元素分别对应的根节点元素值是否相等，若相等，则判断两个元素属于同一个集合。3.并查集(Union Find)简单的代码示例3.1 PHP代码定义

下面是一个 Union Find 类，__construct 构造函数初始化数据，如传入 size=20，那么 $parent 中会初始化 0~19 个指向自己的节点元素：

<?php
require 'UF.php';
class UnionFind implements UF
{
 private $parent = [];
 private $size;
 private $sz = []; // sz[$i] 表示以 $i 为根的集合中的元素个数
 /**
 * 初始化并查集
 * UnionFind constructor.
 * @param int $size
 */
 public function __construct(int $size)
 {
 $this->size = $size;
 for ($i = 0; $i < $size; $i++) {
 $this->parent[$i] = $i;
 $this->sz[$i] = 1;
 }
 }
 /**
 * 返回并查集大小
 * @param int $p
 * @param int $q
 * @return int
 */ public function getSize(int $p, int $q): int
 {
 return $this->size;
 }
 /**
 * 查找p对应的集合编号
 * @param int $p
 */
 public function findRoot(int $p)
 { if ($p < 0 || $p >= $this->size) {
 echo "404";
 exit; }
 while ($p != $this->parent[$p]) {
 $p = $this->parent[$p];
 }
 return $p;
 }
 /**
 * 判断两个元素是否属于同一个集合
 * @param int $p
 * @param int $q
 * @return bool
 */ public function isConnected(int $p, int $q): bool
 {
 return $this->findRoot($p) == $this->findRoot($q);
 }
 /**
 * 合并两个元素
 * @param int $p
 * @param int $q
 */
 public function unionElements(int $p, int $q): void
 {
 $pRoot = $this->findRoot($p);
 $qRoot = $this->findRoot($q);
 if ($pRoot != $qRoot) {
 if ($this->sz[$pRoot] < $this->sz[$qRoot]) { //比较两个合并元素根节点的元素个数
 $this->parent[$pRoot] = $qRoot;
 $this->sz[$qRoot] += $this->sz[$pRoot];
 } else {
 $this->parent[$qRoot] = $pRoot;
 $this->sz[$pRoot] += $this->sz[$qRoot];
 }
 } }}

Tips：代码中的合并方式是基于 根节点元素所包含元素总数 来决定合并方式的，元素少根节点会被合并到 元素多 的节点上，还可以根据 并查集的深度 来决定谁被合并。3.2 输出演示

<?php
require 'UnionFind.php';
$size = 10000;
$uf = new UnionFind($size);
$m = 500;
for ($i = 0; $i < $m; $i++) {
    $a = mt_rand(0, $size - 1);
    $b = mt_rand(0, $size - 1);
    $uf->unionElements($a, $b);
}
var_dump($uf->isConnected(50,100)); //判断 50 和 100是否相连
$size = 10000;
$uf = new UnionFind($size);
$m = 11000;
for ($i = 0; $i < $m; $i++) {
    $a = mt_rand(0, $size - 1);
    $b = mt_rand(0, $size - 1);
    $uf->unionElements($a, $b);
}
var_dump($uf->isConnected(50,100)); //判断 50 和 100是否相连

输出如下图：

代码仓库：https://gitee.com/love-for-po...

扫码关注爱因诗贤

特别申明：本文内容来源网络，版权归原作者所有，如有侵权请立即与我们联系（cy198701067573@163.com），我们将及时处理。