இல் DFS , ஆராயப்படும் முனைகள் ஒரு அடுக்கு தரவு கட்டமைப்பில் சேமிக்கப்படும். ஆராயப்படாத முனைகளுக்கு நம்மை வழிநடத்தும் விளிம்புகள் 'என்று அழைக்கப்படுகின்றன. கண்டுபிடிப்பு விளிம்புகள் ' ஏற்கனவே பார்வையிட்ட முனைகளை வழிநடத்தும் விளிம்புகள் அழைக்கப்படுகின்றன ' தொகுதி விளிம்புகள் '. DFS ஒரு புரோகிராமர் ஒரு வரைபடத்தில் இணைக்கப்பட்ட கூறுகள் அல்லது சுழற்சிகளைக் கண்டறிய விரும்பும் சூழ்நிலைகளில் பயனுள்ளதாக இருக்கும்.
செயல்படுத்த இந்த கட்டுரையின் வழிகாட்டுதல்களைப் பின்பற்றவும் DFS C++ இல்.
C++ இல் DFS ஐ செயல்படுத்துதல்
அடுத்த பகுதியில், எப்படி என்பதைப் பார்ப்போம் DFS C++ இல் செயல்படுத்தப்படுகிறது. செயல்படுத்த கொடுக்கப்பட்ட படிகளைப் பின்பற்றலாம் DFS .
- ஒரு மரத்தின் வேர் முனையை அல்லது வரைபடத்தை அடுக்கில் செருகவும்.
- நீங்கள் பார்வையிட்ட பட்டியலில் அடுக்கின் மேல் உருப்படியைச் சேர்க்கவும்.
- பார்வையிட்ட முனைக்கு அருகிலுள்ள அனைத்து முனைகளையும் கண்டறிந்து, இன்னும் அடுக்கைப் பார்வையிடாத அந்த முனைகளைச் சேர்க்கவும்.
- ஸ்டாக் காலியாகும் வரை 2 மற்றும் 3 படிகளை மீண்டும் செய்யவும்.
DFS சூடோகோட்
தி DFS சூடோகோட் கீழே காட்டப்பட்டுள்ளது. இல் வெப்பம் () செயல்பாடு, நாங்கள் எங்கள் செயல்படுத்த DFS ஒவ்வொரு முனையிலும் செயல்பாடு. வரைபடத்தில் இரண்டு துண்டிக்கப்பட்ட பகுதிகள் இருப்பதால், நாம் அதை இயக்கலாம் DFS ஒவ்வொரு முனையிலும் உள்ள அல்காரிதம் ஒவ்வொரு உச்சியையும் உள்ளடக்கியிருப்பதை உறுதிசெய்யும்.
DFS ( g a )
அ. பார்வையிட்டார் = உண்மை
க்கான ஒவ்வொரு b ∈ g. Adj [ அ ]
என்றால் பி. பார்வையிட்டார் == பொய்
DFS ( g,b )
வெப்பம் ( )
{
ஒவ்வொரு a ∈ g க்கும்
அ. பார்வையிட்டார் = பொய்
ஒவ்வொரு a ∈ g க்கும்
DFS ( g, a )
}
இங்கே g, a மற்றும் b ஆகியவை வரைபடத்தைக் குறிக்கின்றன, முதலில் பார்வையிட்ட முனை மற்றும் கணுவை முறையே அடுக்கில் உள்ளன.
C++ இல் DFS ஐ செயல்படுத்துதல்
ஒரு C++ நிரல் DFS செயல்படுத்தல் கீழே கொடுக்கப்பட்டுள்ளது:
# அடங்கும்
#அடங்கும்<வரைபடம்>
#அடங்கும்<பட்டியல்>
பயன்படுத்தி பெயர்வெளி வகுப்பு ;
டெம்ப்ளேட் < வகைப்பெயர் டி >
வர்க்கம் ஆழம் முதல் தேடல்
{
தனிப்பட்ட :
வரைபடம் < t, பட்டியல் < டி > > adjList ;
பொது :
ஆழம் முதல் தேடல் ( ) { }
வெற்றிடமானது Add_edge ( t a, t b, பூல் நீ = உண்மை )
{
adjList [ அ ] . பின் தள்ளு ( பி ) ;
என்றால் ( நீ )
{
adjList [ பி ] . பின் தள்ளு ( அ ) ;
}
}
வெற்றிடமானது அச்சிடுக ( )
{
க்கான ( ஆட்டோ நான் : adjList ) {
கூட் << நான். முதலில் << '->' ;
க்கான ( டி நுழைவு : நான். இரண்டாவது ) {
கூட் << நுழைவு << ',' ;
}
கூட் << endl ;
}
}
வெற்றிடமானது dfs_helper ( டி முனை, வரைபடம் < டி, பூல் > & பார்வையிட்டார் ) {
பார்வையிட்டார் [ முனை ] = உண்மை ;
கூட் << முனை << '' << endl ;
க்கான ( t பக்கத்து வீட்டுக்காரர் : adjList [ முனை ] ) {
என்றால் ( ! பார்வையிட்டார் [ அண்டை ] ) {
dfs_helper ( பக்கத்து வீட்டுக்காரர், பார்வையிட்டார் ) ;
}
}
}
வெற்றிடமானது DFS ( t src )
{
வரைபடம் < டி, பூல் > பார்வையிட்டார் ;
dfs_helper ( எஸ்ஆர்சி, பார்வையிட்டார் ) ;
}
} ;
முழு எண்ணாக முக்கிய ( ) {
ஆழம் முதல் தேடல் < முழு எண்ணாக > g ;
g. Add_edge ( 0 , 5 ) ;
g. Add_edge ( 0 , 7 ) ;
g. Add_edge ( 4 , 7 ) ;
g. Add_edge ( 7 , 8 ) ;
g. Add_edge ( 2 , 1 ) ;
g. Add_edge ( 0 , 6 ) ;
g. Add_edge ( 2 , 4 ) ;
g. Add_edge ( 3 , 2 ) ;
g. Add_edge ( 3 , 6 ) ;
g. Add_edge ( 7 , 5 ) ;
g. Add_edge ( 5 , 8 ) ;
g. அச்சிடுக ( ) ;
g. DFS ( 6 ) ;
கூட் << endl ;
}
இந்த குறியீட்டில், நாங்கள் செயல்படுத்தியுள்ளோம் DFS மேலே கொடுக்கப்பட்ட போலிக் குறியீட்டைப் பின்பற்றும் அல்காரிதம். எங்களிடம் 12 ஜோடி முனைகள் உள்ளன. நாங்கள் ஒரு வகுப்பை வரையறுத்தோம் ' ஜி ” இது பார்வையிட்ட மற்றும் பார்க்காத முனைகளைக் குறிக்கும் a மற்றும் b செங்குத்துகளைக் கொண்ட வரைபடத்தைக் குறிக்கிறது.
வெளியீடு
முடிவுரை
DFS ஒரு வரைபடத்தில் சுழற்சிகளைக் கண்டறிதல் மற்றும் இணைக்கப்பட்ட கூறுகள் அல்லது வரைபடத்தில் உள்ள அனைத்து செங்குத்துகள் பற்றிய தகவலைப் பெறுதல் போன்ற பல காட்சிகளுக்குப் பயன்படும் பிரபலமான தேடல் அல்காரிதம் ஆகும். இன் செயல்பாட்டையும் விவரித்தோம் DFS ஒரு உதாரணத்துடன் முறை. DFS நுட்பத்தை செயல்படுத்த அடுக்குகளை பயன்படுத்துகிறது மற்றும் மரங்களிலும் பயன்படுத்தலாம்.