ডেপথ-ফার্স্ট সার্চ (DFS) একটি গ্রাফ ট্রাভার্সাল অ্যালগরিদম। এই অ্যালগরিদমে, একটি শুরুর ভার্টেক্স দেওয়া থাকে, এবং যখন একটি আডজাসেন্ট ভার্টেক্স পাওয়া যায়, তবে সেটি সেরকম আডজাসেন্ট ভার্টেক্সে প্রথমে যেতে চায় এবং একই ম্যানারে ট্রাভার্স করার চেষ্টা করে।
এটি যতটা সম্ভব গভীরে চলে যায়, তারপর ব্যাকট্র্যাক করে পূর্বের ভার্টেক্সে আসে নতুন পথ খুঁজতে।
DFS ইটারেটিভলি ইমপ্লিমেন্ট করতে হলে, স্ট্যাক ডেটা স্ট্রাকচার ব্যবহার করতে হয়। যদি রিকার্শিভলি করতে চাই, তবে এক্সটার্নাল স্ট্যাক দরকার নেই, রিকার্শন কলের ইন্টারনাল স্ট্যাকেই করা যায়।
ইনপুট এবং আউটপুট
ইনপুট: একটি গ্রাফের এডজেসেন্সি ম্যাট্রিক্স। A B C D E F A 0 1 1 1 0 0 B 1 0 0 1 1 0 C 1 0 0 1 1 0 D 1 1 1 0 1 1 E 0 1 0 1 0 1 F 0 0 1 1 1 0 আউটপুট: DFS Traversal: C F E B D A
অ্যালগরিদম
dfs(vertices, start)
ইনপুট: সব ভার্টেক্সের লিস্ট, এবং স্টার্ট নোড।
আউটপুট: গ্রাফের সব নোড ট্রাভার্স করা।
শুরু
প্রাথমিকভাবে সব নোডের স্টেট আনভিজিটেড করুন
start কে স্ট্যাকে পুশ করুন
যতক্ষণ স্ট্যাক খালি নয়, করুন
স্ট্যাক থেকে এলিমেন্ট পপ করুন এবং u-তে সেট করুন
নোড u ডিসপ্লে করুন
যদি u ভিজিটেড না হয়, তবে
u কে ভিজিটেড মার্ক করুন
u-এর সাথে সংযুক্ত সব নোড i-এর জন্য করুন
যদি i-তম ভার্টেক্স আনভিজিটেড হয়, তবে
i-তম ভার্টেক্স স্ট্যাকে পুশ করুন
i-তম ভার্টেক্স ভিজিটেড মার্ক করুন
শেষ
শেষ
শেষ
উদাহরণ
#include<iostream> #include<stack> using namespace std; #define NODE 6 typedef struct node { int val; int state; //স্ট্যাটাস }node; int graph[NODE][NODE] = { {0, 1, 1, 1, 0, 0}, {1, 0, 0, 1, 1, 0}, {1, 0, 0, 1, 0, 1}, {1, 1, 1, 0, 1, 1}, {0, 1, 0, 1, 0, 1}, {0, 0, 1, 1, 1, 0} }; void dfs(node *vertex, node start) { node u; stack<node> myStack; for(int i = 0; i
আউটপুট
DFS Traversal: C F E B D A
