Paieška į plotį

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.

Paieška į plotį (angl. Breadth-first search ar BFS) – grafo apėjimo metodas. Pagrindinis principas – aplankius viršūnę ‘v’, aplankome visas viršūnes kaimynines ‘v’. Tokiu būdu apėjimas neprasidės iš jokios kitos viršūnės kaimyninės ‘v’, kol nėra aplankytos visos galimos kaimyninės viršūnės. Pastebėkime, kad paieškos į plotį atveju nėra rekursyvios realizacijos.

Paieška į plotį
Paieška į plotį

Pavyzdys pseudokodu (Q – eilė)

Add(Q, v) //įdedame viršūnę V į eilę
MarkV(v) // pažymi aplankytą viršūnę
While (not IsEmpty(Q)) do
begin
        w:= Get(Q) // Nuskaitomas ir išmetamas pirmas eilės elementas
        for visoms w kaimynems u do
        begin
                MarkV(u)
                Add(Q, u)
        End
end