ব্রেডথ-ফার্স্ট সার্চ (BFS) কী?

Question

Accepted Answer

**BFS** একটি গ্রাফ স্তর দ্বারা স্তর অন্বেষণ করে, একটি নোডের সমস্ত প্রতিবেশী পরিদর্শন করে আরও গভীরে যাওয়ার আগে। এটি একটি **queue** ব্যবহার করে এবং ওজনহীন গ্রাফগুলিতে **সংক্ষিপ্ততম পথ** (ন্যূনতম প্রান্ত) খুঁজে পায়।

## ধারণা

একটি উৎস থেকে শুরু করুন, এটি queue তে যোগ করুন, তারপর বারবার queue থেকে একটি নোড বের করুন, এর অপরিদর্শিত প্রতিবেশীদের পরিদর্শন করুন এবং তাদের queue তে যোগ করুন। একটি `visited` সেট পুনরায় পরিদর্শন প্রতিরোধ করে।

## উদাহরণ

```python
from collections import deque

def bfs(graph, start):
    visited = {start}
    queue = deque([start])
    order = []
    while queue:
        node = queue.popleft()        # FIFO: explore nearest first
        order.append(node)
        for nbr in graph[node]:
            if nbr not in visited:
                visited.add(nbr)
                queue.append(nbr)
    return order

graph = {'A': ['B', 'C'], 'B': ['D'], 'C': ['D'], 'D': []}
bfs(graph, 'A')                        # -> ['A', 'B', 'C', 'D']
```

## জটিলতা

- **সময়:** O(V + E) — প্রতিটি vertex এবং প্রান্ত একবার।
- **স্থান:** O(V) queue এবং visited সেটের জন্য।

## কখন ব্যবহার করবেন / সমস্যাগুলি

ওজনহীন গ্রাফগুলিতে **সংক্ষিপ্ততম পথ**, স্তর-অর্ডার ট্রেভার্সাল এবং সংযুক্ত উপাদান খুঁজে পাওয়ার জন্য BFS ব্যবহার করুন। এটি DFS এর চেয়ে বেশি মেমরি ব্যবহার করে (একবারে সম্পূর্ণ সীমানা)। `visited` ট্র্যাক করুন অথবা চক্রগুলিতে চিরকালের জন্য লুপ করতে পারেন।

## কেন এটি গুরুত্বপূর্ণ

BFS হল সংক্ষিপ্ততম পথের জন্য *প্রধান* অ্যালগরিদম যখন প্রতিটি প্রান্ত সমানভাবে গণনা করা হয় — রুটিং, ওয়েব ক্রলিং, সোশ্যাল-নেটওয়ার্ক বিচ্ছেদ।

এর queue-ভিত্তিক, স্তর-দ্বারা-স্তর কাঠামো একটি মৌলিক ট্রেভার্সাল প্যাটার্ন।

BFS বনাম DFS জেনে আপনি পৌঁছানোর ক্ষমতা, পথ এবং অর্ডারিং সমস্যাগুলির জন্য সঠিক সরঞ্জাম বেছে নিতে পারেন।