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

ప్రచురణ: 16 ఫిబ్రవరి, 2025 12:29:24 PM 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 ఉమ్మడిగా ఉంటుంది.

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