Iskanje v širino

Iz MaFiRaWiki

Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili.

Kaj pomeni to opozorilo?

Iskanje v širino je eno najpreprostejših iskanj po grafu. Reče se mu tudi "Breadth first search" (BFS). Iskanje v širino običajno implementiramo z vrsto. (najdena vozlišča dodajamo na koncu v vrsto, pregledujemo pa prva v vrsti). Časovna zahtevnost je O(V+E). Začnemo v nekem vozlišču s in najprej poiščemo vse njegove sosede. Potem od vsakega najdenega soseda poiščemo njegove sosede, vozlišča ki jih nismo našli v prvem koraku. Nadaljujemo, dokler ne najdemo ciljnega (željenega) vozlišča ali pa ne preiščemo vsega grafa.

Iskanje implementiramo tako, da vozlišča razdelimo v tri skupine: pregledana, odprta oz. najdena (imamo jih v vrsti) in nepregledana. Nepregledana vozlišča dodajamo v vrsto odprtih vozlišč, ko pa odprto vozlišče izločimo iz vrste, ga spremenimo v pregledano.

Zgledi

Primer je epidemija (biološkega ali računalniškega virusa).

Glej tudi

Osebna orodja