Teorija grafova. Implementacija algoritama. HELP :)

Teorija grafova. Implementacija algoritama. HELP :) 11.05.2005. u 20:52 · pre 261 mesec #1

Znam,znam …opet ovaj… Ali sad mi je palo na pamet da bi bolje bilo da ovo pitam na vrijeme. Takođe smatram da je ovo dobro pa i ako ja uspijem da odradim konačnu verziju ovih mojih problema i sam. Jer ja ću uvijek na kraju okačiti krajnji kod tako da se neko kasnije može imati taj kod. Mislio sam da napravim i neki sajt sa svim ovim,jer mi na fax-u radili dosta zanimljivih i standardnih stvari. Toliko o tome… a sad o problemu.

Dakle radi se o teoriji grafova. Dobili smo zadatake koji predstavljaju implementaciju pojedinih stvari iz teorije grafova. Ja sam dobio za zadatak:

Zadatak 1. Za dati graf G i njegova dva čvora x, y naći $d_G{\left({x,y}\right)$ (rastojanje).

Zadatak 2. Da li dati graf sadrži neparnu konturu.

Na net-u sam tražio koliko sam mogao/imao vremena/. Stvar je u tome što ne znam ove pojmove na engleskom, pa mi je teško i da pretražujem. Za početak bi mi dobro došla i pomoć oko ovih izraza na engleskom. Ja ću ovdje dodavati ako budem našao nešto korisno.

Unaprijed zahvalan na pomoći i strpljenju….

Moderatorima: Ako sam pogriješio forum, premjestite ga u odgovarajući…

Potpis

... Mu .... Mu ...

Re: Teorija grafova. Implementacija algoritama. HELP :) 11.05.2005. u 22:06 · pre 261 mesec #2

Graf se kaze Graph :), cvorovi su verticles, a edge je veza izmedju cvorova, ne znam na srpskom izraz.

Sto se rastojanja izmedju 2 cvora tice, koliko se secam koristi se warshall-ov algoritam. Nije komplikovan. Imas u knjizi "Introduction to Algorithms" od Cormena, MIT Press izmedju ostalog i poglavlje (ili 2) posveceno grafovima. Ima je i na netu kao pdf, javi mi se na PM ako ne nadjes.

Potpis

Pop Servis "Paradise Tours"
Java User Group Karlsruhe
IT Dan - Srbija

Officer, I saw the driver who hit me - his name was Johnny Walker.

Re: Teorija grafova. Implementacija algoritama. HELP :) 12.05.2005. u 09:27 · pre 261 mesec #3

Evo jos 2:

1. Neka je dat skup S={1,2,...,n} n e N. Konstruisati graf G=(V,E) gdje je skup cvorova V=|S| a skup grana odredjen sa A~B ako i samo ako je A presjek B prazan skup.

2. Dat je aciklican digraf G sa n cvorova. Oznaciti cvorove grafa G brojevima 1,2,3...n
tako da ako je cvor x oznacen sa k tada su svi cvorovi do kojih se moze doci iz x oznaceni sa brojem vecim od k.

Potpis

... Mu .... Mu ...

Re: Teorija grafova. Implementacija algoritama. HELP :) 12.05.2005. u 15:10 · pre 261 mesec #4

“Određivanje najkraćih rastojanja u netežinskom grafu
Najkraće rastojanje između dva čvora i i j u netežinskom grafu se definiše kao minimalan broj grana na putu između njih. Za nalaženje ovog rastojanja se može iskoristiti modifikovani algoritam obilaska grafa po širini. Čvor i se uzima kao početni čvor pri obilasku. U tom slučaju najkraće rastojanje nekog čvora od njega je jednako njegovom nivou. Zato u algoritam treba još uvesti jedan vektor nevoa čvora u, posle postavljanja odgovarajućeg bita visit u unutrašnjoj for petlji procedure BFS, treba još inkremetirati nivo čvora v preko kojeg se došlo do čvora u i taj rezultat zapamtiti kao nivo čvora u (l(u) = l[v] + 1). Ponovnim dolaskom do već posećenog čvora preko drugog prethodnika, ovo rastojanje se ne može smanjiti. Kada se poseti čvor j, traženo rastojanje je nađeno i algoritam može da završi rad. Pritom se najkraći put sastoji od grana BFS stabla i polazi od korena i do traženog čvora j. Ako se algoritam pusti da odradi do kraja, onda se u vektoru l dobijaju najkraća rastojanja od polaznog do svih drugih čvorova u grafu. “

Strukture podataka Milo V. Tomašević

Ovo je pseudo-kod BFS algoritma iz ove knjige.

Code:

BFS(v)

For i = l to n do
    visit[i] = false
end_for
visit[v] = true
INSERT(Q,v)
while( not QUEUE-EMPTY(Q)) do
    v = DELETE(Q)
for all u, (v,u) e E do
    if (not visit[u]) then
        visit[u] = true
        INSERT(Q,u)
    End_if
End_for
End_while

Ovo sam sad našao pa idem da sad iskucam program pa ću ga ovdje okačit. Ostaje mi poslije još da nadjem ovo za neparnu konturu(ciklus).

https://www.elitesecurity.org/t50794
Ovo jeste slicno ali nije baš to što mi treba.

Potpis

... Mu .... Mu ...

Re: Teorija grafova. Implementacija algoritama. HELP :) 12.05.2005. u 15:16 · pre 261 mesec #5

Citat:

NikolaVeber: ...Sto se rastojanja izmedju 2 cvora tice, koliko se secam koristi se warshall-ov algoritam. Nije komplikovan. Imas u knjizi "Introduction to Algorithms" od Cormena, MIT Press izmedju ostalog i poglavlje (ili 2) posveceno grafovima. Ima je i na netu kao pdf, javi mi se na PM ako ne nadjes.

E da našao sam ovu knjigu ali je još nisam čitavu spustio. A ovaj Warshall-ov algoritam sam malo pogledao ali mi se čini da on služi za izračunavanje matrice puta. Mada nisam se mnogo udubljivao, kasnije ću.

Potpis

... Mu .... Mu ...

Re: Teorija grafova. Implementacija algoritama. HELP :) 12.05.2005. u 15:32 · pre 261 mesec #6

Da, izracunava matricu puteva izmedju svih cvorova... samim tim i izmedju svaka 1 cvora :)
To mi je prvo palo na pamet.

Potpis

Pop Servis "Paradise Tours"
Java User Group Karlsruhe
IT Dan - Srbija

Officer, I saw the driver who hit me - his name was Johnny Walker.

Re: Teorija grafova. Implementacija algoritama. HELP :) 12.05.2005. u 19:53 · pre 261 mesec #7

Bila je vec za rastojanje izmedju dva chvora ...

2. Dat je aciklican digraf G sa n cvorova. Oznaciti cvorove grafa G brojevima 1,2,3...n
tako da ako je cvor x oznacen sa k tada su svi cvorovi do kojih se moze doci iz x oznaceni sa brojem vecim od k.

Preorder obilazak grafa u dubinu. Znachi pustish DFS, i za svaki chvor, kad ga posetish, pridruzish mu broj Counter, i Counter povecash za jedan ...

Potpis

mmmmmm.. aahhhhhh..
e, nije sex nego serem!

Re: Teorija grafova. Implementacija algoritama. HELP :) 12.05.2005. u 21:18 · pre 261 mesec #8

@RooTeR:
Ne bas. Odakle da znas od kog cvora da pocnes?

Ovaj algoritam zove se topolosko sortiranje. Ideja je sledeca:
Nadju se indegree-ovi svih cvorova (npr. DFS-om). Uzmemo one kojima je indegree 0, i stavimo ih na queue. Sa queue uvek uzimamo prvi cvor, numerisemo counterom (koji pocinje od 0, i povecava cim se nekom cvoru dodeli). Kad numerisemo neki cvor, izbacimo ivice koje iz njega polaze, i naravno updateujemo indegree za cvorove sa kojima su bili spojeni. Cim nekom cvoru indegree postane 0, dodajemo ga na queue. As simple as that.

Btw, Floyd-Warshall-ov algoritam sluzi za nalazenje najkracih puteva u bilo kom (dakle i tezinskom) grafu, i slozenosti je $O(|V|^3)$ . Ako graf nije tezinski (dakle sve ivice imaju istu tezinu), najkraci putevi se mogu naci i BFS-om, pri cemu bi morao da se pusti BFS iz svakog cvora, pa bi konacna slozenost bila $O(|V|\cdot (|V|+|E|))$ , sto je u opstem slucaju isto kao Floyd-Warshall. Moze se i pustiti i Dijkstra iz svakog cvora.

Potpis

I HAD A NIGHTMARE
IT ALL STARTED NORMAL
10101010
10110011
THEN ALL OF A SUDDEN
1100102
GAAAAH
_____________________________
www.princeton.edu/~skrstic
www.niwifi.co.sr

Re: Teorija grafova. Implementacija algoritama. HELP :) 13.05.2005. u 01:40 · pre 261 mesec #9

Citat:

NikolaVeber: Da, izracunava matricu puteva izmedju svih cvorova... samim tim i izmedju svaka 1 cvora :)
To mi je prvo palo na pamet.

Ovaj algoritam(ne ovaj koji je iskucan nego ovaj koji je opisan) se zaustavlja cim se doce do trazenog cvora takoda ne trazi rastojanje do sledecih cvorova.

evo pogledajte ove slajdove sto sam prikacio uz poruku.

Nego, bio sam danas na konsultacije kod ove profesorice, i rekla mi je da postoji jedna teorema za ovo. Pa se rastojanje izmedju dva cvora racuna preko matrice susjedstva. Nasao sam to pa cu vam sjutra okaciti to i objasniti.

Potpis

... Mu .... Mu ...

demo-bfs-undirected.zip33.9k

Re: Teorija grafova. Implementacija algoritama. HELP :) 13.05.2005. u 09:59 · pre 261 mesec #10

Ovo je teorema i posledica vezena za problem rastojanja između dva čvora. Pošto imam problem sa kucanjem u $\text{[math]}$ -u, pošto mi je ovo prvi put u životu da sam pokušao da ga koristim objasniću vam ovu teoremu. Kad budem savladao malo tex postaviću i punu teoremu.

Teorema: Neka je $A = \{a_{ij} | i,j = \overline{1 n}\}$ matrica susjedstva jednostavnog grafa G, tada element $a_{ij}^{\left({l}\right)}$ matrice $A^l = \left({a_{ij}^{\left({l}\right)}}\right) i,j = \overline{1 n}$ , tada predstavlkja broj šetnji dužine l od cvora $x_i$ do cvora $x_j$ .

Posledica: Rastojanje izmedu 2 cvora je najkraca staza koja spaja ta dva cvora $d_G\left({x_i, x_j}\right) = min \{ {l|a_ij^{\left({l}\right)}\ne 0}\}$

Dakle radi se o tome da teorema kaže da kad stepenujemo matricu susjedstva prvo pojavljivanje $a_{ij}^\left( l \right)$ \ne 0$ nam daje rastojanje između čvora $x_i$ i čvora $x_j$ koje je jednako stepenu l. Ne znam da li ste me razumjeli.

A ovo je teorema vezana za ovaj drugi problem, da li dati graf sadrži neparni ciklus.

Teorema: Graf G je bipartitan akko ne sadrži neparne cikluse.

Sad idem ovo da isprogramiram. ;)

Potpis

... Mu .... Mu ...

Re: Teorija grafova. Implementacija algoritama. HELP :) 13.05.2005. u 11:23 · pre 261 mesec #11

Citat:

MrLimeni: Ovaj algoritam(ne ovaj koji je iskucan nego ovaj koji je opisan) se zaustavlja cim se doce do trazenog cvora takoda ne trazi rastojanje do sledecih cvorova.

evo pogledajte ove slajdove sto sam prikacio uz poruku.

Koliko sam ja ukapirao, ti pricas o Floyd-Warshallovom algoritmu, a na ovom slajdu je prikazan BFS. Procitaj moj prethodni post i bice ti sve jasno:

Citat:

IsrkiboyI: Btw, Floyd-Warshall-ov algoritam sluzi za nalazenje najkracih puteva u bilo kom (dakle i tezinskom) grafu, i slozenosti je $O(|V|^3)$ . Ako graf nije tezinski (dakle sve ivice imaju istu tezinu), najkraci putevi se mogu naci i BFS-om, pri cemu bi morao da se pusti BFS iz svakog cvora, pa bi konacna slozenost bila $O(|V|\cdot (|V|+|E|))$ , sto je u opstem slucaju isto kao Floyd-Warshall. Moze se i pustiti i Dijkstra iz svakog cvora.

Dakle, ono sto je prikazano na pps prezentaciji je BFS iz jednog cvora, sto ce naci najkraca rastojanja od njega do svih ostalih. Ako hoces i ostala rastojanja, markiras sve cvorove kao neprodjene, pa pustis BFS iz B, pa iz C, itd...

Citat:

Teorema: Graf G je bipartitan akko ne sadrži neparne cikluse.

Da! Dokaz:

(=>) Trivijalno. Neka je graf G bipartitan sa biparticijom (A, B). Podjimo od nekog cvora a iz A. Svaki put neparne duzine dovodi nas do cvora u B, a svaki put parne do cvora u A. Kako treba da se vratimo u a da bi napravili ciklus, on mora biti parne duzine.

(<=) Nesto tezi smer. Nadjimo neko drvo razapinjanja u grafu G, i oznacimo ga sa T. Uzmemo neki, bilo koji cvor, v. Do svakog cvora mozemo iz v stici na jedinstven nacin iduci ivicama koje se nalaze u T. Sada tvrdimo da su one do kojih je put parne duzine u jednoj, a do kojih je neparne u drugoj particiji. Za svaku ivicu e (x, y) vazi jedno od sledeca 2:

(i) e se nalazi u T. U ovom slucaju je ili x pretposlednju cvor na v-y putu kroz T, ili je y pretposlednji cvor na v-x putu kroz T. U svakom slucaju duzine puteva do x i y su razlicite, pa su oni u razlicitim particijama.

(ii) e se ne nalazi u T. U ovom slucaju, x-y put u T, zajedno sa ivicom e pravi ciklus. Po (i) imamo da su cvorovi na x-y putu u T naizmenicno u jednoj i drugoj particiji. Posto je svaki ciklus paran, onda su x i y u razlicitim particijama.

QED

Inace, za proveru da li je graf bipartitan moze se koristiti obican DFS sa markiranjem cvorova crno-belo.

Potpis

I HAD A NIGHTMARE
IT ALL STARTED NORMAL
10101010
10110011
THEN ALL OF A SUDDEN
1100102
GAAAAH
_____________________________
www.princeton.edu/~skrstic
www.niwifi.co.sr

Re: Teorija grafova. Implementacija algoritama. HELP :) 13.05.2005. u 16:32 · pre 261 mesec #12

Ne znam jesmo li se mi razumjeli. Meni treba da ja unesem od kojeg do kojeg cvora mi treba rastojanje. Dakle od čvora x do čvora y. I onda BFS pustim od čvora x i kad čim naiđem na čvor y zaustavim algoritam. Ne treba mi da idem da nađem rastojanje između svih čvorova. Ali, mnogo bolje je ova metoda preko matrice susjedstva , to jest to meni treba. :)

Potpis

... Mu .... Mu ...

Re: Teorija grafova. Implementacija algoritama. HELP :) 13.05.2005. u 19:46 · pre 261 mesec #13

OK, znaci treba ti samo rastojanje izmedju dva cvora. Pa dobro, radi kako hoces, ali stvarno ne mogu da verujem da moze bilo sta da ti bude lakse nego BFS (5-10 redova koda). A o slozenosti (vremenskoj) algoritma za mnozenje matrica da i ne govorim...

Potpis

I HAD A NIGHTMARE
IT ALL STARTED NORMAL
10101010
10110011
THEN ALL OF A SUDDEN
1100102
GAAAAH
_____________________________
www.princeton.edu/~skrstic
www.niwifi.co.sr

Re: Teorija grafova. Implementacija algoritama. HELP :) 13.05.2005. u 23:36 · pre 261 mesec #14

Ma znam ja to, nego ova profesorica je bas to trazila. pa cu odraditi na oba nacina :)))))

Potpis

... Mu .... Mu ...

Re: Teorija grafova. Implementacija algoritama. HELP :) 15.05.2005. u 11:26 · pre 261 mesec #15

Evo ovo je kod koji sam iskucao za privi problem, rastojanje izmedju dva cvora. Ovo je verzija koja koristi ovu teoremu o matricama susjedstva. Odje je samo dio koda. a prikacio sam i kompletnu verziju sa datotekom "matrica.txt" koja cuva matricu susjedstva.

Code:

int main(){
    int **matrix, **matrixTmp;
    //matrix cuva matricu susjedstva
    //matrixTmp cuva stepen matrice susjedstva
    int stepen = 1;
    int x, y;//cvorovi izmedju kojih se trazi rastojanje.
    int brCvorova;

    printf("\nU datoteci matica.txt mora da se nalazi matirca susjedstva");
    printf("\ntako da u jednom redu datoteke nalazi i jedan red matrice.\n");
    printf("\nKoliko cvorova ima u grafu?  ");
    scanf("%d", &brCvorova);

    Allocate2DArray(&matrix, brCvorova);
    Fill2DArray(&matrix, brCvorova, "matrica.txt");
    /* U datoteci matica.txt mora da se nalazi matirca susjedstva
        tako da u jednom redu datoteke nalazi i jedan red matrice
        */
    printf("\tMatrica susjedstva. \n");
    Print2DArray(matrix, brCvorova);

    printf("Unesite broj cvorova izmedju kojih treba naci rastojanje.\n");
    printf("cvor X = ");
    scanf("%d", &x);
    printf("cvor Y = ");
    scanf("%d", &y);

    if ((x<0)||(x>brCvorova)||(y<0)||(y>brCvorova)){
        printf("GRESKA: Takvi cvorovi se ne nalaze u grafu!!!");
        return 0;
    }

    Allocate2DArray(&matrixTmp, brCvorova);
    Fill2DArray(&matrixTmp, brCvorova, "matrica.txt");

    while ((matrixTmp[x-1][y-1] == 0) && (stepen < brCvorova)){
        Multiple2DArray(&matrixTmp, matrix, brCvorova);
        stepen ++;
    }
    if (matrixTmp[x-1][y-1] != 0)
        printf("Rastojanje izmedju cvora %d i cvora %d je %d. \n", x, y, stepen);
    else
        printf("Ne postoji put izmedju cvora %d i cvora %d!!!\n", x, y);
    return 0;
}

Nisam se nesto previse trudio oko menija i dodatnih opcija. Mislim da cu uradit ovaj program i u VB. A vi ako imate kakvih komentara, primjedbi ili pitanja samo navalite. ;)

HVALA SVIMA NA POMOCI.

Potpis

... Mu .... Mu ...

rastojanjeGrafovi.zip1.35k

Re: Teorija grafova. Implementacija algoritama. HELP :) 15.05.2005. u 17:43 · pre 261 mesec #16

Evo druga verzija onog prvog problema, rastojanje. Samo sad pomocu BFS pretrazivanja.

Code:

int distance(int start, int end, Graf g)
{  /* trazi rastojanje od cvora start do cvora end */
    int i;
    int *posjecen = (int*)malloc(g.brojCvorova*sizeof(int));
    Queue q = CreateQueue(g.brojCvorova);
    if (start<0 || start>=g.brojCvorova)
        return -1;
    int *rastojanje = (int*)malloc(g.brojCvorova*sizeof(int));
    for (i=0;i<g.brojCvorova;i++)
        posjecen[i] = 0;
    posjecen[start] = 1;
    rastojanje[start] = 0;

    Enqueue(start,q);
    while(!IsEmpty(q))
    {
        int w = FrontAndDequeue(q);

        for (i=0;i<g.brojCvorova;i++)
        {
            if (g.matricaSusjedstva[w][i] && !posjecen[i])
            {
                Enqueue(i,q);
                posjecen[i] = 1;
                rastojanje[i] = rastojanje[w]+1;
                if (i == end)
                    return rastojanje[i];
            }
        }
    }
    return -1;
}

ovo je samo dio koda. Citav kod sam prikacio...

Potpis

... Mu .... Mu ...

rastojanjeGrafovi_V2.zip1.3k

Forum kao aplikacija na telefonu

Srodne teme