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

ಪ್ರಕಟಣೆ: ಫೆಬ್ರವರಿ 16, 2025 ರಂದು 12:30:03 ಅಪರಾಹ್ನ UTC ಸಮಯಕ್ಕೆ
ಕೊನೆಯದಾಗಿ ನವೀಕರಿಸಲಾಗಿದೆ: ಜನವರಿ 26, 2026 ರಂದು 10:37:09 ಪೂರ್ವಾಹ್ನ 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ಅನ್ನು ಸಾಮಾನ್ಯವಾಗಿ ಹೊಂದಿದ್ದಾರೆ.

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