में डीएफएस , खोजे जा रहे नोड्स को स्टैक डेटा संरचना में संग्रहीत किया जाता है। वे किनारे जो हमें अस्पष्टीकृत नोड्स तक ले जाते हैं, कहलाते हैं ' डिस्कवरी किनारों 'जबकि पहले से देखे गए नोड्स का नेतृत्व करने वाले किनारों को' कहा जाता है ब्लॉक किनारों '। डीएफएस परिदृश्यों में उपयोगी होता है जब एक प्रोग्रामर एक ग्राफ में जुड़े हुए घटकों या चक्रों को खोजना चाहता है।
लागू करने के लिए इस लेख के दिशानिर्देशों का पालन करें डीएफएस सी ++ में।
सी ++ में डीएफएस का कार्यान्वयन
अगले भाग में, हम जानेंगे कि कैसे डीएफएस सी ++ में लागू किया गया है। लागू करने के लिए दिए गए चरणों का पालन कर सकते हैं डीएफएस .
- स्टैक में ट्री या ग्राफ़ का रूट नोड डालें।
- अपनी विज़िट की गई सूची में स्टैक के शीर्ष आइटम को जोड़ें।
- विज़िट किए गए नोड के सभी आसन्न नोड्स की खोज करें और उन नोड्स को जोड़ें जो अभी तक स्टैक पर नहीं गए हैं।
- स्टैक खाली होने तक चरण 2 और 3 दोहराएं।
डीएफएस स्यूडोकोड
डीएफएस स्यूडोकोड नीचे दिखाया गया है। में गर्मी() कार्य, हम अपना निष्पादित करते हैं डीएफएस प्रत्येक नोड पर कार्य करें। क्योंकि ग्राफ़ में दो डिस्कनेक्ट किए गए भाग हो सकते हैं, हम चला सकते हैं डीएफएस प्रत्येक नोड पर एल्गोरिथ्म यह सुनिश्चित करने के लिए कि हमने प्रत्येक शीर्ष को कवर किया है।
डीएफएस ( जी ए )
एक। का दौरा किया = सत्य
के लिए हर बी ∈ जी। समायो [ ए ]
अगर बी। का दौरा किया == असत्य
डीएफएस ( जी, बी )
गर्मी ( )
{
हर एक ∈ जी के लिए
एक। का दौरा किया = असत्य
हर एक ∈ जी के लिए
डीएफएस ( जी, ए )
}
यहाँ जी, ए और बी ग्राफ का प्रतिनिधित्व करते हैं, पहले क्रमशः स्टैक में नोड और नोड का दौरा किया।
सी ++ में डीएफएस लागू करना
के लिए एक C++ प्रोग्राम डीएफएस कार्यान्वयन नीचे दिया गया है:
# शामिल
# शामिल <नक्शा>
# शामिल <सूची>
का उपयोग करते हुए नाम स्थान कक्षा ;
खाका < नाम टाइप करें टी >
कक्षा डेप्थफर्स्टसर्च
{
निजी :
नक्शा < टी, सूची < टी > > adjList ;
जनता :
डेप्थफर्स्टसर्च ( ) { }
खालीपन Add_edge ( टी ए, टी बी, बूल आप = सत्य )
{
adjList [ ए ] . वापस धक्का देना ( बी ) ;
अगर ( आप )
{
adjList [ बी ] . वापस धक्का देना ( ए ) ;
}
}
खालीपन छाप ( )
{
के लिए ( ऑटो मैं : adjList ) {
अदालत << मैं। पहला << '->' ;
के लिए ( टी प्रवेश : मैं। दूसरा ) {
अदालत << प्रवेश << ',' ;
}
अदालत << endl ;
}
}
खालीपन dfs_helper ( टी नोड, नक्शा < टी, बूल > और का दौरा किया ) {
का दौरा किया [ नोड ] = सत्य ;
अदालत << नोड << '' << endl ;
के लिए ( टी पड़ोसी : adjList [ नोड ] ) {
अगर ( ! का दौरा किया [ पड़ोसी ] ) {
dfs_helper ( पड़ोसी, का दौरा किया ) ;
}
}
}
खालीपन डीएफएस ( टी स्रोत )
{
नक्शा < टी, बूल > का दौरा किया ;
dfs_helper ( एसआरसी, का दौरा किया ) ;
}
} ;
int यहाँ मुख्य ( ) {
डेप्थफर्स्टसर्च < int यहाँ > जी ;
जी। Add_edge ( 0 , 5 ) ;
जी। Add_edge ( 0 , 7 ) ;
जी। Add_edge ( 4 , 7 ) ;
जी। Add_edge ( 7 , 8 ) ;
जी। Add_edge ( 2 , 1 ) ;
जी। Add_edge ( 0 , 6 ) ;
जी। Add_edge ( 2 , 4 ) ;
जी। Add_edge ( 3 , 2 ) ;
जी। Add_edge ( 3 , 6 ) ;
जी। Add_edge ( 7 , 5 ) ;
जी। Add_edge ( 5 , 8 ) ;
जी। छाप ( ) ;
जी। डीएफएस ( 6 ) ;
अदालत << endl ;
}
इस कोड में, हमने लागू किया है डीएफएस एल्गोरिथ्म ऊपर दिए गए छद्म कोड के बाद। हमारे पास 12 जोड़े नोड्स हैं। हमने एक वर्ग परिभाषित किया ' जी ” जो एक ग्राफ का प्रतिनिधित्व करता है जिसमें ए और बी होते हैं जो देखे गए और बिना देखे गए नोड्स का प्रतिनिधित्व करते हैं।
उत्पादन
निष्कर्ष
डीएफएस एक लोकप्रिय खोज एल्गोरिद्म है जो कई परिदृश्यों के लिए उपयोगी है, जैसे किसी ग्राफ़ में चक्र खोजना, और कनेक्टेड घटकों या ग्राफ़ में सभी शीर्षों के बारे में जानकारी प्राप्त करना। की कार्यप्रणाली का भी वर्णन किया डीएफएस एक उदाहरण के साथ विधि। डीएफएस तकनीक को निष्पादित करने के लिए ढेर लगाता है और पेड़ों पर भी इस्तेमाल किया जा सकता है।