2.3 Obilazak grafova

Prvi problem na koji se nailazi pri konstrukciji proizvoljnog algoritma za obradu grafa je kako pregledati graf, tj. njegove čvorove i grane. Za razliku od, na primer, nizova gde je taj problem trivijalan zbog jednodimenzionalnosti ulaza (nizovi se mogu lako pregledati sekvencijalnim prolaskom kroz elemente), pregledanje grafa, odnosno njegov obilazak, nije trivijalan problem.

Razmotrimo slučaj lavirinta u obliku pravougaone mreže polja, takvih da se sa svakog polja može preći na neko od četiri susedna polja: desno, levo, dole i gore. Međutim, neka od polja lavirinta sadrže zidove i na njih se ne može preći. Lavirint sadrži dva posebna polja koja nazivamo ulaz i izlaz. Potrebno je pronaći put kojim se od ulaznog polja može stići do izlaznog polja u lavirintu.

Ovaj problem možemo predstaviti kao grafovski problem: svakom polju lavirinta koje ne sadrži zid pridružujemo jedan čvor grafa, dok grana između dva čvora postoji ako su odgovarajuća polja pravougaone mreže susedna. Na ovaj način se problem pronalaska puta kroz lavirint svodi na traženje puta kroz graf od ulaznog čvora do izlaznog čvora.

Postoje dva osnovna algoritma za obilazak grafa: obilazak u dubinu i obilazak u širinu. Umesto termina obilazak često se upotrebljava i termin pretraga.

U opštem slučaju, algoritam obilaska tj. pretrage povezanog grafa iz čvora \(r\) može imati sledeću strukturu:

\begin{algorithm}
\caption{Obilazak grafa}
\begin{algorithmic}
\Procedure{ObilazakGrafa}{početni čvor $r$}
    \State{dodaj čvor $r$ u kolekciju $K$}
    \While{$K$ nije prazna}
        \State{uzmi čvor $u$ iz $K$}
        \State{označi čvor $u$}
        \State{po potrebi izvrši obradu čvora $u$}
        \ForAll{grana $(u, v)$}
             \If{čvor $v$ nije označen}
                 \State{ubaci čvor $v$ u $K$}
             \EndIf
        \EndFor
    \EndWhile
\EndProcedure
\end{algorithmic}
\end{algorithm}

Mehanizam označavanja čvorova nam daje garancije da će se algoritam zaustaviti – svaki čvor biće označen (tj. posećen i obrađen) najviše jednom. Pretpostavlja se da su u početku svi čvorovi neoznačeni. U zavisnosti od toga koja se kolekcija \(K\) odabere, dobijaju se različiti algoritmi obilaska koji se mogu primeniti za rešavanje različitih problema (za neke probleme je bitno koji se obilazak primenjuje, dok za neke nije).

• Ukoliko za kolekciju \(K\) odaberemo stek, dobijamo neku vrstu algoritma obilaska u dubinu¹.
• Ako je kolekcija \(K\) red, dobijamo algoritam obilaska u širinu.
• Ako je kolekcija \(K\) red sa prioritetom dobijamo obilazak prema prioritetu. Ako prioritet čvora predstavlja težina grane koja ga spaja sa čvorovima koje smo prethodno obišli dobijamo minimalno povezujuće drvo datog grafa, a ako prioritet čvora predstavlja najkraće do tada određeno njegovo rastojanje od polaznog čvora, dobijamo najkraće puteve od polaznog čvora do svih ostalih čvorova u datom grafu. O težinskim grafovima i ovim algoritmima biće više reči u poglavlju 2.8.

2.3.1 Obilazak u dubinu

Razmotrimo prethodno razmatrani problem traženja puta kroz lavirint. Ovaj problem možemo rešiti tako što izaberemo neku putanju u lavirintu (po nekom unapred definisanom pravilu) i pratimo je sve dok ne stignemo do izlaza ili dok ne dođemo do polja iz koga ne možemo dalje – u tom slučaju se vraćamo unazad i na prvoj prethodnoj raskrsnici idemo nekim alternativnim putem. Ovo je ideja tzv. obilaska u dubinu, odnosno pretrage u dubinu (DFS, skraćenica od depth–first–search). Obilazak u dubinu je praktično isti za neusmerene i usmerene grafove. Međutim, pošto želimo da ispitamo neke osobine grafova koje nisu iste za neusmerene i usmerene grafove, razmatranje obilaska u dubinu je podeljeno na dva dela: na obilazak neusmerenih i obilazak usmerenih grafova.

Neusmereni grafovi

Neka je dat graf \(G=(V,E)\). Želimo da izvršimo obilazak grafa tako da uvek kada je to moguće idemo dalje (u dubinu) pre nego što se vratimo u čvor u kom smo već bili. Ovaj pristup zove se obilazak u dubinu (DFS). Osnovni razlog korisnosti obilaska u dubinu leži u njenoj jednostavnosti i lakom rekurzivnnom opisu. Implementacija može takođe biti iterativna, a umesto sistemskog steka koji se koristi pri realizaciji rekurzije, može se eliminisati rekurzija tako što se koristi poseban stek – takva implementacija se uklapa u opšti opis algoritama obilaska tj. obilazak grafova dat na početku ovog poglavlja.

Rekurzivna implementacija

Pretraga u dubinu se jednostavno definiše rekurzivno. Razmotrimo problem obilaska grafa u dubinu kada je graf zadat listama povezanosti i kada je dat čvor \(r\) grafa iz koga se započinje obilazak. Inicijalno su svi čvorovi neoznačeni. Čvorove ćemo označavati u trenutku kada ih po prvi put posetimo. Obično se prilikom označavanja čvora vrši neka njegova obrada (mada ćemo videti da obrada može da se vrši i na drugim mestima). Algoritam funkcioniše tako što označi početni čvor, a zatim se rekurzivno primeni na sve njegove neoznačene susede.

\begin{algorithm}
\caption{Obilazak u dubinu -- rekurzivna formulacija}
\begin{algorithmic}
\Procedure{DFS}{čvor $u$}
    \State{označi čvor $u$}
    \State{izvrši ulaznu obradu čvora $u$}
    \ForAll{sused $v$ čvora $u$}
       \If{čvor $v$ nije označen}
         \State{}
         \Call{DFS}{$v$}
       \EndIf
    \EndFor
    \State{izvrši izlaznu obradu čvora $u$}
\EndProcedure
\State{}
\State{}
\Call{DFS}{početni čvor $r$} 
\end{algorithmic}
\end{algorithm}

Dakle, svaki čvor \(u\) za koga se poziva funkcija DFS se označava kao posećen. Zatim se među susedima čvora \(u\) pronalazi prvi neoznačeni sused \(v_1\), pa se iz čvora \(v_1\) rekurzivno pokreće obilazak u dubinu. Zatim se prelazi na sledećeg neoznačenog suseda \(v_2\) i iz njega se rekurzivno pokreće obilazak u dubinu. Postupak (trenutni rekurzivni poziv tj. obrada čvora \(u\)) se završava kada su označeni svi susedi čvora \(u\).

Primer 2.3.1. Razmotrimo neusmereni graf prikazan na slici 1: neka je on predstavljen listama susedstva tako da su čvorovi u svakoj listi navedeni leksikografski rastuće. Ako se na tom grafu pokrene obilazak u dubinu iz čvora \(c\) redom se obilaze čvorovi \(c,a,b,d,e\) (slika 2 levo), tako što se redom prolazi granama \((c,a)\), \((a,b)\), \((c,d)\) i \((d,e)\). Ako se obilazak u dubinu pokrene iz čvora \(b\), obilaze se redom čvorovi \(b,a,c,d,e\) (slika 2 desno), tako što se redom prolazi granama \((b,a)\), \((a,c)\), \((c,d)\) i \((d,e)\).

Obilazak grafa se uvek vrši sa nekim ciljem. Kako bi se različite primene uklopile u obilazak u dubinu, poseti čvora ili grane pridružuju se dve vrste obrade, ulazna obrada i izlazna obrada. Ulazna obrada vrši se u trenutku označavanja čvora. Izlazna obrada vrši se na kraju, kada su obrađeni svi susedi datog čvora. Ulazna i izlazna obrada zavise od konkretne primene algoritma DFS. Na taj način moguće je rešavanje različitih problema jednostavnim definisanjem ulazne i izlazne obrade.

Implementacija algoritma obilaska grafa u dubinu dat je u nastavku. U glavnoj funkciji obilazak se pokreće iz čvora \(0\). Jednostavnosti radi, graf će u narednim kodovima biti deklarisan kao globalna promenljiva (predstavljen je graf sa slike 1 pri čemu su čvorovi od \(a\) do \(e\) numerisani redom brojevima od \(0\) do \(4\)).

// reprezentacija grafa listama povezanosti
// graf je neusmeren, pa se svaka grana dva puta javlja u listi
vector<vector<Cvor>> listaSuseda;

// pomocna rekurzivna funkcija koja vrši DFS obilazak grafa iz datog cvora
void dfs(int cvor, vector<bool> &posecen) {
  posecen[cvor] = true;
  // ovde ide ulazna obrada
  
  // rekurzivno prolazimo kroz sve njegove susede
  // koje ranije nismo obisli
  for (int sused : listaSuseda[cvor])
    if (!posecen[sused])
      dfs(sused,posecen);

  // ovde ide izlazna obrada
}
  
// funkcija koja vrsi DFS obilazak datog grafa iz datog cvora
void dfs(int cvor){
  int brojCvorova = listaSuseda.size();
  vector<bool> posecen(brojCvorova, false);
  dfs(cvor, posecen);
}

int main() {
  // ucitavamo neusmeren graf
  int brojCvorova;
  cin >> brojCvorova;
  listaSuseda.resize(brojCvorova);
  int brojGrana;
  cin >> brojGrana;
  for (int i = 0; i < brojGrana; i++) {
     int cvorOd, cvorDo;
     cin >> cvorOd >> cvorDo;
     listaSuseda[cvorOd].push_back(cvorDo);
     listaSuseda[cvorDo].push_back(cvorOd);
  }
  
  // vrsimo obilazak od ucitanog pocetnog cvora
  int pocetniCvor;
  cin >> pocetniCvor;
  dfs(pocetniCvor);
  
  return 0;
}

Primer 2.3.2. Primer obilaska grafa u dubinu prikazan je na slici 3. Uz svaki čvor su prikazani njegovi redni brojevi u dolaznoj, odnosno odlaznoj DFS numeraciji (dolazna numeracija označava redosled kojim se pokretala ulazna obrada čvorova, a odlazna redosled u kom se završavala obrada čvorova tj. pokretala izlazna obrada čvorova, o čemu će više reči biti u nastavku).

Prilikom izvršavanja algoritma DFS na neusmerenom grafu \(G=(V,E)\) koji je zadat listama povezanosti, svaka grana se pregleda tačno dva puta, po jednom sa svakog kraja. Prema tome, ukupan broj izvršavanja tela petlje for u svim rekurzivnim pozivima algoritma DFS je \(O(|E|)\). S druge strane, broj rekurzivnih poziva je \(|V|\), pa se vremenska složenost algoritma DFS može opisati izrazom \(O(|V|+|E|)\). Primetimo da složenost obilaska grafa u dubinu zavisi od reprezentacije grafa: naime, ako bi graf bio zadat matricom povezanosti, onda bi prolazak kroz susede jednog fiksiranog čvora podrazumevao prolaz kroz odgovarajuću vrstu matrice, što je složenosti \(\Theta(|V|)\). Odatle zaključujemo da je prolazak kroz susede svakog od čvorova složenosti \(\Theta(|V|^2)\). Dakle, u slučaju algoritma obilaska u dubinu, obično se efikasnija implementacija dobija korišćenjem reprezentacije grafa listama povezanosti (naročito kada je graf redak, tj. kada svaki čvor ima relativno mali broj suseda).

Prostorna složenost algoritma DFS zavisi od maksimalne dubine rekurzije. U najgorem slučaju graf može imati oblik dugog puta i u tom slučaju je dubina rekurzije proporcionalna broju čvorova u grafu. Dakle, prostorna složenost algoritma DFS je u najgorem slučaju \(O(|V|)\).

Komponente povezanosti

Algoritam DFS se mora prilagoditi da bi korektno radio i u slučaju nepovezanih grafova. Naime, ako su posle prvog pokretanja opisanog algoritma svi čvorovi označeni, onda je graf povezan, i obilazak je završen. U protivnom, može se pokrenuti novi obilazak u dubinu polazeći od proizvoljnog neoznačenog čvora u grafu, itd. Prema tome, algoritam obilaska u dubinu se može iskoristiti kako bi se ustanovilo da li je graf povezan, odnosno za pronalaženje svih njegovih komponenti povezanosti.

Algoritam se lako implementira ako se pokuša pokretanje obilaska u dubinu redom iz svakog čvora grafa: za svaki čvor se proverava da li je posećen tokom obilaska ranijih čvorova (čime je već pridružen nekoj od ranijih komponenata) i ako jeste, preskače se pokretanje obilaska iz tog čvora.

U ovom i u narednim kodovima, jednostavnosti radi, pretpostavljamo da je graf predstavljen globalnom promenljivom listaSuseda.

// obilazak u dubinu iz cvora cvor
void dfs(int cvor, int brojKomponente, vector<int>& komponente) {
  // tekuci cvor pridruzujemo tekucoj komponenti
  komponente[cvor] = brojKomponente;
    
  // rekurzivno prolazimo kroz sve njegove susede
  // koje ranije nismo obisli
  for (int sused : listaSuseda[cvor])
    if (komponente[sused] == -1)
      dfs(sused, brojKomponente, komponente);
}

// za svaki cvor grafa se u vektor komponente upisuje
// redni broj komponente kojoj on pripada;
// funkcija vraca ukupan broj komponenata povezanosti
int komponentePovezanosti(vector<int>& komponente) {
  int brojCvorova = listaSuseda.size();
  komponente.resize(brojCvorova, -1);
  int brojKomponente = 0;
  // pokrecemo novi DFS obilazak iz prvog neposecenog cvora
  for (int cvor = 0; cvor < brojCvorova; cvor++)
    if (komponente[cvor] == -1) {
      dfs(cvor, brojKomponente, komponente);
      brojKomponente++;
    }
  return brojKomponente;
}
  
int ispisiKomponente() {
  // odredjujemo komponente povezanosti 
  int brojCvorova = listaSuseda.size();
  vector<int> komponente;
  int brojKomponenti = komponentePovezanosti(komponente);

  // ispisujemo rezultat
  cout << "Ukupan broj komponenti povezanosti je "
       << brojKomponenti << endl;
  for (int i = 0; i < brojCvorova; i++)
    cout << "Cvor " << i << " pripada komponenti "
         << komponente[i] << endl;
  return 0;
}

Iako se pretraga u dubinu može pozvati i više puta, i ovaj algoritam je vremenske složenosti \(O(|V|+|E|)\). Naime, obilazak komponente broj \(k\) biće složenosti \(O(|V_k| + |E_k|)\), gde je \(V_k\) broj čvorova, a \(E_k\) broj grana unutar te komponente. Zato se ukupno, tokom svih obilazaka zajedno obiđe \(O(|V|)\) čvorova i \(O(|E|)\) grana.

Mi ćemo najčešće razmatrati slučaj kada je graf povezan, jer se u opštem slučaju problem svodi na posebnu obradu svake komponente povezanosti.

Iterativne implementacije pomoću steka

Iako je jednostavna za razumevanje, mana rekurzivne implementacije je to što kod nekih grafova može doći do prekoračenja sistemske stek-memorije prilikom izvršavanja programa (to se može desiti ako postoji dugačak niz čvorova kojim se prolazi bez vraćanja unazad). Naime, rekurzivni pozivi koriste sistemski stek računara, na koji se smeštaju parametri aktuelnih rekurzivnih poziva (argumenti prosleđeni prilikom svakog od rekurzivnih poziva i vrednosti lokalnih promenljivih). Umesto sistemskog steka koji i na savremenim sistemima predstavlja veoma ograničen deo memorije (obično je u pitanju tek nekoliko megabajta) možemo u našem programu održavati poseban stek, koji može da zauzme mnogo više memorijskog prostora, jer se alocira u zonama kojima je pridruženo mnogo više memorije (na primer, u zoni hipa). Stoga je ponekad potrebno napraviti implementaciju obilaska u dubinu koja nije rekurzivna, a koja, kao što je to i inače često slučaj kod oslobađanja od rekurzije, zahteva korišćenje strukture podataka stek.

Verna varijanta: oslobađanje od rekurzije

Možemo primetiti da se tokom rekurzivnih poziva na sistemskom steku u svakom trenutku nalaze svi čvorovi na trenutnom putu od početnog do tekućeg čvora. Te informacije su nam potrebne zbog vraćanja unatrag. Naime, kada iz tekućeg čvora ne možemo preći dalje u neki neposećen čvor, čvor koja se na steku nalazi ispod tekućeg je onaj iz kojeg smo došli u tekući čvor i u koji treba da se vratimo (to je njegov roditeljski čvor). Prilikom izvršavanja rekurzivne funkcije, u svakom čvoru se izvršava petlja u kojoj se prolazi kroz neposećene susede tog čvora. Prilikom povratka u prethodni čvor potrebno je izvršiti narednu iteraciju te petlje. Stoga se u sistemskom stek okviru koji odgovara čvoru čuva i trenutna vrednost brojačke promenljive u sklopu te petlje (kako bi se nakon povratka u čvor ta promenljiva mogla uvećati i tako preći na naredni korak iteracije, tj. na narednog suseda). Naravno, sve se ovo dešava automatski (na sistemskom steku se čuvaju vrednosti svih lokalnih promenljivih), pa programer ne mora da vodi računa o tome. U sklopu nerekurzivne implementacije možemo imitirati ovaj postupak, tako što na steku koji ručno održavamo čuvamo uređen par koji sadrži oznaku roditeljskog čvora i brojač u petlji u tom roditeljskom čvoru tj. oznaku deteta tog roditelja koje je trenutno obrađeno.

// obilazak grafa u dubinu iz datog pocetnog cvora
void dfs(int pocetniCvor) {
   int brojCvorova = listaSuseda.size();
   vector<bool> posecen(brojCvorova, false);
   // na steku pamtimo roditeljski cvor u koji treba da se vratimo
   // i broj do sada obrađene dece u tom roditeljskom čvoru
   stack<pair<int, int>> stek;
   // prvi roditelj je pocetni cvor i za sada nije obrađeno 
   // ni jedno dete
   stek.emplace(pocetniCvor, 0);
   // ovo je prvi put da smo otkrili pocetni cvor, pa vrsimo njegovu
   // ulaznu obradu
   posecen[pocetniCvor] = true;
   cout << pocetniCvor << endl; // ulazna obrada
   // dok se stek ne isprazni
   while (!stek.empty()) {
       // skidamo roditeljski cvor sa steka
       auto [roditelj, i] = stek.top();
       stek.pop();
       // ako nisu još obrađena sva njegova deca
       if (i < listaSuseda[roditelj].size()) {
          // obradjujemo naredno dete
           
          // pamtimo na steku da je broj obradjene dece ovog roditelja 
          // uvećan za 1, tj. da kada se sledeci put u povratku vratimo
          // do ovog roditelja, da tada preskocimo trenutno dete
          stek.emplace(roditelj, i+1);
          // ako trenutno dete nije vec poseceno, sada ga posecujemo i
          // vrsimo njegovu ulaznu obradu
          int dete = listaSuseda[roditelj][i];
          if (!posecen[dete]) {
             posecen[dete] = true;
             cout << dete << endl; // ulazna obrada
             stek.emplace(dete, 0);
          }
       }
   }
}

Implementacija dobijena na ovaj način je jedina koja verno oslikava rekurzivni obilazak u dubinu. Moguće su i drugačije implementacije u kojima je kôd malo jednostavniji, međutim, videćemo da se svaka od njih po nečemu razlikuje od osnovne rekurzivne formulacije.

Pseudo DFS

Razmotrimo sada jednu moguću modifikaciju obilaska grafa implementiranog uz pomoć steka. Da ne bismo morali da prekidamo petlju i nastavljamo njeno izvršavanje posle prekida, možemo program organizovati tako da na stek odmah stavimo sve susede tekućeg čvora i da ih odmah označimo. Oznaka sada znači da je čvor stavljen na stek, tj. da je zakazano da će čvor u nekom narednom trenutku biti posećen, a ne da je već posećen i obrađen. Dakle, na steku čuvamo čvorove koje u budućnosti treba obraditi (kada ih stavimo na stek, smatramo da smo zakazali njihovu obradu). Čvor obično obrađujemo u trenutku kada ga skidamo sa steka. Nakon toga na stek stavljamo njegove susede za koje još nije zakazan obilazak. Opisani postupak izložen je u algoritmu 1.

\begin{algorithm}
\caption{Obilazak u dubinu -- formulacija sa stekom}

\begin{algorithmic}
\Procedure{DFS}{čvor $r$}
    \State{stavi početni čvor $r$ na stek}
    \While{stek nije prazan}
       \State{skini čvor $u$ sa vrha steka}
       \State{izvrši ulaznu obradu čvora $u$}
       \ForAll{sused $v$ čvora $u$}
       \If{čvor $v$ nije označen}\Comment{tj. nije mu zakazan obilazak}
          \State{stavi čvor $v$ na stek}
          \State{označi čvor $v$}\Comment{tj. zakazuje mu se obilazak}
       \EndIf
      \EndFor
    \EndWhile
\EndProcedure
\end{algorithmic}
\end{algorithm}

To što se čvor označava čim se prvi put stavi na stek, a ne tek kada se skida sa steka nam garantuje da će svaki čvor najviše jednom biti upisan na stek. Ipak ovo može uticati na promenu redosleda obilaska čvorova u odnosu na rekurzivnu implementaciju, tako da ovaj algoritam nije u striktnom smislu obilazak grafa u dubinu (zato se ponekad naziva pseudo DFS). Ipak, u većini primena dovoljno je samo da se garantuje da će se svaki čvor obići tačno jednom, pa ovaj algoritam često zadovoljava sve naše potrebe.

Čak iako se u ovoj varijanti svaki čvor stavlja samo jednom na stek, dubina steka (pa samim tim i potrošnja memorije) potrebna za izvršavanje algoritma može biti znatno veća nego što je slučaj sa prethodnom, vernom varijantom obilaska u dubinu. Naime, u vernoj varijanti obilaska u dubinu je broj elemenata na steku asimptotski jednak dužini najdužeg puta od početnog do nekog udaljenog čvora iz kog ne možemo dalje da se krećemo, dok se u pseudo DFS obilasku na steku istovremeno nalaze i svi susedi tih čvorova. Na primer, ako razmotrimo graf oblika zvezde u kom je jedan centralni čvor povezan sa \(N\) suseda, u vernoj varijanti bi se na stek stavio centralni čvor, a zatim bi se na stek stavljao, pa skidao jedan po jedan njegov sused, tako da je za obilazak dovoljan stek dubine 2. U pseudo DFS algoritmu bi, međutim, nakon centralnog čvora na stek odmah bilo dodato svih \(N\) suseda centralnog čvora, te je za obilazak potreban stek dubine \(N\) (naravno, u najgorem slučaju oba algoritma zahtevaju prostor \(O(N)\)).

Primer 2.3.3. Razmotrimo graf na slici 4. Neka je zadat listama povezanosti i neka su liste povezanosti sortirane u rastućem redosledu suseda.

Prilikom rekurzivnog obilaska u dubinu krenuvši od čvora \(1\), rekurzivno se prelazi na čvor \(2\), pa zatim na čvor \(4\). Pošto čvor \(4\) nema daljih neposećenih suseda vraćamo se nazad, sve do čvora \(1\) i nakon toga se posećuje čvor \(3\). Redosled obilaska i obrade čvorova je, dakle, \(1, 2, 4, 3\).

Prilikom pseudo DFS obilaska istog grafa iz čvora \(1\) na stek se najpre stavlja čvor \(1\). Zatim se taj čvor skida sa steka, obrađuje se i na stek se stavljaju njegovi susedi \(2\), \(3\) i \(4\). Zatim se skida i obrađuje čvor \(2\). On nema neposećenih suseda. Skida se zatim i obrađuje čvor \(3\), koji takođe nema neposećenih suseda. Na kraju se skida i obrađuje čvor \(4\), koji takođe nema neposećenih suseda. Redosled obilaska i obrade je, dakle, \(1, 2, 3, 4\), što je različito od stvarnog redosleda obilaska u dubinu koji zahteva da se iz čvora \(2\) pređe u do tada neposećeni čvor \(4\).

Na osnovu algoritma 1 veoma je jednostavno napraviti implementaciju u jeziku C++ (stoga je nećemo prikazivati).

Višestruko stavljanje čvorova na stek

Alternativa prethodnom algoritmu je da se označavanje čvorova vrši u trenutku kada se zaista posete tj. skinu sa steka, kao što je prikazano u opštem algoritmu za obilazak grafova na početku ovog poglavlja. Ovaj pristup opisan je u algoritmu 2.

\begin{algorithm}
\caption{Obilazak u dubinu -- formulacija sa stekom}

\begin{algorithmic}
\Procedure{DFS}{čvor $r$}
    \State{stavi početni čvor $r$ na stek}
    \While{stek nije prazan}
       \State{skini čvor $u$ sa vrha steka}
       \If{čvor $u$ nije označen}
          \State{označi čvor $u$}
          \State{izvrši ulaznu obradu čvora $u$}
          \ForAll{sused $v$ čvora $u$}
             \State{stavi čvor $v$ na stek}
          \EndFor
       \EndIf
    \EndWhile
\EndProcedure
\end{algorithmic}
\end{algorithm}

Pod pretpostavkom da se susedi na stek postavljaju u obratnom redosledu od onog u kom su navedeni u listi povezanosti, time se dobija isti redosled obilaska kao u rekurzivnoj implementaciji tj. u pitanju je zaista obilazak u dubinu. Mana je to što se isti elementi mogu više puta naći na steku, tako da je ponekad potrebna značajno veća dubina steka da se ceo graf obiđe. Naime, iako se na stek stavljaju samo neoznačeni čvorovi, oni se ne označavaju prilikom stavljanja već tek prilikom skidanja sa steka. Veoma je važno da se susedi označenih čvorova ne analiziraju kada se ti čvorovi skinu sa steka, jer bi se u suprotnom za isti čvor više puta prolazilo kroz liste suseda.

I ovu implementaciju je veoma jednostavno napraviti na osnovu datog algoritma, pa je nećemo prikazivati.

Primetimo da je izlaznu obradu čvora teže implementirati u (svim) nerekurzivnim implementacijama. Naime, izlaznu obradu tekućeg čvora je potrebno izvršiti tek kada sa steka bude skinut i poslednji njegov sused. Jedan način da se taj trenutak uoči je da se na stek pre suseda tekućeg čvora stavi specijalna oznaka čije skidanje sa steka ukazuje da je potrebno izvršiti izlaznu obradu tekućeg čvora.

Primetimo da je prostorna složenost nerekurzivnih verzija algoritma DFS jednaka maksimalnom broju čvorova koji se tokom algoritma nađu u steku, što je opet u najgorem slučaju \(O(|V|)\), kao i u rekurzivnoj implementaciji.

Konstrukcija DFS drveta i DFS numeracija

Prikazaćemo sada dve jednostavne a važne primene algoritma DFS — formiranje specijalnog povezujućeg drveta, takozvanog DFS drveta i numeraciju čvorova grafa DFS brojevima. Tekst u nastavku se odnosi na rekurzivni obilazak.

Prilikom obilaska grafa \(G\) u dubinu, u petlji kojom se prolaze svi susedi čvora \(u\) mogu se izdvojiti sve grane ka novooznačenim čvorovima \(v\). Preko izdvojenih grana dostižni su svi čvorovi povezanog neusmerenog grafa, pa je podgraf koga čine izdvojene grane povezan. Taj podgraf nema cikluse, jer se od svih grana koje vode u neki čvor, izdvaja samo jedna. Prema tome, izdvojene grane su grane podgrafa grafa \(G\) koji je u slučaju povezanog grafa povezujuće drvo, koje nazivamo DFS drvo grafa \(G\). Čvor iz koga se pokreće obilazak u dubinu je koren DFS drveta. Čak i ako se drvo ne formira eksplicitno, mnoge algoritme je lakše razumeti razmatrajući DFS drvo grafa \(G\).

U nastavku je dat program koji konstruiše DFS drvo datog grafa predstavljenog listama susedstva. DFS drvo biće predstavljeno u vidu vektora grana grafa.

// rekurzivna funkcija koja vrsi DFS obilazak grafa od datog cvora  i 
// uz to konstruise DFS drvo
void konstruisi_dfs_drvo(int cvor, vector<bool> &posecen,
                         vector<vector<int>> &dfs_drvo) {
  posecen[cvor] = true;
            
  // rekurzivno prolazimo kroz sve njegove susede
  // koje ranije nismo obisli
  for (int sused : listaSuseda[cvor]) {
    if (!posecen[sused]) {
      // u DFS drvo dodajemo granu iz tekuceg ka novom cvoru
      // i njoj suprotno usmerenu granu (jer je graf neusmeren)
      dfs_drvo[cvor].push_back(sused);
      dfs_drvo[sused].push_back(cvor);
      konstruisi_dfs_drvo(sused, posecen, dfs_drvo);
    }
  }
}
  
// funkcija koja vrsi DFS obilazak datog grafa iz datog cvora
// i konstruise i ispisuje DFS drvo
void ispisi_dfs_drvo(int cvor) {
  int brojCvorova = listaSuseda.size();
  vector<bool> posecen(brojCvorova, false);
  vector<vector<int>> dfs_drvo(brojCvorova);
  konstruisi_dfs_drvo(cvor, posecen, dfs_drvo);

  // stampamo grane grafa koje pripadaju DFS drvetu
  cout << "Grane DFS drveta su: "; 
  for (int i = 0; i < dfs_drvo.size(); i++)
    for (int j = 0; j < dfs_drvo[i].size(); j++)
      cout << "(" << i << "," << dfs_drvo[i][j] << ")" << endl;
}

Postoje dve varijante DFS numeracije čvorova:

• dolazna DFS numeracija, odnosno preOrder numeracija, kojom se čvorovi numerišu prema redosledu označavanja i
• odlazna DFS numeracija, odnosno postOrder numeracija, kod koje se čvorovi numerišu prema redosledu napuštanja.

Dolazni broj čvora \(v\) obeležavaćemo sa \(v.\mathit{Pre}\), a odlazni sa \(v.\mathit{Post}\). Dolazna i odlazna numeracija čvorova imaju primenu prilikom rešavanja raznih problema nad grafovima.

Naredna funkcija ispisuje čvorove u rastućem redosledu njihove dolazne DFS numeracije.

void dfs_preorder(int cvor, vector<bool> &posecen) {
  posecen[cvor] = true;
  // stampamo naredni cvor u preOrder numeraciji
  cout << cvor << " ";
  
  // rekurzivno prolazimo kroz sve susede koje nismo obisli
  for (int sused : listaSuseda[cvor])
    if (!posecen[sused])
      dfs_preorder(sused,posecen);
}

Naredna funkcija ispisuje čvorove u rastućem redosledu njihove odlazne DFS numeracije.

void dfs_postorder(int cvor, vector<bool> &posecen) {
  posecen[cvor] = true;
  
  // rekurzivno prolazimo kroz sve susede koje nismo obisli
  for (int sused : listaSuseda[cvor])
    if (!posecen[sused])
      dfs_postorder(sused,posecen);

  // stampamo naredni cvor u postOrder numeraciji
  cout << cvor << " ";
}

Alternativno, možemo implementirati funkcije kojima se za sve čvorove u grafu pamte, a na kraju ispisuju redni brojevi u dolaznoj i odlaznoj DFS numeraciji.

// za svaki cvor se pamti dolazni i odlazni redni broj
vector<int> dolazna;
vector<int> odlazna;
// naredni slobodan redni broj (odlazni i dolazni)
int rbr_dolazna = 0;
int rbr_odlazna = 0;

void dfs(int cvor, vector<bool> &posecen) {
  posecen[cvor] = true;
  
  // cvor dobija naredni dolazni redni broj
  dolazna[cvor] = rbr_dolazna;
  rbr_dolazna++;

  // rekurzivno prolazimo kroz sve susede koje do sada nismo obisli
  for (int sused : listaSuseda[cvor]) {
    if (!posecen[sused]) {
      dfs(sused,posecen);
    }
  }
  // cvor dobija naredni odlazni redni broj
  odlazna[cvor] = rbr_odlazna;
  rbr_odlazna++;
}

void dfs(int cvor) {
  int brojCvorova = listaSuseda.size();
  dolazna.resize(brojCvorova, -1);
  odlazna.resize(brojCvorova, -1);
  vector<bool> posecen(brojCvorova, false);

  dfs(cvor,posecen);
  
  cout << "Dolazna i odlazna numeracija cvorova:" << endl;
  for (int i = 0; i < brojCvorova; i++)
    cout << "Cvor " << i << ": " << dolazna[i]
         << "/" << odlazna[i] << endl;
}

U odnosu na proizvoljni čvor u drvetu, ostale čvorove možemo podeliti u četiri grupe: čvorovi koji su njegovi preci, čvorove koji su njegovi potomci, čvorove koji su levo od njega i čvorove koji su desno od njega (videti primer na slici 5).

Definišimo precizno ove odnose.

Čvor \(w\) nazivamo pretkom čvora \(v\) u DFS drvetu \(T\) sa korenom \(r\) (slika 6) ako je \(w\) na jedinstvenom putu od \(r\) do \(v\) u \(T\). Ako je čvor \(w\) predak čvora \(v\), onda je čvor \(v\) potomak čvora \(w\).

DFS drvo obuhvata sve čvorove povezanog grafa \(G\). Redosled dece svakog čvora u drvetu određen je listama povezanosti kojima se zadaje graf \(G\), pa se za svaka dva deteta istog čvora može reći koji je od njih levi (prvi po tom redosledu), a koji desni. Relacija levi – desni se prenosi na proizvoljna dva čvora \(u\) i \(v\) koji nisu u relaciji predak – potomak (slika 6). Za čvorove \(u\) i \(v\) tada postoji “najmlađi” zajednički predak \(w\) u DFS drvetu (to je onaj zajednički predak čiji nijedan potomak nije zajednički predak čorova \(u\) i \(v\)), kao i deca \(u'\) i \(v'\) čvora \(w\) takvi da je čvor \(u'\) predak čvora \(u\) i čvor \(v'\) predak čvora \(v\). Kažemo da je čvor \(u\) levo od čvora \(v\) ako i samo ako je čvor \(u'\) levo od čvora \(v'\). Geometrijska interpretacija ove relacije je jasna: DFS drvo ćemo iscrtavati naniže prilikom prelaska u nove – neoznačene čvorove (koraci u dubinu), odnosno sleva udesno prilikom dodavanja novih grana posle povratka u već označene čvorove.

Relacije predak–potomak i levi–desni se mogu okarakterisati i korišćenjem dolazne i odlazne numeracije čvorova.

Redosled obrade čvorova je odozgo-naniže, sleva-nadesno, pa se pre bilo kog čvora obeležavaju čvorovi levo od njega i čvorovi iznad njega (njegovi preci), a posle njega se obeležavaju čvorovi ispod njega (njegovi potomci) kao i čvorovi desno od njega. Dakle, ako su data dva čvora \(u\) i \(v\) takva da je \(u.\mathit{Pre} < v.\mathit{Pre}\), tada je \(u\) ili levo od \(v\) ili je predak čvora \(v\). Kako bismo znali koji od ta dva slučaja važi, potrebno je da uporedimo odlazne redne brojeve: manji odlazni brojevi ukazuju na čvorove levo, a veći na pretke. Sledeća lema nam daje potpunu karakterizaciju odnosa položaja čvorova na osnovu njihove DFS numeracije (videti primer na slici 5).

Dokaz. Na slici 7 prikazana su tri čvora grafa \(u\), \(v\) i \(w\) u okviru DFS drveta grafa. Čvorovi \(u\) i \(v\) su deca čvora \(w\), a čvor \(u\) je levo od čvora \(v\). Na slici su prikazani i vremenski intervali trajanja rekurzivnih poziva algoritma DFS za svaki od ovih čvorova. Prvo se pokreće DFS obilazak čvora \(w\), nakon toga se pokreće DFS obilazak čvora \(u\), zatim se taj obilazak završava, pa se poziva DFS obilazak čvora \(v\), nakon toga se taj obilazak završava i na kraju se završava DFS obilazak čvora \(w\).

Bilo koji potomak čvora \(w\) (recimo \(w'\)) se nalazi unutar poddrveta sa korenom čiji je koren neko dete čvora \(w\) (to su \(u\), \(v\), \(\ldots\)), pa mora da ima veći dolazni DFS broj od dolaznog broja čvora \(w\) tj. važi \(w'.\mathit{Pre} > w.\mathit{Pre}\). Zapažamo da je DFS algoritam pokrenut iz čvora bilo kog potomka čvora \(w\), aktivan samo u podintervalu vremena za koje je aktivan DFS algoritam iz čvora \(w\). DFS pretraga iz bilo kog čvora \(w'\) koji je potomak čvora \(w\) završava se pre završetka DFS pretrage iz čvora \(w\). Prema tome, iz činjenice da je neki čvor \(w'\) potomak čvora \(w\) sledi da je \(w'.\mathit{Post} < w.\mathit{Post}\).

Ako je neki čvor \(u'\) levo od nekog čvora \(v'\), onda \(u'\) mora biti u poddrvetu čiji je koren \(u\), a \(v'\) u poddrvetu čiji je koren \(v\) (za neko \(u\), \(v\) koji imaju zajedničkog roditelja \(w\) i \(u\) je levo od \(v\)). DFS obilazak za svaki čvor u poddrvetu sa korenom \(u\) i počinje i završava se pre DFS obilaska bilo kog čvora u poddrvetu sa korenom \(v\). Zato je \(u'.\mathit{Pre} < v'.\mathit{Pre}\) i \(u'.\mathit{Post} < v'.\mathit{Post}\). \(\Box\)

Primetimo da prethodna lema daje potpunu karakterizaciju odnosa položaja čvorova u drvetu (postoji četiri moguća odnosa položaja i četiri odnosa parova rednih brojeva u dolaznoj i odlaznoj numeraciji) – u sva četiri slučaja važe ekvivalencije (odnos položaja važi ako i samo ako važi navedeni odnos rednih brojeva).

Na slikama 3 i 5 se vidi da sve grane neusmerenog grafa spajaju pretke i potomke tj. da grane ne mogu biti poprečne u odnosu na DFS drvo, odnosno ne povezuju čvorove na razdvojenim putevima od korena (tj. dva čvora koja su u odnosu levo – desno). Zaista, ako bi takva grana postojala, DFS algoritam bi “prošao” njome i uključio je u DFS drvo. Naredna lema precizno izražava ovu karakterizaciju grana grafa u odnosu na DFS drvo.

Usmereni grafovi

Procedura pretrage u dubinu usmerenih grafova ista je kao za neusmerene grafove.

Algoritam DFS za povezan neusmereni graf, započet iz proizvoljnog čvora, obilazi ceo graf. Analogno tvrđenje ne mora biti tačno za usmerene grafove. Preciznije, ovo tvrđenje će važiti samo ako je graf jako povezan (o čemu će biti više reči u poglavlju 2.6). Posmatrajmo usmereni graf na slici 8. Ako se DFS pretraga započne iz čvora \(c\), onda će biti dostignuti samo čvorovi u desnoj koloni (\(c\), \(f\) i \(i\)). DFS pretraga može da dostigne sve čvorove grafa samo ako se započne iz čvora \(a\). Ako se čvor \(a\) ukloni iz grafa zajedno sa dve grane koje izlaze iz njega, onda u datom grafu ne postoji čvor iz koga algoritam DFS obilazi ceo graf. Prema tome, uvek kad govorimo o DFS obilasku usmerenog grafa, smatraćemo da je algoritam DFS pokrenut onoliko puta koliko je potrebno da bi svi čvorovi bili označeni i sve grane bile razmotrene. Dakle, u opštem slučaju usmereni graf umesto DFS drveta ima DFS šumu.

Jedinstveno DFS drvo se može obezbediti tako što se u graf doda novi čvor \(v\) ulaznog stepena \(0\), koji se poveže granama sa svim čvorovima grafa \(G\) (slika 9) – tada DFS obilazak pokrenut iz čvora \(v\) sigurno obilazi sve čvorove grafa \(G\) i postoji jedinstveno DFS drvo.

Čak i kada su jedinstvena za ceo graf, usmerena DFS drveta imaju nešto drugačije osobine od DFS drveta za neusmerene grafove.

I u DFS šumi kod usmerenih grafova važe iste vrste odnosa između čvorova kao i kod neusmerenih grafova (odnosi predak-potomak i levo-desno) i lema 2.3.1 koja daje karakterizaciju ovih odnosa na osnovu dolazne i odlazne DFS numeracije ostaje na snazi. Naime, odnos trajanja rekurzivnih poziva prikazan na slici 7 i dalje važi. Iako to nije pokazano na slici 7, isti zaključak je tačan i ako su čvorovi \(v\) i \(w\) u različitim drvetima DFS šume, pri čemu je drvo čvora \(v\) levo od drveta čvora \(w\).

Međutim, karakterizacija grana je drugačija. Na primer, nije više tačno da graf ne može imati poprečne grane, što se može videti iz primera na slici 10. U odnosu na DFS drvo grane usmerenog grafa pripadaju jednoj od četiri kategorije:

• grane DFS drveta,
• povratne,
• direktne i
• poprečne grane.

Prve tri vrste grana povezuju dva čvora od kojih je jedan potomak drugog u DFS drvetu (slika 10):

• grana DFS drveta povezuje roditelja sa detetom,
• povratna grana povezuje potomka sa pretkom,
• direktna grana povezuje pretka sa potomkom.

Ove vrste grana postoje i kod neusmerenih grafova, jedino što se ne pravi razlika između direktnih i povratnih grana (one spajaju pretke i potomke, ali nisu usmerene, pa ih ne možemo razlikovati).

Novina su poprečne grane, koje povezuju čvorove koji nisu “srodnici” u drvetu. Poprečne grane, međutim, moraju biti usmerene “zdesna ulevo” (od čvorova sa većim ka čvorova sa manjim dolaznim brojevima), kao što pokazuje sledeća lema. Naime, kod neusmerenog grafa DFS algoritam uvek može “preći” preko poprečne grane, dok kod usmerenog grafa može preći preko grana usmerenih sleva nadesno (zato one postaju grane grafa i nikad nisu poprečne).

I karakterizaciju grana usmerenog grafa u odnosu na DFS drvo moguće je izvršiti na osnovu dolazne i odlazne numeracije čvorova grafa. U nastavku ćemo dokazati niz lema koje doprinose konačnoj klasifikaciji. Na slici 11 ilustrovana je veza vrednosti dolaznih i odlaznih rednih brojeva krajeva grane i njenog tipa.

Nepostojanje poprečnih grana u odnosu na DFS drvo koje idu sleva udesno pomaže da se numeracija čvorova grafa upotrebi za klasifikaciju četiri vrste grana u odnosu na DFS drvo.

Dokažimo sledeću karakterizaciju povratnih grana.

Na osnovu svega prethodnog sledi sledeća lema.

U nastavku je prikazan program kojim se za svaku granu usmerenog grafa određuje njen tip u odnosu na DFS drvo, na osnovu dolazne i odlazne numeracije čvorova.

// vrednosti dolazne i odlazne numeracije
vector<int> dolazna;
vector<int> odlazna;
// naredni slobodni redni broj (dolazni i odlazni)
int rbr_dolazna = 0;
int rbr_odlazna = 0;
// roditelj svakog cvora u DFS drvetu
vector<int> roditelj;

void dfs(int cvor) {
  // cvor dobija naredni dolazni redni broj
  dolazna[cvor] = rbr_dolazna;
  rbr_dolazna++;
  // rekurzivno prolazimo kroz sve susede koje do sada nismo obisli
  for (int sused : listaSuseda[cvor]) {
    if (dolazna[sused] == -1) { // !posecen[sused]
      // 'cvor' je roditelj cvora 'sused' u DFS drvetu 
      roditelj[sused] = cvor;
      dfs(sused);
    }
  }
  // cvor dobija naredni odlazni redni broj
  odlazna[cvor] = rbr_odlazna;
  rbr_odlazna++;
}

// klasifikuju se grane DFS drveta dobijenog obilaskom grafa 
// krenuvši od datog čvora 
void klasifikuj_grane(int cvor) {
  int brojCvorova = listaSuseda.size();
  dolazna.resize(brojCvorova, -1);
  roditelj.resize(brojCvorova, -1);
  odlazna.resize(brojCvorova, -1);
  
  dfs(cvor);
  
  cout << "Dolazna i odlazna numeracija cvorova:" << endl;
  for (int i = 0; i < brojCvorova; i++)
    cout << "Cvor " << i << ": " << dolazna[i]
         << "/" << odlazna[i] << endl;

  cout << "Tipovi grana datog usmerenog grafa: " << endl;
  for (int i = 0; i < listaSuseda.size(); i++)
    for (int j = 0; j < listaSuseda[i].size(); j++) {
      int k = listaSuseda[i][j];
      
      if (i == roditelj[k])
         cout << i << "-" << k << " je grana DFS drveta" << endl;
      else if (odlazna[i] <= odlazna[k])
         cout << i << "-" << k << " je povratna grana" << endl;
      else // odlazna[i] > odlazna[j]
         if (dolazna[i] < dolazna[k])
            cout << i << "-" << k << " je direktna grana" << endl;
         else 
            cout << i << "-" << k << " je poprecna grana" << endl;
    }
}

Provera postojanja ciklusa

Pokazaćemo sada kako se algoritam DFS pretrage može iskoristiti za utvrđivanje da li je dati graf aciklički.

Na osnovu prethodne leme zaključuje se da se algoritam za proveru da li graf sadrži ciklus može svesti na DFS pretragu grafa, određivanje odlazne DFS numeracije čvorova datog grafa i proveru postojanja povratne grane. Složenost ovog algoritma je \(O(|V|+|E|)\).

2.3.2 Obilazak u širinu

Druga važna tehnika obilaska grafa je obilazak u širinu ili pretraga u širinu (ili BFS, što je skraćenica od breadth–first–search). Ona podrazumeva obilazak grafa na sistematičan način, redom, po udaljenosti čvorova od početnog (gde pod udaljenošću nekog čvora podrazumevamo broj grana na najkraćem putu od početnog do tog čvora).

Obilazak u širinu se vrši na praktično isti način i kod neusmerenih i kod usmerenih grafova (razlike do kojih može doći ćemo posebno opisati).

Ovaj način obilaska je čini pogodnom za traženje najkraćih puteva ( puteva sa najmanjih brojem grana) od čvora iz koga pretraga kreće. Razmotrimo graf poznanstava korisnika neke društvene mreže: pretraga u širinu može se iskoristiti za pronalaženje najmanje udaljenosti (u terminima broja osoba) između dva korisnika u mreži. Slično, u algoritmima rutiranja u mrežama računara pretragom u širinu se može odrediti najkraći put između dva čvora u mreži.

Pretraga grafa u širinu može biti korisna i u drugim kontekstima. Veb, kao složena mreža veb stranica međusobno povezanih vezama (linkovima), se može prirodno razmatrati kao jedan veliki i složen graf čiji čvorovi odgovaraju pojedinačnim veb stranicama, dok grana od jednog čvora do drugog čvora postoji ako i samo ako na prvoj veb stranici postoji link ka drugoj veb stranici. Interesantan problem jeste indeksiranje veb stranica, koje koriste pretraživači za veb kako bi ažurirali svoj sadržaj ili indekse sadržaja drugih veb stranica. Pošto je u ovom problemu cilj da se krećemo sistematično počev od neke veb stranice, to možemo postići pretragom grafa u širinu, koja u prvom koraku obilazi sve stranice ka kojima sa polazne stranice postoji veza, u narednom koraku se posećuju njihove veze, itd.

Kao i u slučaju obilasku u dubinu, obilazak u širinu implicitno određuje drvo koje se u ovom slučaju naziva drvo pretrage u širinu (BFS drvo). Pretpostavimo da je graf zadat listama povezanosti. Ako BFS obilazak pokrenemo iz čvora \(v\), onda čvor \(v\) postaje koren BFS drveta. Nakon čvora \(v\) posećuju se svi susedi čvora \(v\) redosledom određenim redosledom u listi povezanosti grafa i oni postaju deca čvora \(v\) u BFS drvetu (čvorovi nivoa 1). Zatim se dolazi do svih njihovih neposećenih suseda, odnosno do “unuka” polaznog čvora (čvorovi nivoa 2), i tako dalje. Prilikom obilaska čvorovi se mogu numerisati BFS brojevima, slično kao pri obilasku u dubinu. Preciznije, čvor \(w\) ima BFS broj \(k\) ako je on \(k\)-ti po redu čvor označen u toku obilaska algoritmom BFS. BFS drvo grafa formira se uključivanjem samo grana ka novooznačenim čvorovima: lako se pokazuje da je u slučaju polaznog neusmerenog grafa dobijeni podgraf povezan i da nema ciklus, jer od svih grana koje vode nekom čvoru uključujemo tačno jednu. Ako graf nije povezan, obilazak se može pokrenuti zasebno u svakoj komponenti povezanosti (na taj način se dobija BFS šuma).

Zapaža se da izlazna obrada kod obilaska u širinu, za razliku od obilaska u dubinu, nema smisla; obilazak nema povratak “naviše”, već se, polazeći od korena, kreće samo naniže.

Primer 2.3.5. Za graf prikazan na slici 12 prikazan je postupak obilaska u širinu pokrenut iz čvora \(a\): nakon čvora \(a\) posećuju se njegovi susedi – čvorovi \(b\), \(c\) i \(d\) i oni postaju čvorovi nivoa 1. Nakon njih se obilaze neposećeni susedi čvora \(b\) – to je jedino čvor \(e\), pa čvor \(f\) kao jedini neposećeni sused čvora \(c\) i konačno čvor \(g\) kao neposećeni sused čvora \(d\): čvorovi \(e\), \(f\) i \(g\) postaju čvorovi nivoa 2 u BFS drvetu. Daljom analizom možemo utvditi da nijedan od čvorova \(e\), \(f\) i \(g\) nema neposećenih suseda, te se obilazak u širinu završava. Grane grafa koje pripadaju BFS drvetu istaknute su isprekidanom linijom, a uz svaki čvor prikazana je njegov redni broj u BFS numeraciji.

Kako realizovati pretragu u širinu? Čvorove obilazimo u željenom redosledu korišćenjem pogodne strukture podataka: sve neposećene susede tekućeg čvora smeštamo u datu kolekciju i potrebno ih je obraditi u redosledu dodavanja u tu kolekciju. U ove svrhe možemo iskoristiti red kao strukturu podataka. Čvorovi se obeležavaju čim se postave u red (tj. čim im se zakaže budući obilazak). Ovim se obezbeđuje da se ni jedan čvor neće dva puta staviti u red tj. da će red uvek sadržati različite čvorove. Zato je maksimalni broj elemenata koji mogu biti u redu jednak \(|V|\), što omogućava da se red implementira i uz pomoć običnog niza dužine \(|V|\).

Prikažimo na koji način se može realizovati pretraga u širinu ako je graf povezan i ako je zadat listama povezanosti (ako graf nije povezan svaka njegova komponenta se obilazi zasebno). Prilikom pretrage štampamo čvorove grafa u redosledu određenom BFS numeracijom čvorova i konstruišemo BFS drvo. BFS drvo ćemo predstaviti listom grana. Pretpostavićemo da je graf usmeren, te da pri dodavanju grane \((u,v)\) u BFS drvo ne treba dodavati i njoj simetričnu granu \((v,u)\).

// pretraga grafa u sirinu pokrenuta iz cvora cvor
// pretpostavljamo da je graf usmeren
void bfs(int cvor) {
  int brojCvorova = listaSuseda.size();
  vector<bool> oznacen(brojCvorova, false);
  vector<vector<int>> bfs_drvo(brojCvorova);

  // red u kom cuvamo cvorove u redosledu kojim ih treba posetiti
  queue<int> red;
  red.push(cvor);
  oznacen[cvor] = true;
  // stampamo prvi cvor u redosledu BFS numeracije
  cout << cvor << endl;
  while (!red.empty()) {
    // dohvatamo element sa pocetka reda i uklanjamo ga iz kolekcije
    int cvor = red.front();
    red.pop();
    for (int sused : listaSuseda[cvor]) {
      // neoznacene susede tekuceg cvora dodajemo u red
      if (!oznacen[sused]) {
        oznacen[sused] = true;
        // stampamo naredni cvor u skladu sa BFS numeracijom 
        cout << sused << endl;
        // dodajemo odgovarajucu granu u bfs drvo
        bfs_drvo[cvor].push_back(sused);
        red.push(sused);
      }
    }
  }
  cout << "Grane BFS drveta su: ";
  for (int i = 0; i < bfs_drvo.size(); i++)
    for (int j = 0; j < bfs_drvo[i].size(); j++)
      cout << "(" << i << "," << bfs_drvo[i][j] << ")" << endl;
}

Lako je uveriti se da se prilikom BFS obilaska datog povezanog grafa svaki čvor obrađuje po jednom i da se svaka grana pregleda po jednom u slučaju usmerenog grafa, odnosno dva puta ako je graf neusmeren (grana se smatra pregledanom kada se u toku pretrage iz njenog početka naiđe na njen kraj). Stoga je vremenska složenost algoritma pretrage u širinu \(O(|V|+|E|)\). Slično kao i kod pretrage u dubinu, ako je graf predstavljen matricom povezanosti, složenost pretrage u širinu jednaka je \(\Theta(|V|^2)\), jer je prolaz kroz sve susede nekog čvora složenosti \(\Theta(|V|)\). Dakle, obično je pretraga u širinu efikasnija kada je graf predstavljen listama povezanosti, posebno ako je graf redak.

Prostorna složenost algoritma BFS zavisi od maksimalnog broja čvorova koji će red sadržati tokom izvršavanja algoritma. U situaciji kada je polazni čvor povezan sa svim ostalim čvorovima, nakon polaznog čvora će u red biti dodati svi preostali čvorovi. Dakle, prostorna složenost algoritma BFS je u najgorem slučaju \(O(|V|)\).

Primer 2.3.6. Razmotrimo primer izvršavanja algoritma obilaska u širinu pokrenutog iz čvora \(a\) na primeru grafa sa slike 13. Neka redosled suseda čvorova u listi povezanosti kojom je predstavljen graf odgovara leksikografski rastućem poretku oznaka čvorova.

• Najpre iz reda uzimamo i posećujemo čvor \(a\), a u red dodajemo njegove neposećene susede: čvor \(b\) i čvor \(c\).

• Iz reda uzimamo i posećujemo čvor \(b\), a dodajemo njegove neposećene susede: čvorove \(g\) i \(h\) redom. Zatim iz reda uzimamo i posećujemo čvor \(c\), a u red dodajemo njegove neposećene susede: čvor \(i\).

• Iz reda uzimamo i posećujemo čvor \(g\), a u red dodajemo njegove neposećene susede: čvorove \(e\) i \(f\). Zatim iz reda uzimamo i posećujemo čvor \(h\) koji nema neposećenih suseda. Zatim iz reda uzimamo i posećujemo čvor \(i\), a u red dodajemo njegove neposećene susede: čvor \(d\).

• Nakon ovoga redom iz reda uzimamo i posećujemo čvorove \(e\), \(f\) i \(d\) i zaključujemo da nijedan od njih nema neposećenih suseda i pretraga se završava.

Stanje reda tokom obilaska je prikazano na slici 13, desno. Grane BFS drveta su na slici 13 levo prikazane plavom bojom, a uz svaki čvor prikazan je njegov broj u okviru BFS numeracije.

Primer 2.3.7. Na slici 14 prikazani su obilazak u dubinu i obilazak u širinu jednog neusmerenog grafa. Pretpostavljamo da je graf predstavljen listama povezanosti i da su čvorovi u listama povezanosti navedeni u leksikografski rastućem poretku. U levom delu slike prikazan je postupak pretrage u dubinu pokrenut iz čvora \(a\): uz svaki čvor prikazan je njegov redni broj u dolaznoj DFS numeraciji, a plavom bojom su istaknute grane koje pripadaju DFS drvetu grafa. U desnom delu slike ilustrovan je postupak pretrage u širinu pokrenut iz čvora \(a\): uz svaki čvor prikazana je njegov redni broj u BFS numeraciji, a plavom bojom su istaknute grane koje pripadaju BFS drvetu grafa.

Primetimo da kod neusmerenih grafova u odnosu na BFS drvo mogu postojati jedino grane BFS drveta i poprečne grane (setimo se da u neusmerenom grafu u odnosu na DFS drvo nisu mogle da postoje poprečne grane).

U nastavku ćemo formulisati nekoliko tvrđenja koja važe za obilazak u širinu, odnosno za BFS drvo grafa.

Definišimo rastojanje \(\mathrm{d}(u,v)\) između čvorova \(u\) i \(v\) kao dužinu najkraćeg puta od čvora \(u\) do čvora \(v\), s tim da se pod dužinom puta podrazumeva broj grana koje čine taj put. Nivo čvora \(v\) u odnosu na BFS drvo sa korenom \(u\) jednak je rastojanju \(\mathrm{d}(u,v)\).

Primetimo da analogno tvrđenje ne važi nužno u slučaju da je graf usmeren. Na slici 17 je prikazan usmeren graf koji sadrži grane koje povezuju dva čvora čiji se nivoi razlikuju za više od 1: na primer grane \((f,a)\) i \((g,a)\).

Pokretanje obilaska iz više čvorova istovremeno

Uobičajeno je da se obilazak grafa pokreće iz jednog polaznog čvora, međutim, nekada je obilazak u širinu moguće pokrenuti i iz više čvorova istovremeno. Pretpostavimo, recimo, da su u datom grafu neki čvorovi crveni, a neki plavi i da nas zanima najkraće rastojanje (mereno brojem grana jedinične dužine) između nekog crvenog i plavog čvora. Direktan pristup bi podrazumevao da se pokrene obilazak u širinu iz svakog crvenog čvora, da se izmeri rastojanje od njega do njemu najbližeg plavog čvora i da se odredi minimum tako dobijenih vrednosti. To bi zahtevalo da se obilazak u dubinu pokreće iznova za svaki crveni čvor, što može biti neefikasno (složenost može biti čak \(O(|V|^3)\)). Efikasniji pristup je da se obilazak pokrene istovremeno iz svih crvenih čvorova, što znači da se u početnom koraku svi istovremeno dodaju u red i da se svakom od njih pridruži rastojanje 0. Nakon toga, obilazak u širinu bi se nastavljao na uobičajeni način (uzimanjem elementa sa početka reda i dodavanjem u red njegovih neoznačenih suseda uz rastojanje uvećano za jedan u odnosu na rastojanje elementa sa početka reda), sve dok se ne naiđe na prvi plavi čvor, čime bi se dobilo traženo najkraće rastojanje između crvenih i plavih čvorova. Pošto se vrši samo jedan obilazak, složenost ovog algoritma je \(O(|V|+|E|)\), što je u najgorem slučaju \(O(|V|^2)\).

Zadaci:

• Postavljanje računarske mreže
• Provera da li je graf bipartitan
• Avionska presedanja
• Kose crte