Meklēšana plašumā

Vikipēdijas raksts
Pārlēkt uz: navigācija, meklēt
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

Grafu teorijā meklēšana plašumā (angļu: breadth-first search, BFS) ir grafu meklēšanas algoritms, kurš, sākot no saknes virsotnes, apstaigā visus kaimiņu virsotnes. Pēc tam katrai no šiem tuvākajām virsotnēm tas apstaigā tās neapmeklētās kaimiņu virsotnes, līdz sasniedz mērķi.

Neformāls algoritms[labot šo sadaļu | labot pirmkodu]

  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[labot šo sadaļu | labot pirmkodu]

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