Pregled grafa v širino

Iz MaFiRaWiki

GFDL Avtor tega članka je študent/ka TinaHozjan.

Pripravil/a ga je pri predmetu Računalništvo 2 (FMF PRA).


Kljub temu ste vsi vabljeni k urejanju in popravkom, saj je bistvo wikija ravno v sodelovalnem delu.

Pregled grafa v širino je algoritem, s katerim pregledamo vozlišča grafa.

Najprej obiščemo vse sosede vozlišča u, šele nato gremo na naslednje vozlišče.

Če je graf nepovezan, tvorijo v enem prehodu obiskana vozlišča povezano komponento grafa G. Za pregled celotnega nepovezanega grafa je potrebno po vsakem prehodu izmed neobiskanih vozlišč izbrati naslednje izhodišče za iskanje. To ponavljamo dokler niso obiskana vsa vozlišča v G.


Primer


Vrstni red obiskov: 1, 2, 3, 4, 7, 5, 6

Glej tudi

Osebna orodja