T´ ema
Megval´ os´ıt´ as
Fejleszt´ esi lehet˝ os´ egek
Gr´afalgoritmusok ´es hat´ekony adatszerkezetek szeml´eltet´ese K´esz´ıtette: Bogn´ar Gerg˝ o T´emavezet˝ o: Veszpr´emi Anna E¨ otv¨ os Lor´ and Tudom´ anyegyetem Informatikai Kar Algoritmusok ´ es Alkalmaz´ asaik Tansz´ ek
Budapest, 2012.
Bogn´ ar Gerg˝ o, t´ emavezet˝ o: Veszpr´ emi Anna
Gr´ afalgoritmusok ´ es hat´ ekony adatszerkezetek szeml´ eltet´ ese
T´ ema
Megval´ os´ıt´ as
Fejleszt´ esi lehet˝ os´ egek
A dolgozat t´em´aja Gr´afalgoritmusok P´aros gr´afok ´es maxim´alis p´aros´ıt´as Minim´alis k¨olts´eg˝ u fesz´ıt˝ ofa illetve fesz´ıt˝ o erd˝o keres´es Grafikus fel¨ ulet Gr´af megjelen´ıt´es, szerkeszt´es Algoritmus szeml´eltet´es Adatszerkezetek bemutat´asa C´elkit˝ uz´es Szeml´eltet´es, bemutat´as Tanul´asi seg´edeszk¨ oz Bogn´ ar Gerg˝ o, t´ emavezet˝ o: Veszpr´ emi Anna
Gr´ afalgoritmusok ´ es hat´ ekony adatszerkezetek szeml´ eltet´ ese
T´ ema
Megval´ os´ıt´ as
Fejleszt´ esi lehet˝ os´ egek
A dolgozat t´em´aja Gr´afalgoritmusok P´aros gr´afok ´es maxim´alis p´aros´ıt´as Minim´alis k¨olts´eg˝ u fesz´ıt˝ ofa illetve fesz´ıt˝ o erd˝o keres´es Grafikus fel¨ ulet Gr´af megjelen´ıt´es, szerkeszt´es Algoritmus szeml´eltet´es Adatszerkezetek bemutat´asa C´elkit˝ uz´es Szeml´eltet´es, bemutat´as Tanul´asi seg´edeszk¨ oz Bogn´ ar Gerg˝ o, t´ emavezet˝ o: Veszpr´ emi Anna
Gr´ afalgoritmusok ´ es hat´ ekony adatszerkezetek szeml´ eltet´ ese
T´ ema
Megval´ os´ıt´ as
Fejleszt´ esi lehet˝ os´ egek
A dolgozat t´em´aja Gr´afalgoritmusok P´aros gr´afok ´es maxim´alis p´aros´ıt´as Minim´alis k¨olts´eg˝ u fesz´ıt˝ ofa illetve fesz´ıt˝ o erd˝o keres´es Grafikus fel¨ ulet Gr´af megjelen´ıt´es, szerkeszt´es Algoritmus szeml´eltet´es Adatszerkezetek bemutat´asa C´elkit˝ uz´es Szeml´eltet´es, bemutat´as Tanul´asi seg´edeszk¨ oz Bogn´ ar Gerg˝ o, t´ emavezet˝ o: Veszpr´ emi Anna
Gr´ afalgoritmusok ´ es hat´ ekony adatszerkezetek szeml´ eltet´ ese
T´ ema
Megval´ os´ıt´ as
Fejleszt´ esi lehet˝ os´ egek
P´aros gr´afok t´emak¨or P´aross´ag vizsg´alata Cs´ ucsok feloszt´asa, pirosra ´es k´ekre sz´ınez´ese Alapja: sz´eless´egi bej´ar´as Sor adatszerkezet Magyar m´odszer Maxim´alis p´aros´ıt´as keres´ese p´aros gr´afban ¨ Otlet: p´aros´ıt´as n¨ ovel´ese jav´ıt´ ou ´ttal Altern´al´o erd˝o ´ep´ıt´es Sz´eless´egi bej´ar´as speci´alis alkalmaz´asa Sor adatszerkezet
Bogn´ ar Gerg˝ o, t´ emavezet˝ o: Veszpr´ emi Anna
Gr´ afalgoritmusok ´ es hat´ ekony adatszerkezetek szeml´ eltet´ ese
T´ ema
Megval´ os´ıt´ as
Fejleszt´ esi lehet˝ os´ egek
P´aros gr´afok t´emak¨or P´aross´ag vizsg´alata Cs´ ucsok feloszt´asa, pirosra ´es k´ekre sz´ınez´ese Alapja: sz´eless´egi bej´ar´as Sor adatszerkezet Magyar m´odszer Maxim´alis p´aros´ıt´as keres´ese p´aros gr´afban ¨ Otlet: p´aros´ıt´as n¨ ovel´ese jav´ıt´ ou ´ttal Altern´al´o erd˝o ´ep´ıt´es Sz´eless´egi bej´ar´as speci´alis alkalmaz´asa Sor adatszerkezet
Bogn´ ar Gerg˝ o, t´ emavezet˝ o: Veszpr´ emi Anna
Gr´ afalgoritmusok ´ es hat´ ekony adatszerkezetek szeml´ eltet´ ese
T´ ema
Megval´ os´ıt´ as
Fejleszt´ esi lehet˝ os´ egek
Minim´alis k¨olts´eg˝u fesz´ıt˝ofa t´emak¨or Piros-k´ek elj´ar´as Piros ´es k´ek szab´aly Kruskal algoritmus Moh´o sz´ınez´esi strat´egia, legkisebb s´ uly´ u sz´ıntelen ´el sz´ınez´ese K´ek f´ak, diszjunkt halmaz m˝ uveletek Uni´o-Holvan adatszerkezet Prim algoritmus Moh´o strat´egia, minden l´ep´esben a k´ek szab´aly alkalmaz´asa Cs´ ucsok aktu´alis erd˝ ot˝ ol vett t´avols´aga Kupac adatszerkezet Bogn´ ar Gerg˝ o, t´ emavezet˝ o: Veszpr´ emi Anna
Gr´ afalgoritmusok ´ es hat´ ekony adatszerkezetek szeml´ eltet´ ese
T´ ema
Megval´ os´ıt´ as
Fejleszt´ esi lehet˝ os´ egek
Minim´alis k¨olts´eg˝u fesz´ıt˝ofa t´emak¨or Piros-k´ek elj´ar´as Piros ´es k´ek szab´aly Kruskal algoritmus Moh´o sz´ınez´esi strat´egia, legkisebb s´ uly´ u sz´ıntelen ´el sz´ınez´ese K´ek f´ak, diszjunkt halmaz m˝ uveletek Uni´o-Holvan adatszerkezet Prim algoritmus Moh´o strat´egia, minden l´ep´esben a k´ek szab´aly alkalmaz´asa Cs´ ucsok aktu´alis erd˝ ot˝ ol vett t´avols´aga Kupac adatszerkezet Bogn´ ar Gerg˝ o, t´ emavezet˝ o: Veszpr´ emi Anna
Gr´ afalgoritmusok ´ es hat´ ekony adatszerkezetek szeml´ eltet´ ese
T´ ema
Megval´ os´ıt´ as
Fejleszt´ esi lehet˝ os´ egek
Minim´alis k¨olts´eg˝u fesz´ıt˝ofa t´emak¨or Piros-k´ek elj´ar´as Piros ´es k´ek szab´aly Kruskal algoritmus Moh´o sz´ınez´esi strat´egia, legkisebb s´ uly´ u sz´ıntelen ´el sz´ınez´ese K´ek f´ak, diszjunkt halmaz m˝ uveletek Uni´o-Holvan adatszerkezet Prim algoritmus Moh´o strat´egia, minden l´ep´esben a k´ek szab´aly alkalmaz´asa Cs´ ucsok aktu´alis erd˝ ot˝ ol vett t´avols´aga Kupac adatszerkezet Bogn´ ar Gerg˝ o, t´ emavezet˝ o: Veszpr´ emi Anna
Gr´ afalgoritmusok ´ es hat´ ekony adatszerkezetek szeml´ eltet´ ese
T´ ema
Megval´ os´ıt´ as
Fejleszt´ esi lehet˝ os´ egek
Gr´afok tulajdons´agai
Vizsg´alt gr´afok Ir´any´ıtatlan, egyszer˝ u, ´els´ ulyozott vagy ´els´ uly n´elk¨ uli gr´afok Cs´ ucsok c´ımk´ez´ese egyedi sorsz´ammal ´ Elek s´ ulyoz´asa eg´esz sz´ammal Algoritmusok speci´alis viselked´ese Nem ¨osszef¨ ugg˝o gr´afokra is m˝ uk¨ od˝ o algoritmusv´altozatok Sz´eless´egi bej´ar´as Prim algoritmus
Bogn´ ar Gerg˝ o, t´ emavezet˝ o: Veszpr´ emi Anna
Gr´ afalgoritmusok ´ es hat´ ekony adatszerkezetek szeml´ eltet´ ese
T´ ema
Megval´ os´ıt´ as
Fejleszt´ esi lehet˝ os´ egek
Gr´afok tulajdons´agai
Vizsg´alt gr´afok Ir´any´ıtatlan, egyszer˝ u, ´els´ ulyozott vagy ´els´ uly n´elk¨ uli gr´afok Cs´ ucsok c´ımk´ez´ese egyedi sorsz´ammal ´ Elek s´ ulyoz´asa eg´esz sz´ammal Algoritmusok speci´alis viselked´ese Nem ¨osszef¨ ugg˝o gr´afokra is m˝ uk¨ od˝ o algoritmusv´altozatok Sz´eless´egi bej´ar´as Prim algoritmus
Bogn´ ar Gerg˝ o, t´ emavezet˝ o: Veszpr´ emi Anna
Gr´ afalgoritmusok ´ es hat´ ekony adatszerkezetek szeml´ eltet´ ese
T´ ema
Megval´ os´ıt´ as
Fejleszt´ esi lehet˝ os´ egek
Program ´es k´od
K¨ornyezet, futtat´as Java virtu´alis g´ep JAR arch´ıvum (graf.jar) Ind´ıt´as virtu´alis g´eppel, vagy appletk´ent Fejleszt´es Objektumorient´alt, esem´enyvez´erelt Grafikus fel¨ ulet Logikailag egy v´egrehajt´asi sz´al Csomagok, oszt´alyok, er˝ oforr´asf´ajlok
Bogn´ ar Gerg˝ o, t´ emavezet˝ o: Veszpr´ emi Anna
Gr´ afalgoritmusok ´ es hat´ ekony adatszerkezetek szeml´ eltet´ ese
T´ ema
Megval´ os´ıt´ as
Fejleszt´ esi lehet˝ os´ egek
Program ´es k´od
K¨ornyezet, futtat´as Java virtu´alis g´ep JAR arch´ıvum (graf.jar) Ind´ıt´as virtu´alis g´eppel, vagy appletk´ent Fejleszt´es Objektumorient´alt, esem´enyvez´erelt Grafikus fel¨ ulet Logikailag egy v´egrehajt´asi sz´al Csomagok, oszt´alyok, er˝ oforr´asf´ajlok
Bogn´ ar Gerg˝ o, t´ emavezet˝ o: Veszpr´ emi Anna
Gr´ afalgoritmusok ´ es hat´ ekony adatszerkezetek szeml´ eltet´ ese
T´ ema
Megval´ os´ıt´ as
Fejleszt´ esi lehet˝ os´ egek
Csomagok
Bogn´ ar Gerg˝ o, t´ emavezet˝ o: Veszpr´ emi Anna
Gr´ afalgoritmusok ´ es hat´ ekony adatszerkezetek szeml´ eltet´ ese
T´ ema
Megval´ os´ıt´ as
Fejleszt´ esi lehet˝ os´ egek
Grafikus fel¨ulet
A grafikus fel¨ ulet oszt´alyai
Bogn´ ar Gerg˝ o, t´ emavezet˝ o: Veszpr´ emi Anna
Gr´ afalgoritmusok ´ es hat´ ekony adatszerkezetek szeml´ eltet´ ese
T´ ema
Megval´ os´ıt´ as
Fejleszt´ esi lehet˝ os´ egek
Bels˝o ´abr´azol´as
Gr´afok, algoritmusok ´es adatszerkezetek oszt´alyai Bogn´ ar Gerg˝ o, t´ emavezet˝ o: Veszpr´ emi Anna
Gr´ afalgoritmusok ´ es hat´ ekony adatszerkezetek szeml´ eltet´ ese
T´ ema
Megval´ os´ıt´ as
Fejleszt´ esi lehet˝ os´ egek
Algoritmus oszt´aly
Bogn´ ar Gerg˝ o, t´ emavezet˝ o: Veszpr´ emi Anna
Gr´ afalgoritmusok ´ es hat´ ekony adatszerkezetek szeml´ eltet´ ese
T´ ema
Megval´ os´ıt´ as
Fejleszt´ esi lehet˝ os´ egek
P´elda: Kruskal oszt´aly /** Az algoritmus l´ eptet´ ese. */ @Override protected String internalStep(){ String resultText; if(edge < edges.size()){ Edge e = edges.get(edge); Graph.Vertex u = e.edge.getVertexU(); Graph.Vertex v = e.edge.getVertexV(); resultText = java.text.MessageFormat.format(stepMessage, u.toString(), v.toString()); if(set.find(u) != set.find(v)){ e.edge.set(Graph.Color.BLUE, 0, Graph.Animation.NORMAL); set.union(u, v); }else{ e.edge.set(Graph.Color.RED, 0, Graph.Animation.NORMAL); } ++edge; }else{ result = SUCCESS; resultText = resultMessage; for(Edge e: edges){ if(e.edge.getColor() == Graph.Color.RED){ e.edge.set(Graph.Color.GRAY, 0); } } } return resultText; }
Bogn´ ar Gerg˝ o, t´ emavezet˝ o: Veszpr´ emi Anna
Gr´ afalgoritmusok ´ es hat´ ekony adatszerkezetek szeml´ eltet´ ese
T´ ema
Megval´ os´ıt´ as
Fejleszt´ esi lehet˝ os´ egek
Fejleszt´esi lehet˝os´egek
B˝ov´ıthet˝os´eg Mintagr´af hozz´aad´asa Algoritmus hozz´aad´asa Adatszerkezet hozz´aad´asa Dokument´alts´ag Javadoc
Bogn´ ar Gerg˝ o, t´ emavezet˝ o: Veszpr´ emi Anna
Gr´ afalgoritmusok ´ es hat´ ekony adatszerkezetek szeml´ eltet´ ese
T´ ema
Megval´ os´ıt´ as
Fejleszt´ esi lehet˝ os´ egek
K¨osz¨on¨om a figyelmet!
Bogn´ ar Gerg˝ o, t´ emavezet˝ o: Veszpr´ emi Anna
Gr´ afalgoritmusok ´ es hat´ ekony adatszerkezetek szeml´ eltet´ ese
