Srodne teme

16.01.2003. teorija algoritama?
10.02.2009. Osnove teorije grafova
27.10.2004. Teorija grafova + algoritmi
28.11.2009. Zadaci ( Crtanje Algoritama )
04.06.2013. [Teorija algoritama] Skup poznatih algoritama i s..
13.06.2005. Grafovi-implementacija preko liste susjedstva!
21.10.2007. Natjecanja - Literatura?
19.08.2005. Windows 9X implementacija
07.11.2005. crtanje grafova u c/c++
05.04.2006. Knjige Dragosa Cvetkovica

Navigacija

Brisanje liste

Lista poslednjih: 16, 32, 64, 128 poruka.

Teorija grafova. Implementacija algoritama. HELP :)

[es] :: Art of Programming :: Teorija grafova. Implementacija algoritama. HELP :)

[ Pregleda: 5445 | Odgovora: 15 ] > FB > Twit

Autor

MrLimeni
Montenegro

Član broj: 27761
Poruke: 100
*.crnagora.net.

Profil

Teorija grafova. Implementacija algoritama. HELP :)

^{11.05.2005. u 19:52 - pre 243 meseci}

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

(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…

_{[Ovu poruku je menjao MrLimeni dana 15.05.2005. u 11:30 GMT+1]}

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

Odgovor na temu

NikolaVeber
NikolaVeber
neradnik na porodiljskom bolovanju
Karlsruhe

Član broj: 5115
Poruke: 1254
*.rz.uni-karlsruhe.de.

Jabber: nikolaveber@jabber.org
ICQ: 121532865

Profil

Re: Teorija grafova. Implementacija algoritama. HELP :)

^{11.05.2005. u 21:06 - pre 243 meseci}

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.

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

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

Odgovor na temu

MrLimeni
Montenegro

Član broj: 27761
Poruke: 100
*.cis.cg.ac.yu.

Profil

Re: Teorija grafova. Implementacija algoritama. HELP :)

^{12.05.2005. u 08:27 - pre 243 meseci}

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.

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

Odgovor na temu

MrLimeni
Montenegro

Član broj: 27761
Poruke: 100
*.crnagora.net.

Profil

Re: Teorija grafova. Implementacija algoritama. HELP :)

^{12.05.2005. u 14:10 - pre 243 meseci}

“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).

http://www.elitesecurity.org/tema/50794
Ovo jeste slicno ali nije baš to što mi treba.

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

Odgovor na temu

MrLimeni
Montenegro

Član broj: 27761
Poruke: 100
*.crnagora.net.

Profil

Re: Teorija grafova. Implementacija algoritama. HELP :)

^{12.05.2005. u 14:16 - pre 243 meseci}

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.

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

Odgovor na temu

NikolaVeber
NikolaVeber
neradnik na porodiljskom bolovanju
Karlsruhe

Član broj: 5115
Poruke: 1254
*.rz.uni-karlsruhe.de.

Jabber: nikolaveber@jabber.org
ICQ: 121532865

Profil

Re: Teorija grafova. Implementacija algoritama. HELP :)

^{12.05.2005. u 14:32 - pre 243 meseci}

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

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

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

Odgovor na temu

RooTeR
Rajko Nenadov
nema ga
Detelinara, NS

Član broj: 2386
Poruke: 385
*.neobee.net.

Profil

Re: Teorija grafova. Implementacija algoritama. HELP :)

^{12.05.2005. u 18:53 - pre 243 meseci}

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 ...

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

Odgovor na temu

Srđan Krstić
Srđan Krstić
Princeton, NJ

Član broj: 7526
Poruke: 416
*.rcub.bg.ac.yu.

Jabber: srkiboy@elitesecurity.org
ICQ: 193836365
Sajt: www.princeton.edu/~skrsti..

Profil

Re: Teorija grafova. Implementacija algoritama. HELP :)

^{12.05.2005. u 20:18 - pre 243 meseci}

@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

. 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

, sto je u opstem slucaju isto kao Floyd-Warshall. Moze se i pustiti i Dijkstra iz svakog cvora.

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

Odgovor na temu

MrLimeni
Montenegro

Član broj: 27761
Poruke: 100
*.crnagora.net.

Profil

Re: Teorija grafova. Implementacija algoritama. HELP :)

^{13.05.2005. u 00:40 - pre 242 meseci}

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.

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

Prikačeni fajlovi

demo-bfs-undirected.zip

demo-bfs-undirected.zip - 33.9k

Odgovor na temu

MrLimeni
Montenegro

Član broj: 27761
Poruke: 100
*.crnagora.net.

Profil

Re: Teorija grafova. Implementacija algoritama. HELP :)

^{13.05.2005. u 08:59 - pre 242 meseci}

Ovo je teorema i posledica vezena za problem rastojanja između dva čvora. Pošto imam problem sa kucanjem u

-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

matrica susjedstva jednostavnog grafa G, tada element

matrice

, tada predstavlkja broj šetnji dužine l od cvora

do cvora

.

Posledica: Rastojanje izmedu 2 cvora je najkraca staza koja spaja ta dva cvora

Dakle radi se o tome da teorema kaže da kad stepenujemo matricu susjedstva prvo pojavljivanje

nam daje rastojanje između čvora

i čvora

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. ;)

_{[Ovu poruku je menjao MrLimeni dana 15.05.2005. u 17:58 GMT+1]}

_{[Ovu poruku je menjao MrLimeni dana 15.05.2005. u 18:01 GMT+1]}

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

Odgovor na temu

Srđan Krstić
Srđan Krstić
Princeton, NJ

Član broj: 7526
Poruke: 416
*.rcub.bg.ac.yu.

Jabber: srkiboy@elitesecurity.org
ICQ: 193836365
Sajt: www.princeton.edu/~skrsti..

Profil

Re: Teorija grafova. Implementacija algoritama. HELP :)

^{13.05.2005. u 10:23 - pre 242 meseci}

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

. 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

, 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.

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

Odgovor na temu

MrLimeni
Montenegro

Član broj: 27761
Poruke: 100
*.crnagora.net.

Profil

Re: Teorija grafova. Implementacija algoritama. HELP :)

^{13.05.2005. u 15:32 - pre 242 meseci}

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. :)

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

Odgovor na temu

Srđan Krstić
Srđan Krstić
Princeton, NJ

Član broj: 7526
Poruke: 416
*.rcub.bg.ac.yu.

Jabber: srkiboy@elitesecurity.org
ICQ: 193836365
Sajt: www.princeton.edu/~skrsti..

Profil

Re: Teorija grafova. Implementacija algoritama. HELP :)

^{13.05.2005. u 18:46 - pre 242 meseci}

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...

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

Odgovor na temu

MrLimeni
Montenegro

Član broj: 27761
Poruke: 100
*.crnagora.net.

Profil

Re: Teorija grafova. Implementacija algoritama. HELP :)

^{13.05.2005. u 22:36 - pre 242 meseci}

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

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

Odgovor na temu

MrLimeni
Montenegro

Član broj: 27761
Poruke: 100
*.crnagora.net.

Profil

Re: Teorija grafova. Implementacija algoritama. HELP :)

^{15.05.2005. u 10:26 - pre 242 meseci}

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.

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

Prikačeni fajlovi

rastojanjeGrafovi.zip

rastojanjeGrafovi.zip - 1.35k

Odgovor na temu

MrLimeni
Montenegro

Član broj: 27761
Poruke: 100
*.crnagora.net.

Profil

Re: Teorija grafova. Implementacija algoritama. HELP :)

^{15.05.2005. u 16:43 - pre 242 meseci}

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...

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

Prikačeni fajlovi

rastojanjeGrafovi_V2.zip

rastojanjeGrafovi_V2.zip - 1.3k

Odgovor na temu

[es] :: Art of Programming :: Teorija grafova. Implementacija algoritama. HELP :)

[ Pregleda: 5445 | Odgovora: 15 ] > FB > Twit

Srodne teme

16.01.2003. teorija algoritama?
10.02.2009. Osnove teorije grafova
27.10.2004. Teorija grafova + algoritmi
28.11.2009. Zadaci ( Crtanje Algoritama )
04.06.2013. [Teorija algoritama] Skup poznatih algoritama i s..
13.06.2005. Grafovi-implementacija preko liste susjedstva!
21.10.2007. Natjecanja - Literatura?
19.08.2005. Windows 9X implementacija
07.11.2005. crtanje grafova u c/c++
05.04.2006. Knjige Dragosa Cvetkovica

Navigacija

Lista poslednjih: 16, 32, 64, 128 poruka.