Informatika1-2011/Hazi4
A MathWikiből
(Változatok közti eltérés)
Ador (vitalap | szerkesztései) |
Ador (vitalap | szerkesztései) |
||
| 6. sor: | 6. sor: | ||
* egy ''gr'' nevű irányított gráf egy csúcsának ki-éleit a ''gr.neighbors_out(csúcs)'' függvénnyel kaphatod meg egy listában, a be-éleket a ''gr.neighbors_in(csúcs)'' függvénnyel | * egy ''gr'' nevű irányított gráf egy csúcsának ki-éleit a ''gr.neighbors_out(csúcs)'' függvénnyel kaphatod meg egy listában, a be-éleket a ''gr.neighbors_in(csúcs)'' függvénnyel | ||
* az algoritmus a DFS egy változata lesz (gondolj arra hogy ha egy fát járunk be DFS-sel, az miben különbözik attól ha a gráf nem fa) | * az algoritmus a DFS egy változata lesz (gondolj arra hogy ha egy fát járunk be DFS-sel, az miben különbözik attól ha a gráf nem fa) | ||
| − | * nem elég a bejárt csúcsokat megjegyezni, a bejárt éleket is számon kell tartani | + | * <p style="text-decoration:line-through;"> nem elég a bejárt csúcsokat megjegyezni, a bejárt éleket is számon kell tartani </p> |
| + | * Javítás: nem elég a bejárt csúcsokat megjegyezni, azt is külön számon kell tartani hogy mely csúcsok vannak még "feldolgozás alatt", és mik azok amelyek már "kész vannak" (már visszaléptünk belőlük a bejárás során). | ||
A lap jelenlegi, 2011. október 12., 10:39-kori változata
Írj Sage függvényt, ami megmondja, hogy van-e irányított kör egy irányított gráfban!
Használd a digraphs.RandomDirectedGNP(<csúcsszám>, <él-valószínűség>) függvényt a teszteléshez használható gráfok létrehozásához.
Segítség:
- egy gr nevű irányított gráf egy csúcsának ki-éleit a gr.neighbors_out(csúcs) függvénnyel kaphatod meg egy listában, a be-éleket a gr.neighbors_in(csúcs) függvénnyel
- az algoritmus a DFS egy változata lesz (gondolj arra hogy ha egy fát járunk be DFS-sel, az miben különbözik attól ha a gráf nem fa)
-
nem elég a bejárt csúcsokat megjegyezni, a bejárt éleket is számon kell tartani
- Javítás: nem elég a bejárt csúcsokat megjegyezni, azt is külön számon kell tartani hogy mely csúcsok vannak még "feldolgozás alatt", és mik azok amelyek már "kész vannak" (már visszaléptünk belőlük a bejárás során).
