Bredden först-sökning (BFS)
Utforskar en graf lager för lager. En kö bestämmer vilken nod som står på tur, så de närmaste noderna besöks alltid först.
- O(V + E)
- minne O(V)
- kö
V och E: antalet noder (vertices) och kanter (edges). O(V + E) betyder att varje nod och varje kant hanteras ett fast antal gånger.
Kö: först in, först ut. BFS tar alltid den nod som har väntat längst.
Fler begrepp på sidan
- Nod: en punkt i grafen, här ritad som en cirkel med en bokstav.
- Kant: en linje som förbinder två noder. Här kan man gå längs den åt båda hållen.
- Grannar: de noder som är förbundna med en nod genom en kant. De granskas i bokstavsordning.
Prova det här: Välj grafen med två delar. Noderna som inte hänger ihop med starten nås aldrig.
Så fungerar det
BFS lägger startnoden i en kö. Sedan tar den, om och om igen, noden längst fram i kön och lägger dess nya grannar sist. En kö tar dem i den ordning de kom, så alla noder en kant bort blir klara innan någon nod två kanter bort. Talet bredvid en nod är dess avstånd från start: det minsta antalet kanter som behövs för att nå den.
När det är ett bra val
Använd BFS när du behöver den kortaste vägen i antal steg: minst antal drag i ett pussel, minst antal hopp i ett nätverk, personerna inom två kontakter från dig. I en stor graf kan kön bli lång, eftersom den rymmer ett helt lager på en gång.