Meklēšana plašumā

Grafu teorijā meklēšana plašumā (Veidne:Val, BFS) ir grafu meklēšanas algoritms, kas, sākot no saknes virsotnes, apstaigā visas kaimiņu virsotnes. Pēc tam katrai no šīm tuvākajām virsotnēm tas apstaigā tās neapmeklētās kaimiņu virsotnes līdz sasniedz mērķi.

Neformāls algoritms

1. Pievieno rindai saknes virsotni
2. Atvieno no rindas virsotni un pārbauda to.
   • Ja meklētais elements ir atrasts šajā virsotnē, beidz meklēšanu un atgriež rezultātu.
   • Citādi pievieno rindai nākamās virsotnes (tiešos bērnus), kuri vēl nav apskatīti.
3. Ja rinda ir tukša, visas virsotnes grafā jau ir apskatītas — beidz meklēšanu un atgriež "nav atrasts".
4. Ja rinda nav tukša, atkārto 2. soli.

Piezīme: Ja rindas vietā izmanto steku, algoritms kļūst par meklēšanu dziļumā.

Pseidokods

1  procedure BFS(Graph, source):
2      create a queue Q
3      enqueue source onto Q
4      mark source
5      while Q is not empty:
6          dequeue an item from Q into v and mark v
7          for each edge e incident on v in Graph:
8              let w be the other end of e
9              if w is not marked:
10                  enqueue w onto Q