search

jaanos / or-zbirka

Zbirka nalog iz Operacijskih raziskav
https://jaanos.github.io/or-zbirka/
Creative Commons Attribution 4.0 International
1 stars 11 forks source link

resena naloga 5.41 #24

Closed kuco23 closed 5 years ago

kuco23 commented 5 years ago

Dfs funkcije nisem moral klicati, saj za argument ne sprejme točke v kateri se algoritem začne

jaanos commented 5 years ago

Sem zdaj priredil funkcijo dfs tako, da sprejme še množico začetnih vozlišč. Prosil bi, če algoritem napišeš tako, da bo uporabljal to funkcijo.

Naj opomnim še, da naloga eksplicitno pove, da je vhodni graf neusmerjen, tako da naj tudi zapisani algoritem tako deluje. Najlažje bo, če v Visit obravnavaš povratne povezave - če torej najdeš e kot povratno povezavo, ali pa najdeš povratno povezavo do začetnega vozlišča iz veje, ki vsebuje e, potem si našel iskani cikel.

kuco23 commented 5 years ago

Bi bilo mogoče lažje, če bi definiral graf G', kot G \ {e} in iskal pot med začetno in končno točko povezave e v G' z dfs preko Visit?

jaanos commented 5 years ago

Tudi lahko.

jaanos commented 5 years ago

Najlepša hvala!