Linkek

Programozási ismeretek

Alapoktól a speciálisig...

Gráf adatszerkezet

Speciális adatszerkezetek

A gráf..., de inkább nézzük a Wikipédiát! :) Érdekes lehet a gráfelmélet is... Vagy nézzünk inkább más forrásokat? Például az ELTE? A lényeg: tele van a net információkkal, csak meg kell találnunk a legjobbat...

Amire mi koncentrálunk most az az, hogyan valósítsuk meg a gráfnak nevezett struktúrákat, milyen adatszerkezeteket definiáljunk pythonos programjainkban, hogy minél egyszerűbben tudjuk megoldani az aktuális feladatot.

Lehetséges adatszerkezetek "normál" gráf megadására

Lehetséges adatszerkezetek "súlyozott" gráf megadására

A fenti ábrákból kitűnhet, hogy a gráf pontjait úgy adtuk meg, hogy akár indexelésre is alkalmasak legyenek majd, vagyis 0,1,2... stb módon...

Nézzünk egy Python példát, ahol a szótár szerkezetben megadott gráfot átalakítjuk csúcsmátrix, illetve élmátrix formába!

GRÁFOK - Python példa (letöltés: graf.py)

Gráfokkal kapcsolatban nagyon sok algoritmus létezik, melyek közül az egyik a minimális feszítőfa megtalálásának algoritmusa. Több megoldás is létezik, nézzük először a PRIM-algoritmust:

PRIM-algoritmus

A mintapéldában egy szótár szerkezetben megadott gráfunk van, melyet csúcsmátrix (vagy szomszédsági mátrix) formába átírunk, majd azt dolgozzuk fel ezzel a mohó algoritmussal.

Wikipédia: (egy másik forrás: ELTE, csak, hogy ilyen is legyen :))
(Az ELTE-forrás eredeti elérhetősége: https://people.inf.elte.hu/scmqaai/algoadat2/csoport/FarkasAttila/Prim_algoritmus.pdf)

„Az algoritmus lépésenként építi fel a minimális feszítőfát, minden lépésben egy csúcsot adva hozzá.
Az algoritmus lépései a következők:

  • Válasszuk ki a gráf egy tetszőleges csúcsát, legyen ez egy egycsúcsú fa.
  • Ameddig van a gráfnak olyan csúcsa, amelyik nincs benne a fában, végezzük el a következőket:
    - Válasszuk ki a fa csúcsai és a gráf többi csúcsa között futó élek közül a legkisebb súlyút.
    - A kiválasztott él nem fabeli csúcsát tegyük át a fába az éllel együtt.”

PRIM-ALGORITMUS - Python példa (letöltés: prim_moho.py)