PHP ಯಲ್ಲಿ ಡಿಸ್ಜಾಯಿಂಟ್ ಸೆಟ್ (ಯೂನಿಯನ್-ಫೈಂಡ್ ಅಲ್ಗಾರಿದಮ್)
ಪ್ರಕಟಣೆ: ಫೆಬ್ರವರಿ 16, 2025 ರಂದು 12:30:03 ಅಪರಾಹ್ನ UTC ಸಮಯಕ್ಕೆ
ಈ ಲೇಖನವು ಡಿಸ್ಜೋಯಿಂಟ್ ಸೆಟ್ ಡೇಟಾ ರಚನೆಯ ಪಿಎಚ್ಪಿ ಅನುಷ್ಠಾನವನ್ನು ಒಳಗೊಂಡಿದೆ, ಇದನ್ನು ಸಾಮಾನ್ಯವಾಗಿ ಕನಿಷ್ಠ ಸ್ಪ್ಯಾನಿಂಗ್ ಟ್ರೀ ಅಲ್ಗಾರಿದಮ್ಗಳಲ್ಲಿ ಯೂನಿಯನ್-ಫೈಂಡ್ಗಾಗಿ ಬಳಸಲಾಗುತ್ತದೆ.
Disjoint Set (Union-Find Algorithm) in 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 ಅನ್ನು ಸಮಾನವಾಗಿ ಹೊಂದಿದ್ದಾರೆ.
ಸಹಜವಾಗಿ, ಈ ರೀತಿಯ ಸಣ್ಣ ಉದಾಹರಣೆಯಲ್ಲಿ, ನೀವು ಈ ಸಂಗತಿಯನ್ನು ಸುಲಭವಾಗಿ ಗುರುತಿಸಬಹುದು, ಆದರೆ ಈ ಕ್ರಮಾವಳಿಯ ದಕ್ಷತೆಯು ಶತಕೋಟಿ ಜನರು ಮತ್ತು ಸ್ನೇಹಿತರ ಗುಂಪುಗಳಿಗೆ ಕಾರ್ಯಸಾಧ್ಯವಾಗಿ ಅಳೆಯಲು ಅನುವು ಮಾಡಿಕೊಡುತ್ತದೆ.