Bredde-først søk (BFS)

En måte å søke gjennom en graf på, så lenge vi har en graf $G=(V,E)$ og en kilde $s$. Leter etter noder som er nærmest først. Altså vi besøker noder som er 2 kanter unna før vi besøker noder som er 3 kanter unna. Køen den bruker er en FIFO

---

Det $s$ er startnoden. $d$ er avstanden fra startnoden til elementet, $Q$ er køen vår (nest node vi skal se på), og $\pi$ angir hva den forrige noden var. Noder som ikke er koblet, som $8$ i eksemplet over, får $d[8]=\infty$ og $\pi [8]=NIL$.

Kjøretid: $O(V+E)$

• Linje 1-4 er $O(V)$, og while loopen i ENQUEUE potensielt må innom alle kanter som gir $O(E)$.

Bredde-først tre

Vi får følgende traverseringstre fra eksempelet over