PHP データ構造: セット間の結合性を探索する、集合を見つけるアルゴリズムの旅

Union-find は、オブジェクト間の接続関係を管理および検索するために使用される効率的なデータ構造であり、セットの作成、セットの代表ノードの検索、セットのマージなどの操作をサポートします。 Union-find をネットワーク内で使用すると、どのコンピュータが相互に通信できるかを判断できます。手順は次のとおりです。 各コンピュータを別個のコンピュータ接続として扱い、Union-find セットを作成します。接続されたコンピューターのセットをマージするための Union-Find セット。コンピューターごとに、Find-Set 操作を使用してセットの代表ノードを返します。2 つのコンピューターの代表ノードが同じである場合、それらは同じセットに属します。お互いに通信します。

PHP データ構造: Union-find のアルゴリズムの旅、セット間の接続性の探索

前書き

コンピューター サイエンスの分野では、union-find は管理と接続性の検索に使用される効率的なデータ構造です。オブジェクトの間。この記事では、和集合検索のアルゴリズムを詳しく掘り下げ、実際のケースを通じてその応用例を説明します。

union-findの基本概念

Disjoint Set Unionはツリー状の配列構造であり、各ノードが集合を表します。この構造は次の操作をサポートします:

• Make-Set(x): 要素 x のみを含む新しいセットを作成します。
• Find-Set(x): 要素 x が位置する集合の代表ノードを返します。
• Union(x, y): 要素 x と y を含むセットを 1 つのセットに結合します。

アルゴリズムの実装

セットの初期化と検索:

class DisjointSetUnion {
    private $parents = [];

    public function __construct($numElements) {
        for ($i = 0; $i < $numElements; $i++) {
            $this->parents[$i] = $i;
        }
    }
}

代表ノードの検索:

public function find($x) {
    if ($x != $this->parents[$x]) {
        $this->parents[$x] = $this->find($this->parents[$x]);
    }
    return $this->parents[$x];
}

セットのマージ:

public function union($x, $y) {
    $xRoot = $this->find($x);
    $yRoot = $this->find($y);
    $this->parents[$yRoot] = $xRoot;
}

実際のケース: ネットワーク内の接続

からなるセットがありますof N コンピュータのネットワーク。各コンピュータは他のコンピュータに直接接続できます。どのコンピュータが相互に通信できるか、つまり同じセットに属しているコンピュータかを判断したいと考えています。

この問題を解決するには、union-find セットを使用できます。

1. 各コンピューターが別個のセットである Union-find セットを作成します。
2. コンピューター接続ごとに、ユニオン操作を使用して、接続されているコンピューターのセットを結合します。
3. 各コンピューターについて、Find-Set 操作は、コンピューターが配置されているセットの代表ノードを返します。

2 台のコンピュータの代表ノードが同じであれば、それらは同じセットに属し、相互に通信できます。

りー

以上がPHP データ構造: セット間の結合性を探索する、集合を見つけるアルゴリズムの旅の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。