breddenförsttraversering

Breddenförsttraversering är en graftraverseringsalgoritm som utförs på grafer och träd där målet är att utforska noderna i stigande avstånd från en given startnod. Algoritmen besöker först startnoden, därefter alla dess omedelbara grannar, sedan grannarna till dessa och så vidare.

Algoritmen använder en kö (FIFO). Startnoden markeras som besökt och placeras i kön. Så länge kön inte är tom hämtas en nod, processeras och för varje granne som inte tidigare besökts markeras den som besökt och placeras i kön. Om man vill kunna rekonstruera vägar lagras även oftast en föregångare.

Tidsmässigt har en grov kostnad O(V+E) i en graf med V noder och E kanter. Minnesmässigt krävs vanligtvis O(V) plats för kö och besökta-markeringar. Vid användning av en adjacency-matris ökar tiden till O(V^2) medan minnesbehovet kan öka till O(V^2).

Användningsområden inkluderar att hitta kortaste stig i obelagda grafer, avgöra kopplingskomponenter samt utföra nivåordnad traversering i träd. Den används även inom nätverksteknik, web crawlers och i sociala nätverk för att hitta användare eller objekt på viss distans från en given nod.

Relaterade metoder är bland annat bidirektionell breddenförsttraversering, där sökningen startar från både start- och målnod och möts i mitten, samt varianter som anpassar BFS för riktade eller icke- konfligoterade grafer. Breddenförsttraversering utgör en grundläggande algoritm inom grafteori och relaterade områden.