Menene breadth-first search (BFS)?

Question

Accepted Answer

**BFS** yana bincikon jadawali matakin-matakin, yana ziyartar duk maƙwabacin node kafin ƙara zuriya. Yana amfani da **queue** kuma yana neman **hanyar gida** (gefuna kaɗan) a cikin jadawali marasa nauyi.

## Ra'ayin abu

Fara daga tushe, shigar da shi, sannan a maimaita: cire node, ziyarci maƙwabacinsa wadanda ba'a ziyarcce, sannan shigar da su. Saitin `visited` yana kawar da sake ziyarwa.

## Misali

```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']
```

## Iyawa

- **Lokaci:** O(V + E) — kowane vertex da edge sau daya.
- **Sarari:** O(V) don queue da saitin visited.

## Lokacin amfani / hadaddun batu

Ai BFS don **hanyar gida a cikin jadawali marasa nauyi**, safin-safin matakin, da nemo ɓangaren haɗa. Yana amfani da ƙari kuɗi fiye da DFS (jiya a jiya duka a lokaci gida). A koyaushe lura `visited` ko kuma kila zai kunna kai-kai a hanyoyin da suke jingina.

## Dalilin da ya sa ya kame

BFS shi ne *algorithm* na hanyar gida lokacin da kowane gefe ya lissafi daidai — jiya, binciken kuliga, da digiri-digiri na hanyar sadarwa ta jama'a.

Rabuwar queue-da, rabuwar matakin-matakin ta da abin mahimmanci a cikin salo na binciko.

Sanin BFS da DFS yana ba ka damar zaɓar kayan gida daidai don sakamako, jiya, da bukatun oda.