# Breadth-First Search — डेटा स्ट्रक्चर और एल्गोरिदम

Source: https://www.geekswithgeeks.com/hi/dsa/bfs

> Queue से graph को स्तर दर स्तर देखें — अभारित graph में सबसे छोटा पथ खोजता है।

## शुरुआत के चारों ओर छल्ले

BFS पहले 1 edge दूर सभी nodes, फिर 2 edge दूर सभी, इत्यादि देखता है। **Queue** यह क्रम लागू करती है और **visited set** पुनःयात्रा रोकता है। किसी node तक पहली बार पहुँचना सबसे छोटे पथ (edge में) से होता है। `O(V + E)`।

## सबसे छोटी पथ लंबाई

हर पड़ोसी को पहली बार enqueue करते समय दूरी ट्रैक करें।

```python
from collections import deque
def shortest(g, start, goal):
    q = deque([(start, 0)])
    seen = {start}
    while q:
        node, d = q.popleft()
        if node == goal:
            return d
        for nb in g[node]:
            if nb not in seen:
                seen.add(nb)
                q.append((nb, d + 1))
    return -1
```

## यह कहाँ फिट है

भूलभुलैया/grid में सबसे छोटा पथ, "न्यूनतम चरण...", tree का level-order traversal, word ladder, और flood fill। यदि edge पर weight हो, Dijkstra पर जाएँ।