Új hozzászólás Aktív témák

• #8128 Karma félisten Wyll #8127

  Új Válasz 2014-08-01 19:11:26 #8128

  Új hozzászólás

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  Privát üzenet küldése

  

  Karma

  félisten

  válasz Wyll #8127 üzenetére

  Inkább javasolnám a Google-t és az angol Wikipédiát, meg esetleg egyetemi jegyzeteket gráfalgoritmusokból.

  De ami eszembe jut, azt leírom:

  a) Vannak általános gráfokra használható ábrázolások, amikkel némely művelet könnyebb, némely bonyolultabb, de leírhatóak statikusan.

  Az egyik ilyen a szomszédsági (adjacencia) mátrix, ami egy NxN-es (N = csúcsok száma) tömbbel megvalósítható. Nem kevésbé pazarló, mint az én tömböm, és nem is jó szvsz.

  Másik az éllista, ami egy E méretű tömb (E az élek száma), és soronként azt írja le, hogy honnan-hova fut egy-egy él. C-ben például megvalósíthatod egy int[2][E] változóval.

  Ez jó lehet, és emberileg is könnyebben kezelhető, cserébe lehet, hogy minden menügenerálásnál végig kell futnod a tömbön, keresve azokat az éleket, amik az aktuális csúcsból indulnak. Nekem perpillanat ez a legszimpatikusabb stratégia.

  Van illeszkedési (incidencia) mátrix is, de az annyira nem passzol, hogy bele se kezdek.

  b) Meg van az a verzió, hogy kihasználod a fa tulajdonságait, és például veszed a klasszikus naiv megoldást: a csúcs egy struct, benne pointerekkel, amik másik csúcsokra mutatnak. Ezt ROM-ba nehezebb rakni, és gyanúsan túl sok rizsa.

Új hozzászólás Aktív témák