এই নিবন্ধটি একটি প্রদত্ত গাছ বা গ্রাফের জন্য DFS বাস্তবায়নের পদ্ধতি প্রদর্শন করে।
জাভাতে একটি গ্রাফের জন্য গভীরতার প্রথম অনুসন্ধান বা ডিএফএস কীভাবে প্রয়োগ করবেন?
DFS প্রাথমিকভাবে প্রতিটি শাখা/বিন্দু ঠিক একবার পরিদর্শন করে একটি গ্রাফ অনুসন্ধানের জন্য ব্যবহৃত হয়। এটি একটি গ্রাফে চক্র সনাক্ত বা সনাক্ত করতে পারে যা অচলাবস্থা প্রতিরোধে সহায়তা করে। এটি ধাঁধা বা গোলকধাঁধা সমস্যা সমাধান করতে ব্যবহার করা যেতে পারে। DFS গ্রাফ অ্যালগরিদম, ওয়েব ক্রলিং এবং কম্পাইলার ডিজাইনে প্রয়োগ/ব্যবহার করা যেতে পারে।
একটি ব্যাখ্যার জন্য, গভীরতার প্রথম অনুসন্ধান বা DFS-এর নীচের কোডটি দেখুন:
ক্লাস চিত্রলেখ {
ব্যক্তিগত যোজিত তালিকা addNode [ ] ;
ব্যক্তিগত বুলিয়ান ট্রাভার্সড [ ] ;
চিত্রলেখ ( int শীর্ষবিন্দু ) {
addNode = নতুন যোজিত তালিকা [ শীর্ষবিন্দু ] ;
ট্রাভার্সড = নতুন বুলিয়ান [ শীর্ষবিন্দু ] ;
জন্য ( int i = 0 ; i < শীর্ষবিন্দু ; i ++ )
addNode [ i ] = নতুন যোজিত তালিকা ( ) ;
}
অকার্যকর addEdge ( int src, int শুরু ) {
addNode [ src ] . যোগ করুন ( শুরু ) ;
}
উপরের কোডের বর্ণনা:
- প্রথমে, ক্লাসের নাম ' চিত্রলেখ ' সৃষ্ট. এর ভিতরে ঘোষণা করে একটি ' যোজিত তালিকা 'নাম' addNode[] ” এবং একটি বুলিয়ান টাইপ অ্যারে নামক “ পাড়ি দেওয়া[] ”
- এর পরে, 'এর কনস্ট্রাক্টরের জন্য শীর্ষবিন্দুগুলি পাস করুন চিত্রলেখ একটি পরামিতি হিসাবে ক্লাস।
- এর পরে, ' জন্য নির্বাচিত শাখার প্রতিটি নোডের মধ্য দিয়ে যাওয়ার জন্য লুপ তৈরি করা হয়।
- শেষ পর্যন্ত, অকার্যকর টাইপ ' addEdge() ” শীর্ষবিন্দুর মধ্যে প্রান্ত যোগ করতে ব্যবহৃত হয়। এই ফাংশনটি দুটি প্যারামিটার নেয়: শীর্ষবিন্দুর উৎস “ src ' এবং গন্তব্য শীর্ষবিন্দু ' শুরু ”
একটি গ্রাফ তৈরি করার পর, এখন উপরের তৈরি গ্রাফের জন্য ডেপথ-ফার্স্ট সার্চ বা ডিএফএস কোড যোগ করা যাক:
অকার্যকর ডিএফএস ( int শীর্ষবিন্দু ) {
ট্রাভার্সড [ শীর্ষবিন্দু ] = সত্য ;
পদ্ধতি . আউট . ছাপা ( শীর্ষবিন্দু + '' ) ;
পুনরাবৃত্তিকারী এই = addNode [ শীর্ষবিন্দু ] . listIterator ( ) ;
যখন ( এই. আছে পরবর্তী ( ) ) {
int adj = এই. পরবর্তী ( ) ;
যদি ( ! ট্রাভার্সড [ adj ] )
ডিএফএস ( adj ) ;
}
}
উপরের কোড ব্লকে:
- প্রথমত, ' DFS() ' ফাংশন তৈরি করা হয় যা পাচ্ছে ' শীর্ষবিন্দু একটি প্যারামিটার হিসাবে। যে শীর্ষবিন্দু পরিদর্শন হিসাবে চিহ্নিত করা হয়.
- এর পরে, ' ব্যবহার করে পরিদর্শন করা শীর্ষবিন্দুটি মুদ্রণ করুন out.print() 'পদ্ধতি।
- তারপর, 'এর একটি উদাহরণ তৈরি করুন পুনরাবৃত্তিকারী ” যা বর্তমান শীর্ষবিন্দুর সন্নিহিত শীর্ষবিন্দুর উপর পুনরাবৃত্তি করে।
- যদি শীর্ষবিন্দুটি পরিদর্শন না করা হয়, তাহলে এটি সেই শীর্ষবিন্দুটিকে ' DFS() ' ফাংশন।
এখন, আসুন একটি তৈরি করি ' প্রধান() গ্রাফ তৈরি করতে ফাংশন অংশ এবং তারপরে DFS প্রয়োগ করুন:
সর্বজনীন স্থির অকার্যকর প্রধান ( স্ট্রিং args [ ] ) {
গ্রাফ k = নতুন চিত্রলেখ ( 4 ) ;
k. addEdge ( 0 , 1 ) ;
k. addEdge ( 1 , 2 ) ;
k. addEdge ( 2 , 3 ) ;
k. addEdge ( 3 , 3 ) ;
পদ্ধতি . আউট . println ( 'অনুসরণ হল গভীরতা প্রথম ট্রাভার্সাল' ) ;
k. ডিএফএস ( 1 ) ;
}
}
উপরের কোডের ব্যাখ্যা:
- প্রথমে একটি বস্তু তৈরি করুন ' k 'এর জন্য' চিত্রলেখ() 'পদ্ধতি।
- পরবর্তী, ' addEdge() ” পদ্ধতিটি একাধিক শীর্ষবিন্দুর মধ্যে প্রান্ত যোগ করতে ব্যবহার করা হয়। এটি আমাদের গ্রাফের গঠন তৈরি করে।
- শেষ পর্যন্ত, ইতিমধ্যে তৈরি করা 'এ আর্গুমেন্ট হিসাবে যে কোনও শীর্ষের মান পাস করুন' DFS() ' ফাংশন। মূল থেকে সেই শীর্ষবিন্দু পথটি খুঁজে পেতে, একটি গভীরতা-প্রথম অনুসন্ধান অ্যালগরিদম ব্যবহার করুন। উদাহরণস্বরূপ, 'এর একটি মান 1 'এ পাস করা হয়' DFS() ' ফাংশন।
সংকলন পর্ব শেষ হওয়ার পরে:
আউটপুট দেখায় গভীরতা-প্রথম অনুসন্ধান সফলভাবে প্রয়োগ করা হয়েছে।
উপসংহার
ডেপথ ফার্স্ট সার্চ হল একটি গ্রাফ ট্র্যাভার্সাল অ্যালগরিদম যা অনেক গ্রাফ অ্যালগরিদমের ভিত্তি তৈরি করে যেমন সবচেয়ে ছোট পথ খুঁজে বের করা, গাছ ছড়ানো, এবং সংযোগ বিশ্লেষণ। এটি রুট নোড থেকে শুরু হয় এবং তারপর ব্যাকট্র্যাক করার আগে সেই শাখার লীভ নোড বা শেষ নোড পর্যন্ত যতটা সম্ভব গভীরে চলে যায়। এই নিবন্ধটি জাভাতে একটি গ্রাফের জন্য গভীরতা-প্রথম অনুসন্ধান বা DFS প্রয়োগ করার পদ্ধতি প্রদর্শন করেছে।