Hva er bredde-først-søk (BFS)?

Question

Accepted Answer

**BFS** utforsker en graf nivå for nivå, og besøker alle naboer til en node før det går dypere. Det bruker en **kø** og finner den **korteste stien** (færrest kanter) i uvektede grafer.

## Ideen

Start ved en kilde, sett den inn i køen, fjern deretter gjentatte ganger en node fra køen, besøk dens ubesøkte naboer, og sett dem inn i køen. Et `visited` sett forhindrer gjenbesøk.

## Eksempel

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

## Kompleksitet

- **Tid:** O(V + E) — hver toppunkt og kant en gang.
- **Plass:** O(V) for køen og visited sett.

## Når du skal bruke / fallgruver

Bruk BFS for **korteste sti i uvektede grafer**, nivårekkefølge-traversal og finne sammenkoblede komponenter. Det bruker mer minne enn DFS (hele grensen på en gang). Spor alltid `visited` eller du kan gå i uendelig løkke på sykler.

## Hvorfor det betyr noe

BFS er *algoritmen* for korteste stier når hver kant teller like mye — ruting, web crawling, social-network degrees of separation.

Its købaserte, nivå-for-nivå struktur er et grunnleggende traversal-mønster.

Å kjenne BFS kontra DFS lar deg velge rett verktøy for rekkevidde, stier og ordningsproblemer.