BFS এবং DFS গ্রাফ ট্রাভার্সাল অ্যালগরিদম।
BFS
ব্রেডথ ফার্স্ট সার্চ (BFS) অ্যালগরিদম একটি গ্রাফ ব্রেডথওয়ার্ড গতিতে ট্রাভার্স করে এবং একটি কিউ ব্যবহার করে নেক্স্ট ভার্টেক্স মনে রাখে যাতে ডেড এন্ড হলে সার্চ শুরু করা যায়।
DFS
ডেপথ ফার্স্ট সার্চ (DFS) অ্যালগরিদম একটি গ্রাফ ডেপথওয়ার্ড গতিতে ট্রাভার্স করে এবং একটি স্ট্যাক ব্যবহার করে নেক্স্ট ভার্টেক্স মনে রাখে যাতে ডেড এন্ড হলে সার্চ শুরু করা যায়।
BFS এবং DFS-এর মধ্যে গুরুত্বপূর্ণ পার্থক্যগুলো নিচে:
| Sr. No. | Key | BFS | DFS |
|---|---|---|---|
| 1 | Definition | BFS, stands for Breadth First Search. | DFS, stands for Depth First Search. |
| 2 | Data structure | BFS uses Queue to find the shortest path. | DFS uses Stack to find the shortest path. |
| 3 | Source | BFS is better when target is closer to Source. | DFS is better when target is far from source. |
| 4 | Suitablity for decision tree | As BFS considers all neighbour so it is not suitable for decision tree used in puzzle games. | DFS is more suitable for decision tree. As with one decision, we need to traverse further to augment the decision. If we reach the conclusion, we won. |
| 5 | Speed | BFS is slower than DFS. | DFS is faster than BFS. |
| 6 | Time Complexity | Time Complexity of BFS = O(V+E) where V is vertices and E is edges. | Time Complexity of DFS is also O(V+E) where V is vertices and E is edges. |
