Paghahanap na luwang-muna

Paghahanap na luwang-muna

Order in which the nodes get expanded Order in which the nodes are expanded
Class	Search algorithm
Data structure	Graph
Worst case performance	$O(|V|+|E|)=O(b^{d})$
Worst case space complexity	$O(|V|)=O(b^{d})$

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.

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.

Algoritmo (inpormal)

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

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