PHP ಯಲ್ಲಿ ಡಿಸ್ಜಾಯಿಂಟ್ ಸೆಟ್ (ಯೂನಿಯನ್-ಫೈಂಡ್ ಅಲ್ಗಾರಿದಮ್)

ಪ್ರಕಟಣೆ: ಫೆಬ್ರವರಿ 16, 2025 ರಂದು 12:30:03 ಅಪರಾಹ್ನ UTC ಸಮಯಕ್ಕೆ

ಈ ಲೇಖನವು ಡಿಸ್ಜೋಯಿಂಟ್ ಸೆಟ್ ಡೇಟಾ ರಚನೆಯ ಪಿಎಚ್ಪಿ ಅನುಷ್ಠಾನವನ್ನು ಒಳಗೊಂಡಿದೆ, ಇದನ್ನು ಸಾಮಾನ್ಯವಾಗಿ ಕನಿಷ್ಠ ಸ್ಪ್ಯಾನಿಂಗ್ ಟ್ರೀ ಅಲ್ಗಾರಿದಮ್ಗಳಲ್ಲಿ ಯೂನಿಯನ್-ಫೈಂಡ್ಗಾಗಿ ಬಳಸಲಾಗುತ್ತದೆ.

ಸಾಧ್ಯವಾದಷ್ಟು ಜನರಿಗೆ ಲಭ್ಯವಾಗುವಂತೆ ಮಾಡಲು ಈ ಪುಟವನ್ನು ಇಂಗ್ಲಿಷ್‌ನಿಂದ ಯಂತ್ರಭಾಷಾಂತರಿಸಲಾಗಿದೆ. ದುರದೃಷ್ಟವಶಾತ್, ಯಂತ್ರಭಾಷಾಂತರವು ಇನ್ನೂ ಪರಿಪೂರ್ಣ ತಂತ್ರಜ್ಞಾನವಾಗಿಲ್ಲ, ಆದ್ದರಿಂದ ದೋಷಗಳು ಸಂಭವಿಸಬಹುದು. ನೀವು ಬಯಸಿದರೆ, ನೀವು ಮೂಲ ಇಂಗ್ಲಿಷ್ ಆವೃತ್ತಿಯನ್ನು ಇಲ್ಲಿ ವೀಕ್ಷಿಸಬಹುದು:

Disjoint Set (Union-Find Algorithm) in PHP

ಡಿಸ್ಜೋಯಿಂಟ್ ಸೆಟ್ (ಸಾಮಾನ್ಯವಾಗಿ ಯೂನಿಯನ್-ಫೈಂಡ್ ಎ.ಕೆ.ಎ. ಡಿಸ್ಜೋಯಿಂಟ್ ಸೆಟ್ ಯೂನಿಯನ್ಗೆ ಬಳಸಲಾಗುತ್ತದೆ) ಎಂಬುದು ಮೂಲವಸ್ತುಗಳ ವಿಭಜನೆಯನ್ನು ವಿಭಜಿತ (ಅತಿಕ್ರಮಣವಲ್ಲದ) ಸೆಟ್ಗಳಾಗಿ ನಿರ್ವಹಿಸಲು ಬಳಸುವ ದತ್ತಾಂಶ ರಚನೆಯಾಗಿದೆ. ಇದು ಎರಡು ಪ್ರಮುಖ ಕಾರ್ಯಾಚರಣೆಗಳನ್ನು ಪರಿಣಾಮಕಾರಿಯಾಗಿ ಬೆಂಬಲಿಸುತ್ತದೆ:

ಹುಡುಕಿ: ಒಂದು ಮೂಲವಸ್ತುವು ಯಾವ ಸೆಟ್ ಗೆ ಸೇರಿದೆ ಎಂಬುದನ್ನು ನಿರ್ಧರಿಸುತ್ತದೆ.
ಯೂನಿಯನ್: ಎರಡು ಸೆಟ್ ಗಳನ್ನು ಒಟ್ಟಿಗೆ ವಿಲೀನಗೊಳಿಸುತ್ತದೆ.

ಕ್ರುಸ್ಕಲ್ ನ ಕ್ರಮಾವಳಿಯಂತಹ ಕನಿಷ್ಠ ಸ್ಪ್ಯಾನಿಂಗ್ ಟ್ರೀ ಅಲ್ಗಾರಿದಮ್ ಗಳಲ್ಲಿ ಈ ರಚನೆಯು ವಿಶೇಷವಾಗಿ ಉಪಯುಕ್ತವಾಗಿದೆ.

ಸೆಟ್ ಗಳನ್ನು ಪರಿಣಾಮಕಾರಿಯಾಗಿ ವಿಲೀನಗೊಳಿಸಲು ಡಿಸ್ಜೋಯಿಂಟ್ ಸೆಟ್ ನ ಕೆಳಗಿನ ಪಿಎಚ್ ಪಿ ಅನುಷ್ಠಾನವನ್ನು ಅವಲಂಬಿಸಿರುವ ಯಾದೃಚ್ಛಿಕ ಮೇಜ್ ಗಳನ್ನು ರಚಿಸಲು ಬಳಸುವ ಕ್ರುಸ್ಕಲ್ ನ ಕ್ರಮಾವಳಿಯ ಅನುಷ್ಠಾನವನ್ನು ನಾನು ಹೊಂದಿದ್ದೇನೆ. ನೀವು ಆಸಕ್ತಿ ಹೊಂದಿದ್ದರೆ, ನೀವು ಅದನ್ನು ಇಲ್ಲಿ ಕ್ರಿಯೆಯಲ್ಲಿ ನೋಡಬಹುದು: ಕ್ರುಸ್ಕಲ್ ನ ಅಲ್ಗಾರಿದಮ್ ಮೇಜ್ ಜನರೇಟರ್

ಹೇಗಾದರೂ, ಇದು ಡಿಸ್ಜೋಯಿಂಟ್ ಸೆಟ್ನ ನನ್ನ ಪಿಎಚ್ಪಿ ಅನುಷ್ಠಾನವಾಗಿದೆ:

class DisjointSet 
{
    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 ಅನ್ನು ಸಮಾನವಾಗಿ ಹೊಂದಿದ್ದಾರೆ.

ಸಹಜವಾಗಿ, ಈ ರೀತಿಯ ಸಣ್ಣ ಉದಾಹರಣೆಯಲ್ಲಿ, ನೀವು ಈ ಸಂಗತಿಯನ್ನು ಸುಲಭವಾಗಿ ಗುರುತಿಸಬಹುದು, ಆದರೆ ಈ ಕ್ರಮಾವಳಿಯ ದಕ್ಷತೆಯು ಶತಕೋಟಿ ಜನರು ಮತ್ತು ಸ್ನೇಹಿತರ ಗುಂಪುಗಳಿಗೆ ಕಾರ್ಯಸಾಧ್ಯವಾಗಿ ಅಳೆಯಲು ಅನುವು ಮಾಡಿಕೊಡುತ್ತದೆ.