Meklēšana plašumā
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.
Virsotņu apstaigāšanas secība | |
Klase | Meklēšanas algoritms |
---|---|
Datu struktūra | Grafs |
Sliktākā ātrdarbība | |
Sliktākais atmiņas patēriņš | |
Optimāls | jā (grafiem bez svariem) |
Pilnīgs | jā |
Neformāls algoritms
labot šo sadaļu- Pievieno rindai saknes virsotni
- 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.
- Ja rinda ir tukša, visas virsotnes grafā jau ir apskatītas — beidz meklēšanu un atgriež "nav atrasts".
- 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ļu1 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
Šis ar informācijas tehnoloģijām saistītais raksts ir nepilnīgs. Jūs varat dot savu ieguldījumu Vikipēdijā, papildinot to. |