bredenförstsökning

Breddenförstsökning, oftast benämnd BFS, är en algoritm för att genomgå en graf eller ett träd. Den börjar vid en valfri startnod och utforskar noderna vågvis: först startnoden, därefter alla dess grannar, sedan deras grannar, och så vidare. På så sätt rör sig algoritmen nivå för nivå genom grafen.

Algoritmen använder en kö (FIFO) för att hålla de noder som ska besökas härnäst. Startnoden markeras som besökt och får ett referensvärde till sin föregångare. Därefter upprepas: ta första nod ur könet, besök dess ovisitade grannar, markera dem som besökta, sätt deras föregångare till den aktuella noden och lägg dem i kön.

Breddenförstsökning ger ofta kortaste vägen i en obelastad graf, uttryckt som färden i antal kanter mellan start och mål. Den är dessutom ett verktyg för att hitta anslutna komponenter i en graf och används i olika nivåbaserade sök- och kartläggningsuppgifter inom nätverk, spel, artificiell intelligens och webbsökning.

Komplexitet: i en graf representerad med en lista över grannar är tidskomplexiteten O(V+E) och minnesanvändningen O(V). Om grafen representeras med en adjacensmatris blir tidskomplexiteten O(V^2). Allmänt kräver BFS minne för att hålla alla noder i vyn och för att markera besökta noder.

Begränsningar: BFS är optimal för obelastade grafer, men för vikta grafer används andra algoritmer (som Dijkstra eller Bellman–Ford) för att hitta faktiskt kortaste vägar. Varianter inkluderar bidirekts BFS som inhämtar snabbare sökningar genom att söka från både start- och mål-nod.