PHPలో డిస్జోయింట్ సెట్ (యూనియన్-ఫైండ్ అల్గారిథం)

ప్రచురణ: 16 ఫిబ్రవరి, 2025 12:29:24 PM UTCకి
చివరిగా నవీకరించబడింది: 26 జనవరి, 2026 10:37:06 AM UTCకి

ఈ వ్యాసం డిస్ జాయింట్ సెట్ డేటా స్ట్రక్చర్ యొక్క PHP అమలును కలిగి ఉంది, ఇది సాధారణంగా కనీస స్పానింగ్ ట్రీ అల్గోరిథంలలో యూనియన్-ఫైండ్ కోసం ఉపయోగించబడుతుంది.

వీలైనంత ఎక్కువ మందికి అందుబాటులో ఉండేలా ఈ పేజీని ఇంగ్లీష్ నుండి యాంత్రికంగా అనువదించారు. దురదృష్టవశాత్తు, యాంత్రిక అనువాదం ఇంకా పరిపూర్ణమైన సాంకేతికత కాదు, కాబట్టి లోపాలు సంభవించవచ్చు. మీరు కోరుకుంటే, మీరు అసలు ఆంగ్ల సంస్కరణను ఇక్కడ చూడవచ్చు:

Disjoint Set (Union-Find Algorithm) in PHP

డిస్ జాయింట్ సెట్ (సాధారణంగా యూనియన్-ఫైండ్ అలియాస్ డిస్ జాయింట్ సెట్ యూనియన్ కోసం ఉపయోగించబడుతుంది) అనేది డిస్ జాయింట్ (నాన్-ఓవర్ లాపింగ్) సెట్లలో ఎలిమెంట్ల విభజనను నిర్వహించడానికి ఉపయోగించే ఒక డేటా స్ట్రక్చర్. ఇది రెండు కీలక కార్యకలాపాలకు సమర్థవంతంగా మద్దతు ఇస్తుంది:

కనుగొనండి: ఒక ఎలిమెంట్ ఏ సెట్ కు చెందినదో నిర్ణయిస్తుంది.
యూనియన్: రెండు సెట్లను కలిపి విలీనం చేస్తుంది.

ఈ నిర్మాణం ముఖ్యంగా క్రుస్కల్ యొక్క అల్గోరిథం వంటి కనీస స్పానింగ్ ట్రీ అల్గోరిథంలలో ఉపయోగపడుతుంది.

సెట్లను సమర్థవంతంగా విలీనం చేయడానికి డిస్ జాయింట్ సెట్ యొక్క దిగువ PHP అమలుపై ఆధారపడే యాదృచ్ఛిక చిట్టడవిని రూపొందించడానికి ఉపయోగించే క్రుస్కల్ యొక్క అల్గోరిథం యొక్క అమలు నాకు ఉంది. మీకు ఆసక్తి ఉంటే, మీరు దానిని ఇక్కడ చర్యలో చూడవచ్చు: క్రుస్కల్ యొక్క అల్గోరిథం మేజ్ జనరేటర్

ఏదేమైనా, ఇది డిస్ జాయింట్ సెట్ యొక్క నా 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ఉమ్మడిగా ఉంది.

వాస్తవానికి, ఇలాంటి చిన్న ఉదాహరణలో, మీరు ఈ వాస్తవాన్ని మీరే సులభంగా గుర్తించవచ్చు, కానీ ఈ అల్గోరిథం యొక్క సామర్థ్యం బిలియన్ల మంది ప్రజలు మరియు స్నేహితుల సమూహాలకు సాధ్యమయ్యే విధంగా స్కేల్ చేయడానికి అనుమతిస్తుంది.