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 11. 12. 2010 11:29
Vhodná reprezentácia grafu
Rozmýšľam nad najefektívnejšou reprezentáciou grafu, pre túto úlohu.
Medzi N mestami označenými číslami 1 .. N jazdí niekoľko autobusových liniek.
Sú dané trasy týchto liniek ako zoznamy čísel miest, v ktorých sa jednotlivé linky zastavia.
Všetky autobusové linky sú prevádzkované v oboch smeroch po rovnakej trase.
a) Nájdite a vypíšte všetky mestá, do ktorých sa dá dostať z mesta číslo 1 bez ohľadu
na počet presadaní.
b) Nájdite a vypíšte všetky mestá, do ktorých sa dá dostať z mesta číslo 1 maximálne
s dvoma presadaniami.
Osobne zvažujem zoznam hrán, zoznam susedov alebo reprezentovať to dynamicky.
Aký máte návrh? Dík.
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 11. 12. 2010 17:56
Re: Vhodná reprezentácia grafu
Asi áno ... a bude ale treba ešte odlíšiť, ktoré vrcholy patria do ktorej trasy.
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
#4 18. 12. 2010 17:53
Re: Vhodná reprezentácia grafu
Tak mi napadlo ešte ...
Keď mám graf zadaný zoznamom hrán a chcem ho reprezentovať zoznamom susedov.
Ja som to robil tak, že prosto načítam hrany a potom v nich potupne vyhľadávam a budujem zoznam susedov. Lenže to mi príde nejak pamäťovo príliš náročné a nepraktické. Ale nenapadá mi ako to zostrojiť priamo počas čítania hrán (teda napadá ale tiež je to časovo náročné). Nejaké nápady? Ďakujem.
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