PHP-Datenstruktur: Algorithmische Reise zur Vereinigungsfindung von Mengen, Untersuchung der Konnektivität zwischen Mengen

Union-find ist eine effiziente Datenstruktur, die zum Verwalten und Suchen von Konnektivitätsbeziehungen zwischen Objekten verwendet wird. Sie unterstützt Vorgänge wie das Erstellen von Mengen, das Suchen von Mengenrepräsentantenknoten und das Zusammenführen von Mengen. Union-Find kann in einem Netzwerk verwendet werden, um zu bestimmen, welche Computer miteinander kommunizieren können. Die Schritte sind wie folgt: Erstellen Sie einen Union-Find-Satz, behandeln Sie jeden Computer als einen separaten Satz und verwenden Sie die Union-Operation von Verwenden Sie für jeden Computer die Operation Find-Set, um den repräsentativen Knoten der Gruppe zurückzugeben. Wenn die repräsentativen Knoten zweier Computer gleich sind, gehören sie zu derselben Menge und können miteinander kommunizieren.

PHP-Datenstruktur: Eine algorithmische Reise von Union-Find, die die Konnektivität zwischen Mengen untersucht

Vorwort

Im Bereich der Informatik ist Union-Find eine effiziente Datenstruktur, die für die Verwaltung und Find-Konnektivität verwendet wird zwischen Objekten. Dieser Artikel befasst sich mit dem Algorithmus der Gewerkschaftssuche und veranschaulicht seine Anwendung anhand praktischer Fälle.

Grundkonzept von Union-Find

Disjoint Set Union ist eine baumförmige Array-Struktur, in der jeder Knoten eine Menge darstellt. Diese Struktur unterstützt die folgenden Operationen:

• Make-Set(x): Erstellen Sie einen neuen Satz, der nur Element x enthält.
• Find-Set(x): Gibt den repräsentativen Knoten der Menge zurück, in dem sich Element x befindet.
• Union(x, y): Vereinigung der Mengen, die die Elemente x und y enthalten, zu einer Menge.

Algorithmusimplementierung

Sets initialisieren und nachschlagen:

class DisjointSetUnion {
    private $parents = [];

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

Repräsentative Knoten finden:

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

Sets zusammenführen:

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

Praxisfall: Konnektivität im. Netzwerk

Angenommen, wir haben ein Set bestehend aus von N Ein Netzwerk von Computern, von denen jeder direkt mit einigen anderen Computern verbunden sein kann. Wir wollen feststellen, welche Computer miteinander kommunizieren können, also zum selben Set gehören.

Wir können ein Union-Find-Set verwenden, um dieses Problem zu lösen:

1. Erstellen Sie ein Union-Find-Set, bei dem jeder Computer ein separates Set ist.
2. Verwenden Sie für jede Computerverbindung die Union-Operation, um die Gruppe der verbundenen Computer zusammenzuführen.
3. Für jeden Computer gibt die Find-Set-Operation den repräsentativen Knoten der Menge zurück, in dem sich der Computer befindet.

Wenn die repräsentativen Knoten zweier Computer gleich sind, gehören sie zum selben Satz und können miteinander kommunizieren.

$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.";
}

Das obige ist der detaillierte Inhalt vonPHP-Datenstruktur: Algorithmische Reise zur Vereinigungsfindung von Mengen, Untersuchung der Konnektivität zwischen Mengen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!