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 06. 04. 2011 20:29
Algoritmus na hledání spojitosti grafu
Ahoj. Jaký nejefektivnější algoritmus existuje na hledání spojitosti v neorientovaném grafu? Zajímá mne pouze jestli se mohu z libovolného bodu dostat do libovolného jiného (nikoliv délka cesty apod.). Existuje něco rychlejšího než DFS?
Offline
#2 07. 04. 2011 17:56
- check_drummer
- Příspěvky: 5513
- Reputace: 106
Re: Algoritmus na hledání spojitosti grafu
Jak rychlý je DFS?
"Máte úhel beta." "No to nemám."
Offline
#4 14. 04. 2011 15:22
Re: Algoritmus na hledání spojitosti grafu
↑ check_drummer:
Prehľadávanie do hĺbky je lineárne s počtom vrcholov a hrán grafu.
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
#5 14. 04. 2011 15:22
Re: Algoritmus na hledání spojitosti grafu
↑ vasek125:
DFS alebo BFS.
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
#6 14. 04. 2011 17:26
- check_drummer
- Příspěvky: 5513
- Reputace: 106
Re: Algoritmus na hledání spojitosti grafu
↑ pizet:
Přesně tak - jak tedy potom hledat rychlejší algoritmus? Ten rychlejší by tedy musel nutně nějaké hrany ignorovat - otázka je, zda lze navrhnout nějakou datovou strukturu, která by toto umožňovalka - ale čas na její zbudování by stejně musel každou hranu "otestovat".
Takže: jakým způsobem je daný graf zadán?
"Máte úhel beta." "No to nemám."
Offline
#7 15. 04. 2011 13:56 Příspěvek uživatele pizet byl skryt uživatelem pizet. Důvod: Hlúposť.
#8 15. 04. 2011 20:21
- check_drummer
- Příspěvky: 5513
- Reputace: 106
Re: Algoritmus na hledání spojitosti grafu
↑ pizet:
To určitě ne. Vezměme si graf na 2n vrcholech tvořený dvěma disjunktními úplnými grafy na n vrcholech. Jistě máme více než n-1 hran, každý vrchol má stupeň aspoň jedna a graf není souvislý...
"Máte úhel beta." "No to nemám."
Offline