Amint tanultuk, a mélységi bejárás (DFS) alkalmas annak eldöntésére hogy egy irányított gráf körmentes-e (azaz DAG)
a következő állítás miatt.
Legyen \(G = (V, E)\) egy irányított gráf. Ekkor \(G\) akkor és csak akkor DAG, ha a mélységi bejárása során nincs visszaél.
A feladat egy olyan Python program írása, mely a fenti (és a jegyzetben
is vázolt) módon DFS segítségével eldönti egy adott összefüggő irányított gráfról, hogy DAG-e.
Ehhez először keresni kell egy csúcsot amibe nem futnak be élek. Ha nincs ilyen, akkor a gráf biztos hogy nem körmentes.
Ezután az így megtalált gyökérből indítsunk egy mélységi bejárást, és nézzük meg hogy keletkezik-e visszaél.
A feltöltendő fájl neve dag.py legyen.
A program a bemenetet parancssori argumentum formájában kapja
meg a következő módon:
python3 dag.py graph.text
Az első argumentum (a
példában graph.text)
egy összefüggő, irányított egyszerű gráf, amit a következő módon
adunk meg egy szöveges
(.text) fájlban:
A fájl első sorában az \(N\), \(M\) természetes számok
találhatóak szóközökkel elválasztva, ahol
a \(G = (V, E)\) egyszerű gráf csúcsainak halmaza \(V =
\{0, 1, 2, \ldots, N-1\}\),
az élek száma \(\left| E \right| = M\).
A fájl további \(M\) sora rendre \(U_i\), \(V_i\)
számpárokat tartalmaz. Egy ilyen számpár megfelel egy \(\{U_i,
V_i\} \in E\) irányított élnek. Egy él csak egyszer szerepel
a fájlban.
A bemenet feldolgozására javasoljuk a 3. feladat
gráf beolvasó függvényének módosítását. Figyeljünk arra, hogy
most a fájl első sorában nem szerepelnek az \(S\) és \(T\)
csúcsok.
Amennyiben a gráf DAG, a
DAG
amennyiben nem, akkor a
Nem DAG
szöveget írjuk ki a terminálra.
Próbáljuk ki az elkészült programot
a graph1.text (DAG)
és graph2.text (nem DAG)
bemenetekre, de teszteljük más, saját készítésű teszbemeneteken
is!