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.
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