Meklēšana plašumā (grafu teorija)

Meklēšana plašumā

Mezglu 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, kurš, sākot no saknes mezgla, apstaigā visus kaimiņu mezglus. Pēc tam katram no šiem tuvākajiem mezgliem tas apstaigā to neapmeklētos kaimiņu mezglus, līdz sasniedz mērķi.

Neformāls algoritms

1. Pievieno rindai saknes mezglu
2. Atvieno no rindas mezglu un pārbauda to.
   • Ja meklētais elements ir atrasts šajā mezglā, beidz meklēšanu un atgriež rezultātu.
   • Citādi pievieno rindai nākamos mezglus (tiešos bērnus), kuri vēl nav apskatīti.
3. Ja rinda ir tukša, visi mezgli grafā jau ir apskatīti – 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