Pregled grafa v globino

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 globino je algoritem, s katerim pregledamo vsa vozlišča danega grafa.

Naj bo u neko vozlišče, ki smo ga že obiskali in v njegov sosed, ki ga še nismo obiskali. Obiščemo v in ponovimo postopek od tega vozlišča naprej. Ko pridemo do vozlišča z, katerega vsi sosedje so že obiskani, se vrnemo nazaj po isti poti in obiščemo prvega naslednjega še neobiskanega soseda nekega prejšnjega vozlišča.

Če je graf predstavljen s seznamom sosednosti, prehodimo seznam natanko enkrat. Ker je v seznamu 2*e vozlišč (e - povezava), je časovna zahtevnost algoritma O(e). Če pa je graf predstavljen z matriko sosednosti, pregledamo vse elemente matrike. Torej je časovna zahtevnost algoritma O(n^2).

Č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, 4, 5, 6, 7, 3

Glej tudi

Osebna orodja