Informatika1-2013/HF4

A MathWikiből

Í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, 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).
Személyes eszközök