வழங்கப்பட்ட மரம் அல்லது வரைபடத்திற்கான DFS ஐ செயல்படுத்துவதற்கான செயல்முறையை இந்தக் கட்டுரை விளக்குகிறது.
ஜாவாவில் ஒரு வரைபடத்திற்கான ஆழமான முதல் தேடல் அல்லது DFS ஐ எவ்வாறு செயல்படுத்துவது?
DFS முதன்மையாக ஒவ்வொரு கிளை/உச்சியையும் சரியாக ஒரு முறை சென்று வரைபடத்தைத் தேடுவதற்குப் பயன்படுத்தப்படுகிறது. இது முட்டுக்கட்டைகளைத் தடுக்க உதவும் வரைபடத்தில் சுழற்சிகளைக் கண்டறியலாம் அல்லது அடையாளம் காண முடியும். புதிர்கள் அல்லது பிரமை சிக்கல்களைத் தீர்க்க இது பயன்படுத்தப்படலாம். DFS ஐ வரைபட அல்காரிதம்கள், வலை கிராலிங் மற்றும் கம்பைலர் வடிவமைப்பு ஆகியவற்றில் செயல்படுத்தலாம்/பயன்படுத்தலாம்.
விளக்கத்திற்கு, ஆழமான முதல் தேடல் அல்லது DFS இன் கீழே உள்ள குறியீட்டைப் பார்வையிடவும்:
வர்க்கம் வரைபடம் {
தனிப்பட்ட இணைக்கப்பட்ட பட்டியல் addNode [ ] ;
தனிப்பட்ட பூலியன் பயணித்தது [ ] ;
வரைபடம் ( முழு எண்ணாக முனைகள் ) {
addNode = புதிய இணைக்கப்பட்ட பட்டியல் [ முனைகள் ] ;
பயணித்தது = புதிய பூலியன் [ முனைகள் ] ;
க்கான ( முழு எண்ணாக நான் = 0 ; நான் < முனைகள் ; நான் ++ )
addNode [ நான் ] = புதிய இணைக்கப்பட்ட பட்டியல் ( ) ;
}
வெற்றிடமானது addEdge ( முழு எண்ணாக எஸ்ஆர்சி, முழு எண்ணாக தொடங்கு ) {
addNode [ src ] . கூட்டு ( தொடங்கு ) ;
}
மேலே உள்ள குறியீட்டின் விளக்கம்:
- முதலில், வகுப்பு ' வரைபடம் ” உருவாக்கப்பட்டது. அதன் உள்ளே, '' என்று அறிவிக்கிறது. இணைக்கப்பட்ட பட்டியல் 'பெயர்' addNode[] 'மற்றும் ஒரு பூலியன் வகை வரிசை' என்று பெயரிடப்பட்டது பயணித்தது[] ”.
- அடுத்து, '' இன் கட்டமைப்பாளருக்கான செங்குத்துகளை அனுப்பவும் வரைபடம் ஒரு அளவுருவாக வர்க்கம்.
- அதன் பிறகு, ' க்கான தேர்ந்தெடுக்கப்பட்ட கிளையின் ஒவ்வொரு முனை வழியாகவும் செல்ல வளையம் உருவாக்கப்படுகிறது.
- இறுதியில், வெற்றிட வகை ' addEdge() ” செங்குத்துகளுக்கு இடையில் விளிம்புகளைச் சேர்க்கப் பயன்படுகிறது. இந்த செயல்பாடு இரண்டு அளவுருக்களை எடுக்கும்: உச்சியின் ஆதாரம் ' src 'மற்றும் இலக்கு உச்சி' தொடங்கு ”.
வரைபடத்தை உருவாக்கிய பிறகு, மேலே உருவாக்கப்பட்ட வரைபடத்திற்கான ஆழம்-முதல் தேடல் அல்லது DFS குறியீட்டைச் சேர்ப்போம்:
வெற்றிடமானது DFS ( முழு எண்ணாக உச்சி ) {
பயணித்தது [ உச்சி ] = உண்மை ;
அமைப்பு . வெளியே . அச்சு ( உச்சி + '' ) ;
மறு செய்கை இது = addNode [ உச்சி ] . பட்டியல்இடரேட்டர் ( ) ;
போது ( இது. அடுத்து உள்ளது ( ) ) {
முழு எண்ணாக adj = இது. அடுத்தது ( ) ;
என்றால் ( ! பயணித்தது [ adj ] )
DFS ( adj ) ;
}
}
மேலே உள்ள குறியீடு தொகுதியில்:
- முதலில், ' DFS() 'செயல்பாடு உருவாக்கப்பட்டது, இது பெறுகிறது' உச்சி ” ஒரு அளவுருவாக. அந்த உச்சியில் பார்வையிட்டதாகக் குறிக்கப்பட்டுள்ளது.
- அடுத்து, '' ஐப் பயன்படுத்தி பார்வையிட்ட உச்சியை அச்சிடவும் out.print() ”முறை.
- பின்னர், ஒரு உதாரணத்தை உருவாக்கவும் ' மறு செய்கை ” இது தற்போதைய உச்சியின் அருகிலுள்ள செங்குத்துகளுக்கு மேல் திரும்பும்.
- உச்சியை பார்வையிடவில்லை என்றால், அது அந்த உச்சியை ' DFS() ” செயல்பாடு.
இப்போது, '' ஒன்றை உருவாக்குவோம் முக்கிய() 'செயல்பாட்டு பகுதி வரைபடத்தை உருவாக்கி, அதற்கு DFS ஐப் பயன்படுத்தவும்:
பொது நிலையான வெற்றிடமானது முக்கிய ( லேசான கயிறு args [ ] ) {
வரைபடம் கே = புதிய வரைபடம் ( 4 ) ;
கே. addEdge ( 0 , 1 ) ;
கே. addEdge ( 1 , 2 ) ;
கே. addEdge ( 2 , 3 ) ;
கே. addEdge ( 3 , 3 ) ;
அமைப்பு . வெளியே . println ( 'பின்வருவது ஆழம் முதல் பயணம்' ) ;
கே. DFS ( 1 ) ;
}
}
மேலே உள்ள குறியீட்டின் விளக்கம்:
- முதலில், ஒரு பொருளை உருவாக்கவும் ' கே ' அதற்காக ' வரைபடம்() ”முறை.
- அடுத்து, ' addEdge() பல செங்குத்துகளுக்கு இடையில் விளிம்புகளைச் சேர்க்க 'முறை பயன்படுத்தப்படுகிறது. இது எங்கள் வரைபடத்தின் கட்டமைப்பை உருவாக்குகிறது.
- முடிவில், ஏற்கனவே உருவாக்கப்பட்ட 'உச்சி மதிப்பை ஒரு வாதமாக அனுப்பவும். DFS() ” செயல்பாடு. மூலத்திலிருந்து அந்த உச்சி பாதையைக் கண்டறிய, ஆழமான முதல் தேடல் அல்காரிதத்தைப் பயன்படுத்தவும். உதாரணமாக, ஒரு மதிப்பு ' 1 ''க்கு அனுப்பப்படுகிறது DFS() ” செயல்பாடு.
தொகுத்தல் கட்டம் முடிந்த பிறகு:
ஆழம்-முதல் தேடல் வெற்றிகரமாக செயல்படுத்தப்பட்டதை வெளியீடு காட்டுகிறது.
முடிவுரை
ஆழம் முதல் தேடல் என்பது ஒரு வரைபட டிராவர்சல் அல்காரிதம் ஆகும், இது குறுகிய பாதை, பரந்து விரிந்த மரங்கள் மற்றும் இணைப்பு பகுப்பாய்வு போன்ற பல வரைபட வழிமுறைகளுக்கு அடிப்படையாக அமைகிறது. இது ரூட் முனையிலிருந்து தொடங்கி, பின்தொடருவதற்கு முன் அந்த கிளையின் லீவ் முனை அல்லது கடைசி முனை வரை முடிந்தவரை ஆழமாக நகரும். ஜாவாவில் ஒரு வரைபடத்திற்கான ஆழமான முதல் தேடல் அல்லது DFS ஐ செயல்படுத்துவதற்கான செயல்முறையை இந்தக் கட்டுரை விளக்கியுள்ளது.