Paghahanap na luwang-muna

Sa teoriya ng grapo, ang (Ingles: breadth-first search o BFS) ay isang algoritmo ng paghahanap ng grapo na nagmumula sa ugat na nodo(root node) at gumagalugad(explore) sa lahat ng mga kapitbahay na nodo. Sa bawat naman mga pinakamalapit na nodong ito, ito ay gumagalugad sa mga hindi pa nagagalugad na mga nodong kapitbahay at iba pa hanggang sa mahanap ang layuning(goal) nodo. 


 Algoritmo (inpormal) 
 I-enqueue ang ugat na nodo
 I-dequeue ang isang nodo at siyasatin ito 
 Kung ang elementong hinahanap ay natagpuan sa nodong ito, itigil ang paghahanap at ibalik ang resulta. 
 Kung hindi, i-enqueue ang anumang kahalili(successors) na mga direktang anak na mga nodo na hindi pa natutuklasan.
 Kung ang queue ay walang laman, ang bawat nodo sa grapo ay nasiyasat na – itigil na ang paghahanap at ibalik ang "hindi natagpuan". 
 Kung ang queue ay hindi walang laman, ulitin mula sa hakbang 2. 

Komento: Ang paggamit ng stack imbis na queue ay gagawa sa algoritmong ito na isang paghahanap na lalim-muna.

 Sudokodigo 
Input: Isang grapong G at isang ugat na v ng G

 1  procedure BFS(G,v):
 2      create a queue Q
 3      enqueue v onto Q
 4      mark v
 5      while Q is not empty:
 6          t ← Q.dequeue()
 7          if t is what we are looking for:
 8              return t
 9          for all edges e in G.incidentEdges(t) do
 10             o ← G.opposite(t,e)
 11             if o is not marked:
 12                  mark o

Kategorya:Mga algoritmo ng paghahanap
Kategorya:Mga algoritmo ng grapo