Miklix

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

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

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


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

Disjoint Set (Union-Find Algorithm) in PHP

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

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

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

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

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

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

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

ಬ್ಲೂಸ್ಕೈನಲ್ಲಿ ಹಂಚಿಕೊಳ್ಳಿಫೇಸ್‌ಬುಕ್‌ನಲ್ಲಿ ಹಂಚಿಕೊಳ್ಳಿLinkedIn ನಲ್ಲಿ ಹಂಚಿಕೊಳ್ಳಿTumblr ನಲ್ಲಿ ಹಂಚಿಕೊಳ್ಳಿX ನಲ್ಲಿ ಹಂಚಿಕೊಳ್ಳಿLinkedIn ನಲ್ಲಿ ಹಂಚಿಕೊಳ್ಳಿPinterest ನಲ್ಲಿ ಪಿನ್ ಮಾಡಿ

Mikkel Bang Christensen

ಲೇಖಕರ ಬಗ್ಗೆ

Mikkel Bang Christensen
ಮಿಕೆಲ್ miklix.com ನ ಸೃಷ್ಟಿಕರ್ತ ಮತ್ತು ಮಾಲೀಕರು. ಅವರು ವೃತ್ತಿಪರ ಕಂಪ್ಯೂಟರ್ ಪ್ರೋಗ್ರಾಮರ್/ಸಾಫ್ಟ್‌ವೇರ್ ಡೆವಲಪರ್ ಆಗಿ 20 ವರ್ಷಗಳಿಗೂ ಹೆಚ್ಚು ಅನುಭವ ಹೊಂದಿದ್ದಾರೆ ಮತ್ತು ಪ್ರಸ್ತುತ ದೊಡ್ಡ ಯುರೋಪಿಯನ್ ಐಟಿ ಕಾರ್ಪೊರೇಷನ್‌ನಲ್ಲಿ ಪೂರ್ಣ ಸಮಯದ ಉದ್ಯೋಗಿಯಾಗಿದ್ದಾರೆ. ಬ್ಲಾಗಿಂಗ್ ಮಾಡದಿರುವಾಗ, ಅವರು ತಮ್ಮ ಬಿಡುವಿನ ವೇಳೆಯನ್ನು ವ್ಯಾಪಕವಾದ ಆಸಕ್ತಿಗಳು, ಹವ್ಯಾಸಗಳು ಮತ್ತು ಚಟುವಟಿಕೆಗಳಲ್ಲಿ ಕಳೆಯುತ್ತಾರೆ, ಇದು ಸ್ವಲ್ಪ ಮಟ್ಟಿಗೆ ಈ ವೆಬ್‌ಸೈಟ್‌ನಲ್ಲಿ ಒಳಗೊಂಡಿರುವ ವಿವಿಧ ವಿಷಯಗಳಲ್ಲಿ ಪ್ರತಿಫಲಿಸಬಹುದು.