Paieška į plotį

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.
Peršokti į: navigaciją, paiešką
Paieška į plotį
Animacija, iliustruojanti paiešką į plotį

Paieška į plotį (angl. breadth-first search, angl. BFS) – paieškos grafe arba grafo apėjimo būdas, kai pasirinkus pradinę viršūnę pirmiausia yra aplankomos visos jos kaimynės (t. y., viršūnės, sujungtos grafo briaunomis su pradine viršūne), po to kaimynių kaimynės ir t. t., kol randamas ieškomas tikslas arba kol yra apeinamos visos grafo viršūnės ir briaunos.

Algoritmas[taisyti | redaguoti kodą]

Paieška į plotį gali būti realizuojama naudojant eilę. Tokiu atveju iš pradžių į eilę įtraukiama pasirinkta viršūnė, nuo kurios vykdoma paieška. Po to kiekviename žingsnyje iš eilės imama viršūnė ir į eilę dedamos jai gretimos neaplankytos viršūnės. Tai kartojama, kol eilė lieka tuščia.[1]

Pseudokodu, paremtu Pascal programavimo kalba, tai užrašoma taip:

TrauktiĮEilę(Eilė, PradinėViršūnė);
PažymėtiKaipAplankytą(PradinėViršūnė); // pažymi aplankytą viršūnę
while (NeTuščia(Eilė)) do
begin
	w := ImtiIšEilės(Eilė); // Nuskaitomas ir išmetamas pirmas eilės elementas
	for u := visoms neaplankytoms viršūnėms, gretimoms w do
	begin
		PažymėtiKaipAplankytą(u);
		TrauktiĮEilę(Eilė, u);
	end
end

Taikymai[taisyti | redaguoti kodą]

Paieška į plotį galima rasti trumpiausius kelius nuo pasirinktos viršūnės nesvoriniame grafe.[1]

Išnašos[taisyti | redaguoti kodą]

  1. 1,0 1,1 Kostas Plukas, Eugenijus Mačikėnas, Birutė Jarašiūnienė, Irena Mikuckienė „Taikomoji diskrečioji matematika“, Kaunas, „Technologija“, 2007

Išorinės nuorodos[taisyti | redaguoti kodą]

Commons-logo.svg Vikiteka: Paieška į plotį – vaizdinė ir garsinė medžiaga

Vikiteka