Što je pretraga u širinu (BFS)?

Question

Accepted Answer

**BFS** istražuje graf razinu po razinu, posjećujući sve susjede čvora prije nego što ide dublje. Koristi **red čekanja** i pronalazi **najkraću putanju** (najmanje grana) u neusmjerenim grafovima.

## Ideja

Počnite od izvora, stavite ga u red, zatim se ponavljajuće uklanjaju čvorovi iz reda, posjećuju se neposjećeni susjedi i stavljaju u red. Skup `visited` sprječava ponovno posjećivanje.

## Primjer

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

## Kompleksnost

- **Vrijeme:** O(V + E) — svaki čvor i grana samo jednom.
- **Prostor:** O(V) za red čekanja i skup posjećenih.

## Kada koristiti / zamke

Koristite BFS za **najkraću putanju u neusmjerenim grafovima**, prolazak po razinama i pronalaženje povezanih komponenti. Koristi više memorije nego DFS (cijeli graničnik odjednom). Uvijek pratite `visited` ili se možda beskonačno petljati na ciklusa.

## Zašto je važno

BFS je *pravi* algoritam za najkraće putanje kada je svaka grana jednako važna — usmjeravanje, web crawling, stupnjevi odvajanja u društvenim mrežama.

Njezina struktura bazirana na redu čekanja i prolazak razinu po razinu fundamental je uzorak prolaska.

Znati BFS vs DFS omogućuje vam da odaberete pravi alat za dostižnost, putanje i probleme sortiranja.