একটি গ্রাফের জন্য গভীরতার প্রথম অনুসন্ধান (DFS)

The Depth-First Search (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 0 1 0 1 E 0 1 0 1 0 1 0 1 F 0 0 1 1 1 0 0 1 F 0 0 1 1 1 0 আউটপুট:DFS ট্র্যাভার্সাল:সি এফ ডি প্রি> 
অ্যালগরিদম
 
dfs(শীর্ষ, শুরু)
 

 ইনপুট: সমস্ত শীর্ষবিন্দুর তালিকা এবং স্টার্ট নোড।
 

 আউটপুট: গ্রাফের সমস্ত নোড অতিক্রম করুন৷
৷ 
স্ট্যাক খালি না থাকা অবস্থায় স্ট্যাকের মধ্যে সমস্ত নোড পুশ স্টার্টের জন্য প্রথমে স্টেটটিকে আনভিজিটেড করা শুরু করুন, স্ট্যাক থেকে পপ এলিমেন্ট করুন এবং নোড u ডিসপ্লেতে সেট করুন যদি u ভিজিট না করা হয়, তারপর ইউকে সবার জন্য ভিজিট করা হিসাবে চিহ্নিত করুন আমি আপনার সাথে সংযুক্ত নোডগুলি, যদি ith vertex unvisited হয় তাহলে করুন, তারপর ith vertex কে স্ট্যাক মার্ক ith vertex যেমন পরিদর্শন করা হয়েছে সম্পন্ন করা হয়েছে। 
উদাহরণ
 
#include#includeNamespace std ব্যবহার করে;#define NODE 6typedef struct node { int val; int state; //status}নোড;int গ্রাফ[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 (নোড *ভার্টেক্স, নোড শুরু) { নোড ইউ; স্ট্যাক<নোড> মাইস্ট্যাক; for(int i =0; i 
আউটপুট
 
DFS ট্রাভার্সাল:CF E B D A