ভিতরে ডিএফএস , অন্বেষণ করা নোডগুলি একটি স্ট্যাক ডেটা কাঠামোতে সংরক্ষণ করা হয়। যে প্রান্তগুলি আমাদেরকে অনাবিষ্কৃত নোডগুলিতে নির্দেশ করে তাকে বলা হয় ' আবিষ্কার প্রান্ত যখন প্রান্তগুলি ইতিমধ্যে পরিদর্শন করা নোডগুলিকে নেতৃত্ব দিতে যাচ্ছে তখন বলা হয় ' ব্লক প্রান্ত ' ডিএফএস পরিস্থিতিতে যখন একজন প্রোগ্রামার একটি গ্রাফে সংযুক্ত উপাদান বা চক্র খুঁজে পেতে চায় তখন এটি কার্যকর।
বাস্তবায়ন করতে এই নিবন্ধের নির্দেশিকা অনুসরণ করুন ডিএফএস C++ এ।
C++ এ DFS বাস্তবায়ন
নিম্নলিখিত বিভাগে, আমরা কীভাবে তা নিয়ে যাব ডিএফএস C++ এ প্রয়োগ করা হয়। কেউ বাস্তবায়নের জন্য প্রদত্ত পদক্ষেপগুলি অনুসরণ করতে পারেন ডিএফএস .
- স্ট্যাকের মধ্যে একটি গাছ বা গ্রাফের রুট নোড ঢোকান।
- আপনার পরিদর্শন তালিকায় স্ট্যাকের শীর্ষ আইটেম যোগ করুন।
- পরিদর্শন করা নোডের সমস্ত সংলগ্ন নোডগুলি আবিষ্কার করুন এবং সেই নোডগুলি যোগ করুন যেগুলি এখনও স্ট্যাকের পরিদর্শন করেনি।
- স্ট্যাক খালি না হওয়া পর্যন্ত পদক্ষেপ 2 এবং 3 পুনরাবৃত্তি করুন।
ডিএফএস সিউডোকোড
দ্য ডিএফএস pseudocode নীচে দেখানো হয়. মধ্যে তাপ() ফাংশন, আমরা আমাদের চালানো ডিএফএস প্রতিটি নোডে ফাংশন। কারণ গ্রাফটিতে দুটি সংযোগ বিচ্ছিন্ন অংশ থাকতে পারে, আমরা চালাতে পারি ডিএফএস প্রতিটি নোডের অ্যালগরিদম নিশ্চিত করুন যে আমরা প্রতিটি শীর্ষকে কভার করেছি।
ডিএফএস ( g ক )
ক পরিদর্শন = সত্য
জন্য প্রতি b ∈ g. Adj [ ক ]
যদি খ. পরিদর্শন == মিথ্যা
ডিএফএস ( g,b )
তাপ ( )
{
প্রতিটি a ∈ g এর জন্য
ক পরিদর্শন = মিথ্যা
প্রতিটি a ∈ g এর জন্য
ডিএফএস ( g, a )
}
এখানে g, a এবং b গ্রাফের প্রতিনিধিত্ব করে, প্রথমে ভিজিট করা নোড এবং নোড যথাক্রমে স্ট্যাকের মধ্যে।
C++ এ DFS বাস্তবায়ন করা
এর জন্য একটি C++ প্রোগ্রাম ডিএফএস বাস্তবায়ন নীচে দেওয়া হল:
#অন্তর্ভুক্ত করুন
#include
# অন্তর্ভুক্ত <তালিকা>
ব্যবহার নামস্থান std ;
টেমপ্লেট < টাইপনাম t >
ক্লাস DepthFirstSearch
{
ব্যক্তিগত :
মানচিত্র < t, তালিকা < t > > adjList ;
পাবলিক :
DepthFirstSearch ( ) { }
অকার্যকর Add_edge ( t a, t b, bool আপনি = সত্য )
{
adjList [ ক ] . ফেরত পাঠাও ( খ ) ;
যদি ( আপনি )
{
adjList [ খ ] . ফেরত পাঠাও ( ক ) ;
}
}
অকার্যকর ছাপা ( )
{
জন্য ( স্বয়ংক্রিয় i : adjList ) {
cout << i প্রথম << '->' ;
জন্য ( টি এন্ট্রি : i দ্বিতীয় ) {
cout << প্রবেশ << ',' ;
}
cout << endl ;
}
}
অকার্যকর dfs_helper ( t নোড, মানচিত্র < টি, bool > এবং পরিদর্শন ) {
পরিদর্শন [ নোড ] = সত্য ;
cout << নোড << '' << endl ;
জন্য ( t প্রতিবেশী : adjList [ নোড ] ) {
যদি ( ! পরিদর্শন [ প্রতিবেশী ] ) {
dfs_helper ( প্রতিবেশী, পরিদর্শন করেছেন ) ;
}
}
}
অকার্যকর ডিএফএস ( t src )
{
মানচিত্র < টি, bool > পরিদর্শন ;
dfs_helper ( src, পরিদর্শন করেছেন ) ;
}
} ;
int প্রধান ( ) {
DepthFirstSearch < int > 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 ডিএফএস ( 6 ) ;
cout << endl ;
}
এই কোডে, আমরা বাস্তবায়ন করেছি ডিএফএস উপরে দেওয়া ছদ্ম কোড অনুসরণ করে অ্যালগরিদম। আমাদের 12 জোড়া নোড আছে। আমরা একটি ক্লাস সংজ্ঞায়িত করেছি ' জি ” যা একটি গ্রাফ প্রতিনিধিত্ব করে যার শীর্ষবিন্দু a এবং b রয়েছে যা পরিদর্শন করা এবং দেখা না হওয়া নোডগুলিকে উপস্থাপন করে৷
আউটপুট
উপসংহার
ডিএফএস এটি একটি জনপ্রিয় অনুসন্ধান অ্যালগরিদম যা বিভিন্ন পরিস্থিতির জন্য উপযোগী, যেমন একটি গ্রাফে চক্রগুলি খুঁজে বের করা এবং একটি গ্রাফে সংযুক্ত উপাদান বা সমস্ত শীর্ষবিন্দু সম্পর্কে তথ্য পাওয়া। আমরা এর কাজও বর্ণনা করেছি ডিএফএস একটি উদাহরণ সহ পদ্ধতি। ডিএফএস কৌশলটি কার্যকর করার জন্য স্ট্যাক নিয়োগ করে এবং গাছেও ব্যবহার করা যেতে পারে।