Paghahanap na luwang-muna

(Idinirekta mula sa Breadth-first search)

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.

Paghahanap na luwang-muna
Order in which the nodes get expanded
Order in which the nodes get expanded
Order in which the nodes are expanded
ClassSearch algorithm
Data structureGraph
Worst case performance
Worst case space complexity
Isang halimbawang mapa ng Alemanya na may ilang mga koneksiyon sa pagitan ng mga siyudad.
Ang puno na luwang-muna na nakuha kung patatakbuhin ang algoritmong BFS sa ibinigay na mapa at magsisimula sa siyudad ng Frankfurt.
Animadong(animated) halimbawa ng isang paghahanap na luwang-muna.

Padron:Tree search algorithm

Algoritmo (inpormal)

baguhin
  1. I-enqueue ang ugat na nodo
  2. 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.
  3. Kung ang queue ay walang laman, ang bawat nodo sa grapo ay nasiyasat na – itigil na ang paghahanap at ibalik ang "hindi natagpuan".
  4. 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

baguhin

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