Bredden-först-sökning (BFS)

Släpp en sten i en damm så sprider sig vågorna jämnt i ringar. Bredden-först-sökning utforskar en graf på samma sätt: först allt ett steg från starten, sedan allt två steg bort, och så vidare. Det är den enkla ordningen som gör att den hittar kortaste vägar.

En graf med noder märkta med bokstäver, färgade i ringar efter avståndet från startnoden, med en kö av noder ritad under
En graf med noder märkta med bokstäver, färgade i ringar efter avståndet från startnoden, med en kö av noder ritad under

Idén

En graf är en mängd noder förbundna med kanter: platser och vägar, människor och vänskaper, rutor i en labyrint och öppningarna mellan dem. Bredden-först-sökning svarar på frågan: vad kan jag nå härifrån, och på hur få steg? Den har en kö med noder som ska besökas. Eftersom noder tas längst fram och nya läggs till längst bak hanteras noderna i den ordning de upptäcktes.

Steg för steg

Lägg starten i kön med avstånd 0. Ta noden längst fram. För varje granne som inte har setts: anteckna dess avstånd som ett mer än den aktuella nodens, minns den aktuella noden som vägen den nåddes från och lägg den längst bak i kön. Hoppa över grannar som redan setts. Upprepa tills kön är tom eller målet är nått.

Ett exempel

Ta en graf med kanterna A–B, A–C, B–D, C–D, C–E och D–F, och börja i A. När A tas ur kön hittas B och C på avstånd 1. B hittar D på avstånd 2. C ser att D redan är sedd och hittar E på avstånd 2. D hittar F på avstånd 3. E och F hittar inget nytt, och kön är tom. Följer man de sparade noderna bakåt från F får man F ← D ← B ← A, så en kortaste väg från A till F är A → B → D → F, tre kanter lång.

Varför avstånden stämmer

Varje nod på avstånd 1 kommer in i kön före varje nod på avstånd 2, varje nod på avstånd 2 före varje nod på avstånd 3, och så vidare, eftersom en nods grannar köas först när noden själv tas ur kön. Den första väg som når en nod har alltså minst antal kanter, och BFS behöver aldrig rätta ett avstånd. Varje nod tas en gång och varje kant granskas från båda ändarna, så arbetet växer med antalet noder plus antalet kanter.

Historia och användning

Konrad Zuse beskrev bredden-först-sökning 1945, i arbetet med sitt språk Plankalkül som inte publicerades förrän 1972. Edward F. Moore uppfann den på nytt 1959 för att hitta kortaste vägen ut ur en labyrint, och C. Y. Lee använde den 1961 för att dra ledningar på kretskort. I dag hittar den minsta antalet drag i pussel, graderna av separation i sociala nätverk, sidorna en sökrobot når först och närmaste lediga ruta i spel. När kanterna har längder generaliseras den av Dijkstras algoritm.

Konrad Zuse (i mitten, med glasögon) och Heinz Billing (till vänster) på mässan SYSTEMS ’91 i München. Zuse beskrev bredden-först-sökning 1945, i arbete med språket Plankalkül som inte publicerades förrän 1972.
Konrad Zuse (i mitten, med glasögon) och Heinz Billing (till vänster) på mässan SYSTEMS ’91 i München. Zuse beskrev bredden-först-sökning 1945, i arbete med språket Plankalkül som inte publicerades förrän 1972.

Utforska den

Öppna appen och tryck på Steg. Noden som besöks är markerad, noder som väntar i kön är blå och besökta noder är gröna, var och en med sitt avstånd. Kön visas under grafen, med den främsta först. Byt klicket till Mål och välj en nod för att stanna där och se den kortaste vägen, eller skapa en ny graf med fler noder och kanter.

Ofta ställda frågor

Vilken tidskomplexitet har BFS?

O(V + E) för V noder (vertices) och E kanter (edges): varje nod går in i och ut ur kön en gång, och varje kant granskas från båda ändarna. Den behöver O(V) extra minne för kön och avstånden.

Varför använder BFS en kö?

Eftersom först in, först ut håller noderna i den ordning de upptäcktes, och det är ordningen efter avstånd. Med en stack i stället skulle sökningen dyka på djupet först: det är djupet-först-sökning.

Kan BFS hitta kortaste vägar i viktade grafer?

Inte i allmänhet: den räknar kanter, inte deras längder. För viktade grafer utan negativa kanter, använd Dijkstras algoritm. Är varje vikt 0 eller 1 fungerar en variant som kallas 0-1 BFS.

Var används BFS?

För att lösa pussel och labyrinter med så få drag som möjligt, hitta vänners vänner i sociala nätverk, genomsöka webben nivå för nivå, sända broadcast i nätverk och som byggsten i andra algoritmer, till exempel för att hitta maximala flöden.

Redo att prova det?

Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.

Prova bredden-först-sökning