মডিউল ৩_০ঃ ইনট্রোডাকশন

BFS vs DFS

BFS	DFS
BFS এর পূর্ণরূপ হল Breadth-First Search।	DFS এর পূর্ণরূপ হল Depth-First Search।
BFS কোন একটি গন্তব্যের shortest path বের করে দেয়।	DFS নিচের সাব-ট্রি গুলো গিয়ে আবার ব্যাকট্র্যাক করতে পারে।
BFS লেভেল অনুযায়ী ট্রাভাস করে।	DFS ডেপ্ট অনুযায়ী ট্রাভাস করে।
BFS ইমপ্লিমেন্ট queue দিয়ে করা হয়।	DFS ইমপ্লিমেন্ট recursion দিয়ে করা হয়।
BFS তুলনামূলক DFS থেকে বেশি মেমোরি ব্যবহার করে।	DFS তুলনামূলক BFS থেকে কম মেমোরি ব্যবহার করে।
BFS চালাতে ব্যাকট্র্যাকিংয়ের প্রয়োজন নেই।	DFS চালাতে ব্যাকট্র্যাকিংয়ের প্রয়োজন হয়।

Time Complexity:

Worst কেসে BFS এবং DFS এর time complexity একইরকম O(V+E) হয়ে থাকে।