అందించిన చెట్టు లేదా గ్రాఫ్ కోసం DFSని అమలు చేసే విధానాన్ని ఈ కథనం ప్రదర్శిస్తుంది.
జావాలో గ్రాఫ్ కోసం డెప్త్ ఫస్ట్ సెర్చ్ లేదా DFSని ఎలా అమలు చేయాలి?
ప్రతి శాఖ/శీర్షాన్ని సరిగ్గా ఒకసారి సందర్శించడం ద్వారా గ్రాఫ్‌ను శోధించడానికి DFS ప్రధానంగా ఉపయోగించబడుతుంది. ఇది డెడ్‌లాక్‌లను నివారించడంలో సహాయపడే గ్రాఫ్‌లోని చక్రాలను గుర్తించగలదు లేదా గుర్తించగలదు. ఇది పజిల్స్ లేదా చిట్టడవి సమస్యలను పరిష్కరించడానికి ఉపయోగించవచ్చు. DFSని గ్రాఫ్ అల్గారిథమ్‌లు, వెబ్ క్రాలింగ్ మరియు కంపైలర్ డిజైన్‌లో అమలు చేయవచ్చు/ఉపయోగించవచ్చు.
వివరణ కోసం, డెప్త్ ఫస్ట్ సెర్చ్ లేదా DFS యొక్క దిగువ కోడ్‌ని సందర్శించండి:
తరగతి గ్రాఫ్ {
ప్రైవేట్ లింక్డ్లిస్ట్ addNode [ ] ;
ప్రైవేట్ బూలియన్ ప్రయాణించారు [ ] ;
గ్రాఫ్ ( int శీర్షాలు ) {
addNode = కొత్త లింక్డ్లిస్ట్ [ శీర్షాలు ] ;
ప్రయాణించారు = కొత్త బూలియన్ [ శీర్షాలు ] ;
కోసం ( int i = 0 ; i < శీర్షాలు ; i ++ )
addNode [ i ] = కొత్త లింక్డ్లిస్ట్ ( ) ;
}
శూన్యం addEdge ( int src, int ప్రారంభించండి ) {
addNode [ src ] . జోడించు ( ప్రారంభించండి ) ;
}
పై కోడ్ వివరణ:
- మొదట, తరగతి పేరు ' గ్రాఫ్ ” సృష్టించబడింది. దాని లోపల, ' లింక్డ్లిస్ట్ ' అనే ' addNode[] 'మరియు' అనే బూలియన్ రకం శ్రేణి ప్రయాణించారు[] ”.
- తర్వాత, “నిర్మాత కోసం శీర్షాలను పాస్ చేయండి గ్రాఫ్ ” తరగతి పారామీటర్‌గా.
- ఆ తరువాత, ' కోసం ఎంచుకున్న బ్రాంచ్ యొక్క ప్రతి నోడ్ ద్వారా తరలించడానికి లూప్ సృష్టించబడుతుంది.
- చివరికి, శూన్య రకం ' addEdge() ” శీర్షాల మధ్య అంచులను జోడించడానికి ఉపయోగించబడుతుంది. ఈ ఫంక్షన్ రెండు పారామితులను తీసుకుంటుంది: శీర్షం యొక్క మూలం ' src 'మరియు గమ్య శీర్షం' ప్రారంభించండి ”.
గ్రాఫ్‌ని సృష్టించిన తర్వాత, ఇప్పుడు పైన రూపొందించిన గ్రాఫ్‌కు డెప్త్-ఫస్ట్ సెర్చ్ లేదా DFS కోడ్‌ని జోడిద్దాం:
శూన్యం DFS ( int శీర్షము ) {
ప్రయాణించారు [ శీర్షము ] = నిజం ;
వ్యవస్థ . బయటకు . ముద్రణ ( శీర్షము + '' ) ;
ఇటరేటర్ ఇది = addNode [ శీర్షము ] . జాబితాఇటరేటర్ ( ) ;
అయితే ( ఇది. తదుపరి ఉంది ( ) ) {
int adj = ఇది. తరువాత ( ) ;
ఉంటే ( ! ప్రయాణించారు [ adj ] )
DFS ( adj ) ;
}
}
పై కోడ్ బ్లాక్‌లో:
- మొదట, ' DFS() 'ఫంక్షన్ సృష్టించబడింది, అది పొందుతోంది' శీర్షము ” పారామీటర్ గా. ఆ శీర్షం సందర్శించినట్లు గుర్తు పెట్టబడింది.
- తరువాత, సందర్శించిన శీర్షాన్ని 'ని ఉపయోగించి ప్రింట్ చేయండి out.print() ” పద్ధతి.
- అప్పుడు, '' యొక్క ఉదాహరణను సృష్టించండి ఇటరేటర్ ” అది ప్రస్తుత శీర్షం యొక్క ప్రక్కనే ఉన్న శీర్షాల మీద మళ్ళిస్తుంది.
- శీర్షాన్ని సందర్శించకపోతే, అది ఆ శీర్షాన్ని ''కి పంపుతుంది. DFS() ” ఫంక్షన్.
ఇప్పుడు, మనం ఒక 'ని సృష్టిద్దాం' ప్రధాన () ”ఫంక్షన్ భాగం గ్రాఫ్‌ని సృష్టించి, ఆపై దానికి DFSని వర్తింపజేయండి:
ప్రజా స్థిరమైన శూన్యం ప్రధాన ( స్ట్రింగ్ ఆర్గ్స్ [ ] ) {
గ్రాఫ్ k = కొత్త గ్రాఫ్ ( 4 ) ;
కె. addEdge ( 0 , 1 ) ;
కె. addEdge ( 1 , 2 ) ;
కె. addEdge ( 2 , 3 ) ;
కె. addEdge ( 3 , 3 ) ;
వ్యవస్థ . బయటకు . println ( 'తదుపరిది డెప్త్ ఫస్ట్ ట్రావర్సల్' ) ;
కె. DFS ( 1 ) ;
}
}
పై కోడ్ యొక్క వివరణ:
- మొదట, ఒక వస్తువును సృష్టించండి ' కె ' కొరకు ' గ్రాఫ్() ” పద్ధతి.
- తరువాత, ' addEdge() 'పద్ధతి బహుళ శీర్షాల మధ్య అంచులను జోడించడానికి ఉపయోగించబడుతుంది. ఇది మా గ్రాఫ్ యొక్క నిర్మాణాన్ని సృష్టిస్తుంది.
- చివరికి, ఏదైనా శీర్ష విలువను ఇప్పటికే సృష్టించిన దానికి ఆర్గ్యుమెంట్‌గా పాస్ చేయండి DFS() ” ఫంక్షన్. రూట్ నుండి ఆ శీర్ష మార్గాన్ని కనుగొనడానికి, డెప్త్-ఫస్ట్ సెర్చ్ అల్గారిథమ్‌ని ఉపయోగించండి. ఉదాహరణకు, విలువ ' 1 ''కి పంపబడుతుంది DFS() ” ఫంక్షన్.
సంకలన దశ ముగిసిన తర్వాత:
డెప్త్-ఫస్ట్ శోధన విజయవంతంగా అమలు చేయబడిందని అవుట్‌పుట్ చూపిస్తుంది.
ముగింపు
డెప్త్ ఫస్ట్ సెర్చ్ అనేది గ్రాఫ్ ట్రావర్సల్ అల్గోరిథం, ఇది చిన్నదైన మార్గాన్ని కనుగొనడం, విస్తరించిన చెట్లను మరియు కనెక్టివిటీ విశ్లేషణ వంటి అనేక గ్రాఫ్ అల్గారిథమ్‌లకు ఆధారం. ఇది రూట్ నోడ్ నుండి మొదలవుతుంది మరియు బ్యాక్‌ట్రాకింగ్ చేయడానికి ముందు ఆ శాఖ యొక్క లీవ్ నోడ్ లేదా చివరి నోడ్ వరకు వీలైనంత లోతుగా కదులుతుంది. ఈ కథనం జావాలో గ్రాఫ్ కోసం డెప్త్-ఫస్ట్ సెర్చ్ లేదా DFSని అమలు చేసే విధానాన్ని ప్రదర్శించింది.