Structure de données PHP : parcours algorithmique d'ensembles de recherche d'union, explorant la connectivité entre les ensembles

Union-find est une structure de données efficace utilisée pour gérer et trouver des relations de connectivité entre les objets. Elle prend en charge des opérations telles que la création d'ensembles, la recherche de nœuds représentatifs d'ensembles et la fusion d'ensembles. Union-find peut être utilisé dans un réseau pour déterminer quels ordinateurs peuvent communiquer entre eux. Les étapes sont les suivantes : Créez un ensemble de recherche d'union, en traitant chaque ordinateur comme un ensemble distinct, et utilisez l'opération Union de ; l'ensemble union-find pour fusionner les ensembles d'ordinateurs connectés ; pour chaque ordinateur, utilisez l'opération Find-Set pour renvoyer le nœud représentatif de l'ensemble si les nœuds représentatifs de deux ordinateurs sont identiques, ils appartiennent au même ensemble et peuvent communiquer entre eux.

Structure de données PHP : Un voyage algorithmique d'union-find, explorant la connectivité entre les ensembles

Avant-propos

Dans le domaine de l'informatique, union-find est une structure de données efficace utilisée pour la gestion et la connectivité Find entre les objets. Cet article approfondira l’algorithme de recherche d’union et illustrera son application à travers des cas pratiques.

Concept de base de union-find

Disjoint Set Union est une structure de tableau en forme d'arborescence, dans laquelle chaque nœud représente un ensemble. Cette structure prend en charge les opérations suivantes :

• Make-Set(x) : Créez un nouvel ensemble contenant uniquement l'élément x.
• Find-Set(x) : Renvoie le nœud représentatif de l'ensemble où se trouve l'élément x.
• Union(x, y) : Union des ensembles contenant les éléments x et y en un seul ensemble.

Mise en œuvre de l'algorithme

Initialiser et rechercher des ensembles :

class DisjointSetUnion {
    private $parents = [];

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

Trouver des nœuds représentatifs :

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

Fusionner des ensembles :

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

Cas pratique : Connectivité dans le réseau

Supposons que nous ayons un ensemble composé de N Un réseau d'ordinateurs, dont chacun peut être directement connecté à d'autres ordinateurs. Nous voulons déterminer quels ordinateurs peuvent communiquer entre eux, c'est-à-dire qu'ils appartiennent au même ensemble.

Nous pouvons utiliser un ensemble de recherche d'union pour résoudre ce problème :

1. Créez un ensemble de recherche d'union où chaque ordinateur est un ensemble distinct.
2. Pour chaque connexion d'ordinateur, utilisez l'opération Union pour fusionner l'ensemble des ordinateurs connectés.
3. Pour chaque ordinateur, l'opération Find-Set renvoie le nœud représentatif de l'ensemble où se trouve l'ordinateur.

Si les nœuds représentatifs de deux ordinateurs sont identiques, ils appartiennent au même ensemble et peuvent communiquer entre eux.

$numComputers = 10;
$dsu = new DisjointSetUnion($numComputers);

// 模拟计算机连接
$connections = [
    [1, 3],
    [2, 5],
    [3, 6],
    [5, 7],
    [7, 8],
];

foreach ($connections as $connection) {
    $dsu->union($connection[0], $connection[1]);
}

// 检查计算机 1 和 8 是否可以通信
$root1 = $dsu->find(1);
$root8 = $dsu->find(8);
if ($root1 == $root8) {
    echo "Computer 1 and Computer 8 can communicate.";
} else {
    echo "Computer 1 and Computer 8 cannot communicate.";
}

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!