Meklēšana plašumā

Meklēšana plašumā

Virsotņu apstaigāšanas secība Virsotņu apstaigāšanas secība
Klase	Meklēšanas algoritms
Datu struktūra	Grafs
Sliktākā ātrdarbība	$O(|V|+|E|)=O(b^{d})$
Sliktākais atmiņas patēriņš	$O(|V|+|E|)=O(b^{d})$
Optimāls	jā (grafiem bez svariem)
Pilnīgs	jā

Grafu teorijā meklēšana plašumā (angļu: breadth-first search, 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