Jump to content
GSForum - Segélyvonal

Gráfelmélet


ocsi

Recommended Posts

ocsi

Ez egy nagyon érdekes téma, és kapásból lenne is egy problémám...

 

A feladat:

 

Egy irányított gráf egy adott pontjáról kell azt megvizsgálnom, hogy vissza lehet-e jutni belõle saját magába (nem feltétlenül közvetlenül, akár sok más ponton keresztül)

Erre szeretném megtalálni, a leggyorsabb megoldást. Eddig csak azt találtam, amit a kép pont közti út vizsgálatára mondanak:

 

Kiindulási pont összes 'szomszédját' (ahova eljuthatok belõle közvetlenül) megjelölöm, a megjelöltekel ugyanezt csinálom, egésszen addig amig vissza nem jutok az eredeti pontba, vagy meg nem vizsgáltam minden lehetõséget....

DE nekem maximum 1 000 000 pontom van. ÉS ennél nekem egy gyorsabb megoldásra lenne szükségem.. van rá valami ötletetek, vagy forrásotok???

Link to comment
Share on other sites

arpsoft

Gondolkodom rajta. Azt meg tudom mutatni, hogy egy gráf körmentes vagy sem.

De azt, hogy egy adott pont benne van-e egy körben, azt még nem.

Link to comment
Share on other sites

google

Lista illetve láncolt lista adattípusban szokták ezeket. Ha binfa, akkor veremben. (Binfa az a gráf, amely minden ágának maximum két részága van.) A pontokat, amelyeken már áthaladtunk, betesszük a sorba, amíg véget nem ér a dolog. Minden további pontnál megvizsgáljuk, hogy benne van-e a sorban. További okosságokat nem tudok mondani, mert ettõl mindig is irtóztam. :upsz:

Próbálok kódrészletet találni.

Link to comment
Share on other sites

ocsi

Hmmm adattipusról itt szó sincs.. én konkrétan egy gráfot kapok ( egyszöveg file írja le az éleket) És csak annyit tudok, hogy irányított gráf, tehát a kapcsolatok száma nincs megszabva!

Link to comment
Share on other sites

arpsoft

A fa és a binfa is biztosan körmentes, tehát azt elvethetjük.

A txt fájl szerkezete megvan? Mondjuk olyan, hogy:

10000;10001

10001;20000

10001;20030

20030;10000

 

Tehát az van benne, hogy melyik pontból melyik pontba vezet út, és az irány mindig balról jobbra?

Mert ha igen, akkor el lehet indítani a keresést elõre és hátra egyszerre, ezzel gyorsítani lehetne az algoritmust.

Link to comment
Share on other sites

csutomi

Próbáld meg talán a következõ könyvben megnézni: Knuth: A számítógép-programozás mûvészete

ui: Csak tipp

Link to comment
Share on other sites

ocsi

Arpsoft: igen! a szövegfile minden sorában egy 'él' van megadva ami A ból B be mutat'

 

A B

1 2

2 4

4 1

3 3

 

A kétirányú keresésre én is gondoltam, csak az vele a problémám, hogy visszafelé keresés idõigényesebb jóval mint, elõre felé...

 

---------------------------------------------------------------------------------

Utólag:

A file-ban való mozgás miadt a visszafelé keresés egy picitvel idõigényesebb, de nem sokkal... szóval igazad van, én számoltam el magam...

 

----------------------------------------------------------------------------------

 

utólag2:

 

Másik lehetõség, hogy elõre megkeressük az összes 'kört' a gráfban, tehát elõre minden pontnak adunk egy tulajdonságot, hogy szerepel-e körben, vagy nem. Így ezt csak egyszer kell megcsinálni!

Edited by ocsi
Link to comment
Share on other sites

arpsoft

Akkor itt a megoldás:

 

Az adott csúcstól indulva bejárjuk a gráf elérhetõ csúcsait, mindegyiket megjelöljük valamivel, mondjuk beszínezzük feketére, hogy ott már jártunk. A bejárás nyilván rekurzív lesz, ezért a körök kikerülésére, ha fekete csúcs következne a rekurzióban, akkor azt kihagyjuk.

Most van egy gráfunk, aminek azon csúcsai feketék, amiket el lehet érni a keresett csúcsból.

 

Most jön a trükk: megfordítjuk az élek irányítottságát, és elvégezzük az elõzõ eljárást, csak fekete helyett piros színt használunk.

 

Az adott csúcstól indulva bejárjuk a megfordított gráf elérhetõ csúcsait, mindegyiket megjelöljük pirossal, hogy ott már jártunk. A körök kikerülésére, ha piros csúcs következne a rekurzióban, akkor azt kihagyjuk.

Ha viszont fekete csúcsot találtunk, akkor a keresett csúcs egy kör része!

 

A futási idõ maximuma O(2*csúcsok száma+élek száma).

Link to comment
Share on other sites

ocsi

Nos.. Köszönöm a megoldást. Az élek száma max 5M a csúcsoké max 1M

Tehát a futásdõ max (5*2*10^12)=10^13 És ezt függvényt le kéne futtatni akár megközelítõleg 1M szor...

Ezért azt találtam ki, hogy fogom a gráfot és az elején bejelölöm benne az összes kört. Tehát annak összes elemét.

Ez a rekurzió nem lesz lassab mint ha egy élre nézném meg ( a legrosszabb esetet nézve) csak annyival, hogy közben eltárolom az adatokat...

Megvalósítás:

Elindulok egy ponttól, és minden elágazásnál rekurzívan végig megyek minden szálom. A függvény mindig megkap egy tömböt ( a mutatóját) amiben a bejárt mezõk vannak, és megkap egy számot, hogy hol volt az elágazás. Ha 5 nél van elágazás akkor a rekurzió a 6. elemtõl irogatja a tömbbe a végigjárt csúcsokat. HA zsákutcába jut, akkor kilép, és a következõ rekurzió megkapja a tömböt, amiben ugyan benne van az elõzõ út, de õt ez nem érdekli, mert ugye megkapta azt a számot, ahol az elágazás van, tehát õ onnan folytatja a tömböt. HA olyan helyre lép ami már benne van a tömbben( vagy ki van szinezve) akkor megjelöli az összes elemet az elõzõ elem és a most megtalált már egyszer megjelölt elem között...

Így elõre megkapjuk az összes csúcsot ami legalább egy körnek a tagja.

Link to comment
Share on other sites

arpsoft

Bocs, de a feladat az volt, hogy egy adott pontról kell megmondani, hogy vissza lehet-e jutni bele, nem az összesrõl.

Az én megoldásom egy pontra asszimptotikusan élek+csúcsok idõ alatt lefut.

 

De ha a köröket akarod megkeresni, akkor javaslom a mélységi keresést, illetve az azzal összefüggõ erõsen összefüggõ komponensek keresését.

Az utóbbi algoritmus megkeresi az összes kört és a gráf részfájaként kiadja.

Két teljes mélységi keresést tartalmaz.

Részletes leírása megtalálható Cormen,Lesierson,Rivest: Algoritmusok címû könyvében.

Link to comment
Share on other sites

  • 4 weeks later...
atzs

Csinálhatsz egy M0 mátrixot. Az M0(i,j)=1, ha az i. csúcsból vezet út a j. csúcsba, a többi érték 0.

 

(Általában N=M0^n-ben N(i,j)=k, ha az i. csúcsból k-féleképpen el lehet jutni a j. csúcsba pontosan n lépésben, ha nem tévedek.)

 

Ha veszed M1=M0^2+M0-et, és ahol >0 szám van, azt helyettesíted 1-gyel, akkor megkapod, hogy honnan hová tudsz eljutni maximum 2 lépésben.

 

Aztán veszed M2=M1*M0+M1-t, és ahol >0 van...

 

Aztán veszed M3=M2*M0+M2-t, és ahol >0 van...

 

Akkor állsz meg, ha M(i)=M(i+1), mert akkor már máshová nem tudsz sehonnét eljutni.

 

A max lépésszám a csúcsok száma.

 

A konkrét feladatra persze ez nem optimális, de több információt ad.

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
×
×
  • Create New...