Utolsó módosítás: 2016.11.17.
Hozzuk létre az absztrakt Graph ősosztályt. Rendelkezzen az alábbi absztrakt metódusokkal, melyek megvalósítását a származtatott osztályok végzik el.
Egy boolean visszatérésű hasEdge() függvény, ami két int típusú paramétert kap. Akkor tér vissza igazzal, ha létezik él az első paraméterrel jelzett csúcsból a második paraméterrel jelzett csúcsba.
Egy számok halmazát visszaadó edgesFrom() függvény, amely megadja, hogy a paraméterként kapott csúcsból mely csúcsok érhetőek el.
Egy addEdge() függény, amely a gráfhoz hozzáad egy új élt az első paraméterként kapott csúcsból a második csúcsba.
Hozzuk létre a Graph leszármazottját, a sűrű gráfok ábrázolásában hatékony DenseGraph osztályt.
Az élek jelenlétét tároljuk egy logikai értékeket tartalmazó mátrixban. Ha az i, j koordinátákon true érték van tárolva, akkor az i-ből van j-be él.
Az osztálynak legyen egy konstruktora, ami megkapja a csúcsok számát. Ezek után a csúcsokat \([0 \dots n-1]\) számok reprezentálják. A csúcsok a későbbiekben már nem bővíthetők, de éleket majd hozzáadhatunk a gráfhoz.
Implementáljuk le a hasEdge(), edgesFrom() és addEdge() függvényeket ennek megfelelően.
A Graph osztályban hozzunk létre egy depthFirstTraversal() függvényt, ami a paraméterként kapott csúcsból indulva mélységi bejárást végez, és a meglátogatott csúcsokat egy listában adja vissza.
Ehhez használjunk stack-ként egy láncolt listát és legyen még egy láncolt lista, amiben számon tartjuk, hogy mely csúcsokat jártuk be (ez lesz a végeredmény).
Kezdetben a stack-ben egy elem van, az a csúcs, amiből a bejárás kiindul.
Minden egyes iterációban kivesszük a verem első elemét. Ha ez az elem még nem szerepel a bejárt csúcsok listájában (most találjuk meg először), akkor beletesszük. Megnézzük a kivett elemből egy éllel elérhető összes elemet, és amit még nem jártunk be, azt betesszük a verembe.
A bejárás addig megy, amíg a stack nem üres.
Hozzuk létre a Graph másik leszármazottját, a SparseGraph-ot, amely a ritka gráfok tárolására optimális. Az éleket tároljuk egy gyorsan indexelhető java.util.ArrayList-ben, ennek minden eleme egy java.util.Set, amiben benne vannak azok a csúcsok amelyek az adott sorszámú csúcsból elérhetők.
Implementáljuk le a hasEdge(), edgesFrom() és addEdge() függvényeket ennek megfelelően. Konstruktor legyen az előző ábrázoláshoz hasonló.
Megoldásunk teszteléséhez írjunk egy Main osztályt. Az osztály négy parancssori paramétert kap (a paraméterek helyességét nem kell ellenőrizni):
a gráf típusa (sparse vagy dense)
a csúcsok száma
az élek listája: élek szóköz nélkül vesszővel elválasztva, ahol egy élt csúcs1-csúcs2 alakban adunk meg
a mélységi bejárást melyik csúcsból indítjuk
A program hozza létre a megfelelő gráfot, adja hozzá az éleket, majd végezzen mélységi bejárást a megadott csúcsból és írja ki ennek eredményét. Példák:
$ java Main sparse 4 0-1,1-3,0-2,2-3 0
[0, 2, 3, 1]
$ java Main dense 4 0-1,1-3,0-2,2-3 0
[0, 2, 3, 1]