PHP ਵਿੱਚ ਡਿਸਜੋਇੰਟ ਸੈੱਟ (ਯੂਨੀਅਨ-ਫਾਈਂਡ ਐਲਗੋਰਿਦਮ)
ਪ੍ਰਕਾਸ਼ਿਤ: 19 ਮਾਰਚ 2025 9:36:31 ਬਾ.ਦੁ. UTC
ਇਸ ਲੇਖ ਵਿੱਚ ਡਿਸਜੋਇੰਟ ਸੈੱਟ ਡੇਟਾ ਸਟ੍ਰਕਚਰ ਦਾ PHP ਲਾਗੂਕਰਨ ਦਿਖਾਇਆ ਗਿਆ ਹੈ, ਜੋ ਆਮ ਤੌਰ 'ਤੇ ਘੱਟੋ-ਘੱਟ ਸਪੈਨਿੰਗ ਟ੍ਰੀ ਐਲਗੋਰਿਦਮ ਵਿੱਚ ਯੂਨੀਅਨ-ਫਾਈਂਡ ਲਈ ਵਰਤਿਆ ਜਾਂਦਾ ਹੈ।
Disjoint Set (Union-Find Algorithm) in PHP
ਡਿਸਜੌਇੰਟ ਸੈੱਟ (ਜੋ ਆਮ ਤੌਰ 'ਤੇ ਯੂਨੀਅਨ-ਫਾਈਂਡ ਜਾਂ ਡਿਸਜੌਇੰਟ ਸੈੱਟ ਯੂਨੀਅਨ ਲਈ ਵਰਤਿਆ ਜਾਂਦਾ ਹੈ) ਇੱਕ ਡੇਟਾ ਸਟ੍ਰਕਚਰ ਹੈ ਜੋ ਤੱਤਾਂ ਨੂੰ ਡਿਸਜੌਇੰਟ (ਗੈਰ-ਅਧਿਕਾਰਿਤ) ਸੈੱਟਾਂ ਵਿੱਚ ਵੰਡਣ ਲਈ ਵਰਤਿਆ ਜਾਂਦਾ ਹੈ। ਇਹ ਦੋ ਮੁੱਖ ਓਪਰੇਸ਼ਨਾਂ ਨੂੰ ਕੁਸ਼ਲਤਾਪੂਰਕ ਸਹਾਇਤਾ ਪ੍ਰਦਾਨ ਕਰਦਾ ਹੈ:
- ਫਾਈਂਡ: ਇਹ ਨਿਰਣੈਤ ਕਰਦਾ ਹੈ ਕਿ ਕਿਸ ਸੈੱਟ ਨਾਲ ਇੱਕ ਤੱਤ ਸੰਬੰਧਿਤ ਹੈ।
- ਯੂਨੀਅਨ: ਇਹ ਦੋ ਸੈੱਟਾਂ ਨੂੰ ਇੱਕਠਾ ਕਰਦਾ ਹੈ।
ਇਹ ਸਟ੍ਰਕਚਰ ਖਾਸ ਤੌਰ 'ਤੇ ਨਿਊਨਤਮ ਸਪੈਨਿੰਗ ਟ੍ਰੀ ਅਲਗੋਰੀਥਮਾਂ ਵਿੱਚ ਲਾਭਕਾਰੀ ਹੁੰਦਾ ਹੈ, ਜਿਵੇਂ ਕਿ ਕ੍ਰੁਸਕਲ ਦਾ ਅਲਗੋਰੀਥਮ।
ਮੇਰੇ ਕੋਲ ਕ੍ਰੁਸਕਲ ਦੇ ਅਲਗੋਰੀਥਮ ਦੀ ਇੱਕ ਅਮਲਦਾਰੀ ਹੈ ਜੋ ਰੈਂਡਮ ਮੈਜ਼ਾਂ ਬਣਾਉਣ ਲਈ ਵਰਤੀ ਜਾਂਦੀ ਹੈ ਅਤੇ ਇਹ ਡਿਸਜੌਇੰਟ ਸੈੱਟ ਦੀ ਹੇਠਾਂ ਦਿੱਤੀ PHP ਅਮਲਦਾਰੀ 'ਤੇ ਨਿਰਭਰ ਕਰਦੀ ਹੈ ਜੋ ਸੈੱਟਾਂ ਨੂੰ ਕੁਸ਼ਲਤਾਪੂਰਕ ਮਿਲਾਉਂਦੀ ਹੈ। ਜੇਕਰ ਤੁਸੀਂ ਰੁਚੀ ਰੱਖਦੇ ਹੋ, ਤਾਂ ਤੁਸੀਂ ਇਸ ਨੂੰ ਇੱਥੇ ਕਾਰਜ ਵਿੱਚ ਦੇਖ ਸਕਦੇ ਹੋ: ਕ੍ਰਸਕਲ ਦਾ ਐਲਗੋਰਿਦਮ ਮੇਜ਼ ਜਨਰੇਟਰ
ਕਿਸੇ ਵੀ ਤਰੀਕੇ ਨਾਲ, ਇਹ ਮੇਰੀ 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]++;
}
}
}
}
ਮਜ਼ੇ ਲਈ ਮੈਜ਼ਾਂ ਬਣਾਉਣ ਤੋਂ ਇਲਾਵਾ, ਡਿਸਜੌਇੰਟ ਸੈੱਟ ਡੇਟਾ ਸਟ੍ਰਕਚਰ ਨੂੰ ਨਿਸਚਿਤ ਤੌਰ 'ਤੇ ਹਕੀਕਤ ਵਾਲੀਆਂ ਸਥਿਤੀਆਂ ਵਿੱਚ ਵੀ ਵਰਤਿਆ ਜਾ ਸਕਦਾ ਹੈ।
ਮੰਨੋ, ਉਦਾਹਰਨ ਵਜੋਂ, ਇੱਕ ਸਮਾਜਿਕ ਜਾਲ ਹੈ ਜੋ ਆਪਣੇ ਉਪਭੋਗਤਾਵਾਂ ਨੂੰ ਨਵੇਂ ਦੋਸਤਾਂ ਦੀ ਸੁਝਾਅ ਦੇਣਾ ਚਾਹੁੰਦਾ ਹੈ, ਅਤੇ ਫਿਰ ਮੰਨੋ ਕਿ ਸਾਡੇ ਕੋਲ ਛੇ ਲੋਕ ਹਨ ਜਿਨ੍ਹਾਂ ਨਾਲ ਇਹ ਦੋਸਤੀਆਂ ਪਹਿਲਾਂ ਹੀ ਮੌਜੂਦ ਹਨ:
- 1 ਅਤੇ 2 ਦੋਸਤ ਹਨ।
- 2 ਅਤੇ 3 ਦੋਸਤ ਹਨ।
- 4 ਅਤੇ 5 ਦੋਸਤ ਹਨ।
- 6 ਦਾ ਕੋਈ ਦੋਸਤ ਨਹੀਂ ਹੈ।
ਇਹ ਵੱਖਰੇ ਗਰੁੱਪਾਂ 'ਤੇ ਯੂਨੀਅਨ-ਫਾਈਂਡ ਅਲਗੋਰੀਥਮ ਨੂੰ ਲਾਗੂ ਕਰਨ ਨਾਲ, ਸਾਨੂੰ ਹੇਠਾਂ ਦਿੱਤਾ ਜਾਣਾ ਚਾਹੀਦਾ ਹੈ:
- 1, 2 ਅਤੇ 3 ਇੱਕ ਗਰੁੱਪ ਵਿੱਚ।
- 4 ਅਤੇ 5 ਦੂਜੇ ਗਰੁੱਪ ਵਿੱਚ।
- 6 ਤੀਸਰੇ ਗਰੁੱਪ ਵਿੱਚ।
ਇਸ ਆਧਾਰ 'ਤੇ, ਇਹ ਸਮਝਣਾ ਤਕੜਾ ਹੋਵੇਗਾ ਕਿ 1 ਅਤੇ 3 ਨੂੰ ਦੋਸਤ ਬਣਨਾ ਚਾਹੀਦਾ ਹੈ, ਕਿਉਂਕਿ ਉਹਨਾਂ ਦੇ ਪਾਸ ਵਿਅਕਤੀ 2 ਹੈ।
ਬਿਲਕੁਲ, ਇਸ ਤਰ੍ਹਾਂ ਦੇ ਛੋਟੇ ਉਦਾਹਰਨ ਵਿੱਚ, ਤੁਸੀਂ ਆਸਾਨੀ ਨਾਲ ਇਸ ਤੱਥ ਨੂੰ ਖੁਦ ਪਤਾ ਕਰ ਸਕਦੇ ਹੋ, ਪਰ ਇਸ ਅਲਗੋਰੀਥਮ ਦੀ ਕੁਸ਼ਲਤਾ ਇਸਨੂੰ ਬਿਲੀਅਨ ਭੀੜਾਂ ਅਤੇ ਦੋਸਤ ਗਰੁੱਪਾਂ ਵਿੱਚ ਵਿਹਾਰ ਕਰਨ ਯੋਗ ਬਣਾਉਂਦੀ ਹੈ।