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

• Joooe tag

  #2385

  #2380 Gerghu

  2006-12-08 05:02:36

  Új Válasz

  Ú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

  

  Joooe

  tag

  #2380 Gerghu

  #2380 Gerghu

  Okay elárulom, eddig azért nem tettem mert tartok tőle hogy az előadó szeme mindent meglát.
  A feladat: egy irányított gráfban megkeresni azokat a csúcsokat amelyek legalább egy körnek a részei.
  Tudom hogy kellene megcsinálni csak implementálni nem tudom: egy éllistába be kell olvasni a gráfot, azon futtatni egy erősen összefüggő komponensek(EOK) keresést és ennyi.
  C és Java között gondolkodom, Javaban megvan az algoritmus, meg ugy látom ott van eleve láncolt lista, mig C-ben az algoritmust ujra fel kellene épiteni.
  Az éllistát ugy kell csinálni, hogy létrehozok egy tömböt aminek az indexei a csúcsok sorszámai? és minden tömbelem egy LinkedList? mert ha igen akkor a beolvasás nem lehet gond Java alatt... csak utána hogy hozzam össze a kezembe adott algoritmussal? vagy a irjam meg a mélységi keresést az éllistámhoz? (2 mélységi keresés kell az EOK-hez)
  
  Köszönöm

  Én inkább egy bitmátrixot tartanék megfelelőnek erre a feladatra.
  A memóriában az is elfér (10000^2/8 = kb. 12 MB)
  Bár elgondolkodtató, hogy ez a megközelítés nem használja ki az élek relatíve alacsony számát.
  
  Ami gyorssá teheti a megvalósítást, hogy ha a mátrix azt mutatja, hogy az i-edik csúcsból elérhető a j-edik, akkor a j-edik sort hozzá VAGY-oljuk az i-edik sorhoz, ezzel tovább bővítve az i-ből elérhető csúcsok listáját, azokkal ami j-n keresztül elérhető.
  
  Ez mindenféle implementációban elvégzendő művelet, hogy megvizsgáljuk, hogy mi van ha arra megyünk, de azt hiszem így tudjuk leggyorsabban megtenni. Így processzortól függően egyetlen művelet során nagyon sok (64?) csúcsra történik meg a vizsgálat.
  
  Az még egy kicsit elgondolkodtató, hogy mikor végeztünk, hiszen ezt többször el kell végezni, de ha végeztünk, akkor azokat a csúcsokat listázzuk amire mátrix[i,i]=1, azaz elérhető magából maga, azaz tagja valamely irányított körnek.
  
  
  
  [Szerkesztve]
  
  [Szerkesztve]

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