క్రుస్కల్ యొక్క అల్గోరిథం మేజ్ జనరేటర్

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

పరిపూర్ణ మేజ్ అంటే ఒక మేజ్, దీనిలో మేజ్‌లోని ఏ బిందువు నుండి మరొక బిందువుకు అయినా ఒకే మార్గం ఉంటుంది. అంటే మీరు వృత్తాలుగా తిరగలేరు, కానీ మీరు తరచుగా డెడ్ ఎండ్‌లను ఎదుర్కొంటారు, దీనివల్ల మీరు తిరిగి వెనక్కి వెళ్ళవలసి వస్తుంది.

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

క్రుస్కాల్ అల్గోరిథం గురించి

క్రుస్కల్ యొక్క అల్గోరిథంను అమెరికన్ గణిత శాస్త్రజ్ఞుడు, గణాంకవేత్త మరియు కంప్యూటర్ శాస్త్రవేత్త అయిన జోసెఫ్ బెర్నార్డ్ క్రుస్కల్ జూనియర్ రూపొందించారు. ఆయన మొదట 1956లో తన "ఆన్ ది షార్టెస్ట్ స్పానింగ్ సబ్‌ట్రీ ఆఫ్ ఎ గ్రాఫ్ అండ్ ది ట్రావెలింగ్ సేల్స్‌మ్యాన్ ప్రాబ్లమ్" అనే పత్రంలో అల్గోరిథంను వివరించారు.

ఈ అల్గోరిథం గ్రాఫ్ యొక్క కనిష్ట స్పానింగ్ ట్రీ (MST)ని కనుగొనడానికి రూపొందించబడింది, అన్ని శీర్షాలు చక్రాలను తప్పించుకుంటూ కనిష్ట సాధ్యమైన మొత్తం అంచు బరువుతో అనుసంధానించబడి ఉన్నాయని నిర్ధారిస్తుంది.

మేజ్ జనరేషన్ కోసం క్రుస్కల్ అల్గోరిథం ఎలా పనిచేస్తుంది

దశ 1: ప్రారంభించు

• చిట్టడవిలోని ప్రతి కణాన్ని ప్రత్యేక సమితిగా (ఒక ప్రత్యేకమైన భాగం) పరిగణించండి.
• ప్రక్కనే ఉన్న కణాల మధ్య ఉన్న అన్ని గోడలను పొటెన్షియల్ అంచులుగా జాబితా చేయండి.

దశ 2: గోడలను క్రమబద్ధీకరించండి

• గోడలను షఫుల్ చేయండి లేదా యాదృచ్ఛికంగా ఆర్డర్ చేయండి. నిజమైన క్రుస్కల్ అల్గోరిథం వలె దీన్ని అమలు చేస్తే, గోడలను యాదృచ్ఛిక క్రమంలో క్రమబద్ధీకరించండి (మేజ్ జనరేషన్‌కు బరువులు అవసరం లేదు కాబట్టి).

దశ 3: ప్రాసెస్ వాల్స్

• షఫుల్ చేయబడిన గోడల ద్వారా పునరావృతం చేయండి.
• గోడ ద్వారా విభజించబడిన రెండు కణాలు వేర్వేరు సెట్లకు చెందినవి అయితే (అంటే, అవి ఇంకా మేజ్‌లో కనెక్ట్ కాలేదు), గోడను తీసివేసి సెట్‌లను విలీనం చేయండి.
• అవి ఇప్పటికే ఒకే సెట్‌లో ఉంటే, గోడను దాటవేయండి (చక్రాలను నివారించడానికి).

దశ 4: పూర్తయ్యే వరకు కొనసాగించండి

• అన్ని కణాలు అనుసంధానించబడి, ఒకే స్పానింగ్ ట్రీ ఏర్పడే వరకు ఈ ప్రక్రియను పునరావృతం చేయండి.
• చివర్లో, ప్రతి కణం ఉచ్చులు లేదా వివిక్త విభాగాలు లేకుండా ఇతరులకు అనుసంధానించబడి ఉంటుంది.

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