Obilazak grafa
U računarstvu, obilazak grafa je problem posete svih čvorova u grafu na određeni način. Obilazak drveta je poseban slučaj obilaska grafa.
Problem obilaska grafa[uredi | uredi izvor]
U radu sa grafovima se često javlja potreba da se na sistematičan način tačno jednom posete svi njegovi čvorovi. Ovakav obilazak se može početi iz unapred zadatog čvora, ili se početni čvor može izabrati na slučajan način. Obilazak se odvija iterativno, a do tada posećenih čvorova se dolazi prateći grane koje izlaze iz već posećenih čvorova, pri čemu se do tada posećeni čvorovi ne posećuju nanovo.
Redosled obilaska čvorova osim pravila izbora narednog čvora za obilazak zavisi i od izbora početnog čvora. To je najočiglednije kod nepovezanih ili usmerenih grafova, gde se nekada praćenjem grana koje izlaze iz posećenih čvorova ne mogu naći novi neposećeni čvorovi iako oni postoje. U tom slučaju postupak obilaska treba ponoviti uzimajući neki od neposećenih čvorova kao početni.
Obilaskom grafa dobija se stablo obilaska koje sadrži sve čvorove grafa kao i one grane preko kojih su se pronalazili i posećivali novi čvorovi. U odnosu na ovo stablo grane grafa se dele na 4 kategorije:
- Grana stabla (u,v) je ona grana preko koje se prvi put tokom obilaska otkriva i posećuje čvor v, čvor v je direktni sledbenik čvora u u stablu obilaska.
- Direktna grana (u,v) je ona grana gde je čvor v sledbenik, ali ne direktni čvora u u stablu obilaska.
- Povratna grana (u,v) je ona grana gde je čvor v prethodnik čvora u u stablu obilaska.
- Poprečna grana (u,v) je ona grana gde u i v nisu u direktnoj liniji nasleđivanja u stablu obilaska. Ova grana mora biti usmerena zdesna ulevo, te otud i naziv grana ulevo.
Za DFS stablo neusmerenog grafa, pak važi: grane povezanog neusmerenog grafa ne mogu biti biti poprečne za DFS stablo, tj. ne mogu povezivati čvorove na različitim putevima od korena. Kod neusmerenog grafa povratne i direktne grane se poklapaju jer nisu usmerene.
Može se pokazati da je usmereni graf acikličan ako i samo ako DFS stablo nema povratnih grana.
Algoritmi za obilazak grafa[uredi | uredi izvor]
Algoritmi obilaska grafa se razlikuju po pravilu izbora narednog čvora za obilazak. Dva osnovna algoritma su:
Obilazak u dubinu (DFS)[uredi | uredi izvor]
Obilazak započinje iz proizvoljnog zadatog čvora r, korena pretrage u dubinu. Koren se označava kao posećen. Zatim se bira proizvoljni neoznačeni čvor r1, susedan sa r, pa se iz čvora r1 rekurzivno startuje pretraga u dubinu. Iz nekog nivoa rekurzije izlazi se kad se naiđe na čvor v kome su svi susedi (ako ih ima) već označeni. Ako su u trenutku završetka pretrage iz r1, svi susedi čvora r označeni, onda se pretraga za čvor r završava. U protivnom, bira se sledeći proizvoljni neoznačeni sused r2 čvora r, izvršava se pretraga polazeći od r2, itd. Pretraga grafa uvek se vrši sa nekim ciljem. Da bi se različite aplikacije uklopile u pretragu u dubinu, posećivanju čvora ili grane pridružuju se dve vrste obrade:
- ulazna obrada,
- izlazna obrada.
Ulazna obrada vrši se u trenutku označavanja čvora. Izlazna obrada vrši se posle povratka nekom granom, ili kad se otkrije da neka grana vodi već označenom čvoru. Ulazna i izlazna obrada zavise od konkretne primene DFS.
Pseudokod[uredi | uredi izvor]
Ulaz: G = (V,E) (usmereni povezani graf) i v (čvor grafa G).
Izlaz: zavisi od primene.
1 Алгоритам DFS(G, v);
2 begin
3 означи v;
4 изврши улазну обраду на v; //улазна обрада зависи од примене -{DFS}-
5 for све гране (v,w) do
6 if w је неозначен then
7 DFS(G,w); //Нови рекурзивни позив
8 изврши излазну обраду за (v,w); //излазна обрада зависи од примене -{DFS}-
9 //она се понекад врши само за гране ка новоозначеним чворовима
10 end
Redosled obilaska čvorova nije jedinstven. Da bi bio jedinstven, potrebno je uvesti dodatno pravilo da se među susedima bira čvor sa najmanjom vrednošću (slovo najbliže početku azbuke ili abecede).
Obilazak u širinu (BFS)[uredi | uredi izvor]
Obilazak u širinu počinje iz proizvoljnog zadatog čvora r koji se označava kao posećen i dodaje kao jedini element reda. Potom se ponavljaju sledeći koraci, dok god red ne postane prazan: obriši čvor sa početka reda i svakog neposećenog komšiju ovog čvora označi kao posećenog i dodaj ga na kraj reda.
Pseudokod[uredi | uredi izvor]
Pseudokod BFS algoritma za obilazak grafa G=(V,E) koji je zadat matricom povezanosti tako da ispisuje čvorove u redosledu obilaska:
Ideja: Kod BFS pretrage kada se stigne do nekog čvora x grafa G, najpre se obilaze njegovi neposećeni i neposredni susedi. Nakon toga se nastavlja BFS algoritam, tj. posećuju se svi neposećeni susedi iz prethodnog nivoa pretrage. Zbog toga se koristi FIFO (First InFirst Out) red.
Skica rešenja:
- Polazni čvor x grafa G.
- Smesti se u red.
- Poseti se.
- Markira kao posećen.
- Upišu se susedi čvorova x na kraj reda.
- Poseti se sledeći čvor iz reda, markira kao posećen, njegovi neposećeni susedi se upišu na kraj reda.
- Ponavlja se korak 2 dok ima neposećenih čvorova u redu.
1 /* a = матрица суседства, n= број чворова графа G */
2 void BFS (int a[][50], int n )
3 {
4 int x; /* чвор графа */
5 int m[50]; /* m је низ маркираних чворова графа */
6 /* иницијализација низа маркираних чворова на 0, јер су на почетку сви непосећени */
7 for (x = 0 ; x < n ; x++ )
8 m[x] = 0;
9 /* посета графа почев од првог непосећеног чвора */
10 for (x = 0 ; x < n ; x++ )
11 if (!m[x] )
12 poseti (x, a, n, m )
13 }
14 /* s = пролази чвор претраге по ширини, a = матрица суседства */
15 /* n = број чворова графа, m = низ посећених чворова */
16
17
18 void poseti(int s, int a [][50], int n, int m[] )
19 {
20 int i, k; /* бројачи у циклусу */
21 int v; /* чвор графа */
22 int red[50]; /* низ чворова графа поређаних у поретку BFS претраге */
23 /*иницијализација низа m, ред у односу на полазну чвор претраге s */
24 m[s] = 1;
25 red[0] = s;
26 k = 1;
27 /* обилазак непосредних суседа чвора s, разлика од DFSа */
28 for (i = 0 ; i < k ; i++ )
29 {
30 s = red[i];
31 for (v = 0 ; v < n ; v++ )
32 if(!m[v] && a[s][v] )
33 {
34 m[v] = 1;
35 red[k++] = v;
36 }
37 }
38 /*испис -{BFS}- поретка*/
39 for (i = 0 ; i < k ; i++ )
40 printf("%d" , red[i] );
41 }
Složenost[uredi | uredi izvor]
Svaka grana pregleda se tačno dva puta, jednom sa svakog kraja. Prema tome, vremensku složenost je proporcionalna broju grana. S druge strane, broj rekurzivnih pokretanja algoritma je V, pa se složenost algoritma može opisati izrazom O(|V|+|E|). Ako je korišćeno matrično predstavljanje imamo vremensku složenost od O(|V|²), a ukoliko je korišćeno ulančano predstavljanje složenost je O(|V|+|E|). Ulančano predstavljanje daje bolje vremenske performanse.
Problemi koji se rešavaju preko obilaska grafa[uredi | uredi izvor]
- Topološko sortiranje.
- Minimalno povezujuće stablo.
- Transportne mreže.
- Uparivanje, Hopcroft-Karp algoritam.
- Tranzitivno zatvorenje.
- Najkraći putevi iz datog čvora, Dajkstrin algoritam.
- Svi najkraći putevi, Flojd-Voršalov algoritam.
- Pronalaženje artikulacionih tačaka.
- Pronalaženje mostova.
Literatura[uredi | uredi izvor]
- Algoritmi, profesor Miodrag Živković, MATF, Beograd 2001. godina.
- Beginning Algorithms, Simon Harris and James Ross, published 2006. by Wiley Publishing, Inc., Indianapolis, Indiana.
- How to Think About Algorithms, Jeff Edmonds, published 2008. by Cambridge University Press, New York.
- Coding Theory Algorithms, Architectures, and Applications, Andre Neubauer, Volker Kuhn, Jurgen Freudenberger, published 2007. by John Wiley & Sons Ltd, The Atrium, Southern Gate, Chichester, West Sussex PO19 8SQ, England.
- Elementary Functions Algorithms and Implementation Second Edition, Jean-Michel Muller, publised 2006 by Birkhauser Boston.
- Introduction to Algorithms Second Edition, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, published 2001. by The Massachusetts Institute of Technology.
