PHP data structure: Algorithmic journey of union-finding sets, exploring the connectivity between sets

Union-find is an efficient data structure used to manage and find connectivity relationships between objects. It supports operations such as creating sets, finding set representative nodes, and merging sets. Union-find can be used in a network to determine which computers can communicate with each other. The steps are as follows: Create a union-find set, treating each computer as a separate set; simulate computer connections, and use the Union operation of the union-find set to merge the sets of connected computers; for For each computer, use the Find-Set operation to return the set representative node; if the representative nodes of two computers are the same, they belong to the same set and can communicate with each other.

PHP Data Structure: Algorithmic Journey of Union-Find Sets, Exploring the Connectivity between Sets

Preface

In the field of computer science, union search is an efficient data structure used to manage and find connectivity relationships between objects. This article will delve into the algorithm of union search and illustrate its application through practical cases.

Basic concept of union-find

Disjoint Set Union is a tree-shaped array structure in which each node represents a set. This structure supports the following operations:

• Make-Set(x): Creates a new set containing only element x.
• Find-Set(x): Returns the representative node of the set where element x is located.
• Union(x, y): Combine the sets containing elements x and y into one set.

Algorithm implementation

Initialization and search set:

class DisjointSetUnion {
    private $parents = [];

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

Find representative node:

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

Merge set:

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

Practical case: Connectivity in the network

Suppose we have a network composed of N computers, and each computer can Connect directly to some other computer. We want to determine which computers can communicate with each other, i.e. they belong to the same set.

We can use a union-find set to solve this problem:

1. Create a union-find set where each computer is a separate set.
2. For each computer connection, use the Union operation to merge the set of connected computers.
3. For each computer, the Find-Set operation returns the representative node of the set where the computer is located.

If the representative nodes of two computers are the same, they belong to the same set and can communicate with each other.

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

The above is the detailed content of PHP data structure: Algorithmic journey of union-finding sets, exploring the connectivity between sets. For more information, please follow other related articles on the PHP Chinese website!