PHP での分離集合 (結合検索アルゴリズム)
出版された： 2025年2月16日 12:25:49 UTC
この記事では、最小全域木アルゴリズムの Union-Find でよく使用される Disjoint Set データ構造の PHP 実装について説明します。
Disjoint Set (Union-Find Algorithm) in PHP
分離セット (Union-Find または Disjoint Set Union でよく使用されます) は、要素を分離した (重複しない) セットに分割する管理に使用されるデータ構造です。次の 2 つの主要な操作を効率的にサポートします。
- 検索: 要素がどのセットに属しているかを決定します。
- 結合: 2 つのセットを結合します。
この構造は、クラスカルのアルゴリズムなどの最小全域木アルゴリズムで特に役立ちます。
私はランダム迷路を生成するために使用されるクラスカルのアルゴリズムの実装を持っています。これは、セットを効率的にマージするために、以下の PHP 実装の Disjoint Set に依存しています。興味があれば、ここで動作を確認できます:クラスカルのアルゴリズム迷路ジェネレータ
とにかく、これが Disjoint Set の PHP 実装です。
{
private $parent = [];
private $rank = [];
public function __construct($size)
{
for ($i = 0; $i < $size; $i++)
{
$this->parent[$i] = $i;
$this->rank[$i] = 0;
}
}
public function find($x)
{
if ($this->parent[$x] != $x)
{
$this->parent[$x] = $this->find($this->parent[$x]);
}
return $this->parent[$x];
}
public function union($x, $y)
{
$rootX = $this->find($x);
$rootY = $this->find($y);
if ($rootX != $rootY)
{
if ($this->rank[$rootX] > $this->rank[$rootY])
{
$this->parent[$rootY] = $rootX;
}
elseif ($this->rank[$rootX] < $this->rank[$rootY])
{
$this->parent[$rootX] = $rootY;
}
else
{
$this->parent[$rootY] = $rootX;
$this->rank[$rootX]++;
}
}
}
}
楽しみのために迷路を生成する以外にも、Disjoint Set データ構造は実際のシナリオにも使用できます。
たとえば、ユーザーに新しい友達を提案したいソーシャル ネットワークを想像してください。そして、次のような友達関係がすでに確立されている 6 人の人がいるとします。
- 1と2は友達です。
- 2と3は友達です。
- 4と5は友達です。
- 6には友達がいません。
これらの個別のグループに Union-Find アルゴリズムを適用すると、次の結果が得られます。
- 1、2、3 を 1 つのグループにまとめます。
- 2番目のグループの4と5。
- 3番目のグループには6人。
これを踏まえると、1 と 3 は共通点 2 を持っているので、友達になるべきだと提案するのは理にかなっています。
もちろん、このような小さな例では、この事実を自分で簡単に見つけることができますが、このアルゴリズムの効率性により、数十億人の人々や友人グループにまで拡張することが可能になります。