Matematické Fórum
Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.
Nástěnka
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.
Nejste přihlášen(a). Přihlásit
#1 05. 06. 2012 19:14
Prehladavanie orientovaneho grafu BFS,DFS
Ahoj, nikde neviem zrozumitelne najst algoritmus na prechadzanie orientovaneho grafu , ci uz do hlbky alebo do sirky....
http://img855.imageshack.us/img855/3204/beznzvubj.png
Preco napr. neexistuje postupnost abcfed pri prehl. do sirky?
Ved idem A, B, C, šipka vedie aj do F , takze A B C F a potom by som sa vratil do najblizsieho uzli cize ABCFE a posledny tiez ziskam vratenim ABCFED...
Mohol by mi niekto napisat ake podmienky musi BFS a DFS prehladavanie splnat?
Na internete som to nikde nenasiel zrozumitelne...
Vdaka
Offline
#2 05. 06. 2012 19:42
Re: Prehladavanie orientovaneho grafu BFS,DFS
↑ milwoukee:
Skus sa pozriet na http://ksp.mff.cuni.cz/tasks/20/cook3.html
Do you follow my way? Or you just see a black stain swimming in the Milky Way ...
KSP je určený pre študentov základných a stredných škôl, ktorí majú záujem naučiť sa niečo z oblasti algoritmov, logických úloh, programovania a informatiky.
Offline
#3 05. 06. 2012 20:39
Re: Prehladavanie orientovaneho grafu BFS,DFS
↑ pizet:
Je tam dost toho ale uplne som to aj tak nepochytil. Chyba mi tam vecny priklad.
Hodim sem svoj postup, ktory je isto zle. 
Moj postup -> A (trivialne - koren)
B (mam na vyber z B a C)
C (jedina moznost),
F ( B,C mam vycerpane, preto zacinam dalsi "riadok", a kedze do F
. ide z C sipka, mozem pokracovat Fkom)
E (z F nemam sipku preto sa vraciam po C kde mam dalsiu moznost E)
D opat sa vratim o jeden uzol a mozem ist do D sipkou
Offline
#6 06. 06. 2012 19:00 — Editoval jindra (06. 06. 2012 19:03)
Re: Prehladavanie orientovaneho grafu BFS,DFS
Trochu to motáš, teď píšeš o prohledávání do šířky a předtím jsi psal o vracení se. Při prohledávání do šířky se nevracíš. Proto jsem myslel že používáš prohledávání do hloubky a tím pádem by c nebyla jediná možnost.
Pakliže používáš do šířky, tak máš svůj postup jen o kousek špatně bylo by to:
a
b
c
d
e
f
Jde o to že jak přijdeš do vrcholu, hodíš jeho následníky do fronty a vždy bereš první z fronty, takže když dáš do fronty b c tak první na řadu přijdou potomci uzlu b a teprve pak uzlu c.
edit: aby to bylo srozumitelnější.
Offline