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.
- tid O(V + E)
- minne O(V)
- använder en kö
Vad betyder det här?
- 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.
- Kö: först in, först ut. BFS tar alltid den nod som har väntat längst.
- Stack: sist in, först ut. DFS fortsätter alltid från den nod den nådde sist.
- 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.
- i kön
- aktuell
- klar
- kant i sökträdet
- överhoppad kant
Börja i A. Tryck på Spela upp eller stega igenom sökningen.
Blanksteg: spela upp eller pausa. Vänster och höger pil: steg. Home och End: hoppa.
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.