यह आलेख किसी दिए गए ट्री या ग्राफ़ के लिए DFS को लागू करने की प्रक्रिया को प्रदर्शित करता है।
जावा में ग्राफ के लिए गहराई पहली खोज या डीएफएस कैसे कार्यान्वित करें?
डीएफएस का उपयोग मुख्य रूप से प्रत्येक शाखा/शीर्ष पर ठीक एक बार जाकर ग्राफ खोजने के लिए किया जाता है। यह ग्राफ में चक्रों का पता लगा सकता है या उनकी पहचान कर सकता है जो गतिरोध को रोकने में मदद करता है। इसका उपयोग पहेली या भूलभुलैया की समस्याओं को हल करने के लिए किया जा सकता है। डीएफएस को ग्राफ एल्गोरिदम, वेब क्रॉलिंग और कंपाइलर डिजाइन में लागू/उपयोग किया जा सकता है।
स्पष्टीकरण के लिए, डेप्थ फर्स्ट सर्च या डीएफएस के नीचे दिए गए कोड पर जाएं:
कक्षा ग्राफ़ {
निजी लिंक्ड सूची ऐडनोड [ ] ;
निजी बूलियन चल [ ] ;
ग्राफ़ ( int यहाँ कोने ) {
ऐडनोड = नया लिंक्ड सूची [ कोने ] ;
चल = नया बूलियन [ कोने ] ;
के लिए ( int यहाँ मैं = 0 ; मैं < कोने ; मैं ++ )
ऐडनोड [ मैं ] = नया लिंक्ड सूची ( ) ;
}
खालीपन addEdge ( int यहाँ स्रोत, int यहाँ शुरू ) {
ऐडनोड [ स्रोत ] . जोड़ना ( शुरू ) ;
}
उपरोक्त कोड का विवरण:
- सबसे पहले, वर्ग नाम ' ग्राफ़ ' बनाया गया है। इसके अंदर, एक 'घोषित करता है लिंक्ड सूची 'नामित' एडनोड [] 'और एक बूलियन प्रकार की सरणी जिसका नाम' ट्रैवर्स किया गया [] ”।
- इसके बाद, 'के कंस्ट्रक्टर के लिए वर्टिकल पास करें' ग्राफ़ 'एक पैरामीटर के रूप में वर्ग।
- उसके बाद, ' के लिए 'लूप चयनित शाखा के प्रत्येक नोड के माध्यम से जाने के लिए बनाया गया है।
- अंत में, शून्य प्रकार ' ऐड एज () ” का उपयोग शीर्षों के बीच किनारों को जोड़ने के लिए किया जाता है। यह फ़ंक्शन दो पैरामीटर लेता है: वर्टेक्स का स्रोत ' स्रोत 'और गंतव्य शीर्ष' शुरू ”।
एक ग्राफ के निर्माण के बाद, अब हम उपरोक्त बनाए गए ग्राफ के लिए डेप्थ-फर्स्ट सर्च या डीएफएस का कोड जोड़ते हैं:
खालीपन डीएफएस ( int यहाँ शिखर ) {
चल [ शिखर ] = सत्य ;
प्रणाली . बाहर . छपाई ( शिखर + '' ) ;
इटरेटर यह = ऐडनोड [ शिखर ] . listIterator ( ) ;
जबकि ( यह। अगला है ( ) ) {
int यहाँ समायो = यह। अगला ( ) ;
अगर ( ! चल [ समायो ] )
डीएफएस ( समायो ) ;
}
}
उपरोक्त कोड ब्लॉक में:
- पहले ' डीएफएस () 'फ़ंक्शन बनाया गया है जो' प्राप्त कर रहा है शिखर 'एक पैरामीटर के रूप में। उस शीर्ष को विज़िट के रूप में चिह्नित किया गया है।
- अगला, 'का उपयोग करके विज़िट किए गए शीर्ष को प्रिंट करें' आउट.प्रिंट () ' तरीका।
- फिर, 'का एक उदाहरण बनाएँ इटरेटर ' जो वर्तमान शीर्ष के निकटवर्ती शीर्षों पर पुनरावृति करता है।
- यदि शीर्ष का दौरा नहीं किया जाता है, तो यह उस शीर्ष को ' डीएफएस () ' समारोह।
अब, हम एक 'बनाते हैं' मुख्य() ” ग्राफ़ बनाने के लिए कार्य करें और फिर उस पर DFS लागू करें:
जनता स्थिर खालीपन मुख्य ( डोरी तर्क [ ] ) {
ग्राफ के = नया ग्राफ़ ( 4 ) ;
क। addEdge ( 0 , 1 ) ;
क। addEdge ( 1 , 2 ) ;
क। addEdge ( 2 , 3 ) ;
क। addEdge ( 3 , 3 ) ;
प्रणाली . बाहर . println ( 'निम्नलिखित गहराई पहले ट्रैवर्सल है' ) ;
क। डीएफएस ( 1 ) ;
}
}
उपरोक्त कोड की व्याख्या:
- सबसे पहले, एक वस्तु बनाएँ ' क ' के लिए ' ग्राफ () ' तरीका।
- अगला, ' ऐड एज () ” विधि का उपयोग कई शीर्षों के बीच किनारों को जोड़ने के लिए किया जाता है। यह हमारे ग्राफ की संरचना बनाता है।
- अंत में, किसी भी वर्टेक्स वैल्यू को पहले से बनाए गए तर्क के रूप में पास करें ' डीएफएस () ' समारोह। जड़ से उस शीर्ष पथ को खोजने के लिए, गहराई-पहले खोज एल्गोरिथम का उपयोग करें। उदाहरण के लिए, 'का मान 1 'को पास किया जाता है' डीएफएस () ' समारोह।
संकलन चरण के अंत के बाद:
आउटपुट दिखाता है कि डेप्थ-फर्स्ट सर्च को सफलतापूर्वक कार्यान्वित किया गया है।
निष्कर्ष
डेप्थ फर्स्ट सर्च एक ग्राफ ट्रैवर्सल एल्गोरिथम है जो कई ग्राफ एल्गोरिदम के लिए आधार बनाता है जैसे सबसे छोटा रास्ता खोजना, पेड़ों को फैलाना और कनेक्टिविटी विश्लेषण। यह रूट नोड से शुरू होता है और फिर बैकट्रैकिंग से पहले लीव नोड या उस शाखा के अंतिम नोड तक जितना संभव हो उतना गहरा चलता है। इस लेख ने जावा में एक ग्राफ के लिए डेप्थ-फर्स्ट सर्च या डीएफएस को लागू करने की प्रक्रिया का प्रदर्शन किया है।