Informatika1-2011/Hazi4
A MathWikiből
(Változatok közti eltérés)
Ador (vitalap | szerkesztései) |
Ador (vitalap | szerkesztései) |
||
| 4. sor: | 4. sor: | ||
Segítség: | Segítség: | ||
| − | * egy ''gr'' nevű irányított gráf egy csúcsának | + | * 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 | + | * 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 | * nem elég a bejárt csúcsokat megjegyezni, a bejárt éleket is számon kell tartani | ||
A lap 2011. október 3., 23:18-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
