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 aplankyti visos galimos kaimyninės viršūnės. Pastebėkime, kad BFS atveju nėra rekursyvios realizacijos.

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

Pavyzdys presudokodu (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