रुंदीच्या-प्रथम शोध (BFS) म्हणजे काय?

Question

Accepted Answer

**BFS** एक आलेख स्तर-दर-स्तर शोधते, एका नोडचे सर्व शेजारी भेट दिल्यानंतर खोलीत जाते. हा **रांग** वापरतो आणि **सर्वात लहान मार्ग** (सर्वात कमी किनारे) अवजन केलेल्या आलेखांमध्ये शोधतो.

## कल्पना

स्रोतापासून प्रारंभ करा, त्यास रांगेत टाका, त्यानंतर वारंवार नोड काढून घ्या, त्याचे अपरिदर्शक शेजारी भेट द्या आणि त्यांना रांगेत टाका. `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) — प्रत्येक शीर्ष आणि किनारा एकदा.
- **जागा:** O(V) रांग आणि visited सेटसाठी.

## कधी वापरायचे / नुकसान

**अवजन केलेल्या आलेखांमध्ये सर्वात लहान मार्ग**, स्तर-क्रम ट्रॅव्हर्सल आणि जोडलेले घटक शोधण्यासाठी BFS वापरा. DFS पेक्षा अधिक स्मृति वापरते (एकाच वेळी संपूर्ण सीमा). नेहमी `visited` ट्रॅक करा किंवा तुम्ही चक्रांमध्ये कायमचे लूप करू शकता.

## हे महत्वाचे का आहे

BFS हा **सर्वात लहान मार्गांचे** *अल्गोरिदम* आहे जेव्हा प्रत्येक किनारा समान महत्वाचा असतो — रूटिंग, वेब क्रॉलिंग, सामाजिक नेटवर्क विभाजन अंश.

त्याची रांग-आधारित, स्तर-दर-स्तर रचना एक मूलभूत ट्रॅव्हर्सल नमुना आहे.

BFS बनाम DFS हे जाणून घेणे तुम्हाला पहुँचक्षमता, मार्ग आणि ऑर्डरिंग समस्यांसाठी योग्य साधन निवडू देते.