SVET PROGRAMIRANJA

Grafovi — BFS i DFS (osnove)


Čemu služe grafovi i stabla u praksi?

Kada se prvi put susretnemo sa grafovima i stablima, prirodno se nameće pitanje: čemu ovo zapravo služi i gde se koristi u praksi?

Grafovi i stabla nisu apstraktni koncepti koji postoje samo u teoriji algoritama. Naprotiv, oni su jedan od najčešće korišćenih modela za opisivanje problema iz stvarnog sveta, posebno kada postoji više objekata koji su međusobno povezani.

Stablo je poseban slučaj grafa koji ima hijerarhijsku strukturu. To znači da postoji jedan početni čvor (koren), a svi ostali čvorovi se granaju iz njega, bez ciklusa i bez povratnih veza.

Stabla se koriste kada želimo da predstavimo odnose tipa: roditelj – dete, nadređeni – podređeni ili opšte – specifično.

Zamislimo strukturu menija jednog sajta:

  • Početna
  • Algoritmi
    • Grafovi
      • BFS
      • DFS
    • Sortiranja
  • Kontakt

Ova struktura je čisto stablo. Svaka stranica ima svog „roditelja“, a putanja do nje je jedinstvena.

Upravo ovakve strukture koriste se u:

  • navigaciji web sajtova
  • menijima u aplikacijama
  • organizaciji fajlova i foldera

Graf koristimo kada odnosi između objekata nisu strogo hijerarhijski. Drugim rečima, kada objekti mogu biti povezani na više načina.

Primeri problema koji se prirodno modeluju grafovima su:

  • mapa gradova i puteva između njih
  • društvene mreže (korisnici i njihova prijateljstva)
  • računarske mreže
  • zavisnosti između zadataka

Kada imamo graf ili stablo, često želimo da odgovorimo na pitanja poput:

  • Da li postoji put između dva čvora?
  • Koji je najkraći put?
  • Koje sve čvorove možemo da dohvatimo?
  • U kom redosledu treba da ih obiđemo?

Tu na scenu stupaju algoritmi BFS i DFS.

BFS je posebno koristan kada tražimo:

  • najkraći put (u broju koraka)
  • rešenja po nivoima

DFS je koristan kada želimo:

  • da detaljno istražimo jednu granu problema
  • da proverimo postojanje ciklusa
  • da pretražimo sva moguća rešenja

Drugim rečima, grafovi i stabla nam omogućavaju da realne probleme prevedemo u strukturu nad kojom algoritmi mogu da rade.

U nastavku lekcije videćemo kako se BFS i DFS primenjuju na konkretnom grafu i zašto isti graf može dati različite redoslede obilaska, u zavisnosti od algoritma koji koristimo.

Graf je struktura podataka sastavljena od čvorova (vertex) i grana (edges) koje povezuju te čvorove. Grafovi se koriste za modelovanje mreža, puteva, društvenih veze, hijerarhija i mnogih realnih problema.

U algoritmici, poznavanje pretrage grafova je osnova za naprednije teme: Dijkstra, MST algoritmi, topološko sortiranje, DP na grafovima.



Predstavljanje grafa


Najčešći način na takmičenjima je lista suseda (adjacency list) jer je efikasna po memoriji i omogućava brzu obradu. 



vector<int> graf[100]; // za n čvorova

// primer dodavanja grane (neusmeren graf):
graf[1].push_back(2);
graf[2].push_back(1);

Terminologija:

  • usmeren graf – grane imaju smer (A → B)
  • neusmeren graf – veze su obostrane (A — B)
  • težinski graf – svaka grana ima vrednost (npr. dužina puta)
  • matrica susedstva – čuva se u formi n×n tabele (manje praktično)


Da bismo lakše razumeli razliku između algoritama BFS (Breadth-First Search) i DFS (Depth-First Search), prvo ćemo definisati konkretan graf nad kojim će se oba algoritma izvršavati.

Na slici ispod prikazano je stablo (poseban slučaj grafa) sa jednim početnim čvorom (korenom) i više povezanih čvorova. Ovaj graf će ostati nepromenjen tokom cele lekcije — menja se samo način na koji ga algoritmi obilaze.

Važno je da prvo jasno vidimo kompletan graf i sve njegove veze, jer će nam to pomoći da kasnije, korak po korak, pratimo kako BFS i DFS dolaze do različitih redosleda obilaska.

Vizuelni prikaz stabla sa čvorovima A, B, C, D, E, F i G, korišćen kao primer za BFS i DFS algoritme.
Slika 1. Primer stabla (grafa) koje ćemo koristiti za objašnjenje BFS (pretraga po širini) i DFS (pretraga po dubini). Graf je isti za oba algoritma — razlikuje se samo redosled obilaska čvorova.

Na prikazanom grafu čvor A predstavlja početni čvor (koren stabla). Iz njega se granaju čvorovi B, C i D. Čvor B ima dodatne potomke E i F, dok čvor D vodi do čvora G.

Ovaj graf ćemo koristiti kao referencu u nastavku. Bez obzira da li primenjujemo BFS ili DFS, struktura grafa ostaje ista — razlika je isključivo u redosledu kojim se čvorovi posećuju.

Na sledećoj slici videćemo kako se ovaj isti graf razlaže korak po korak za oba algoritma, uz jasno obeležen redosled obilaska i tok pretrage.

Slika 1: BFS vs DFS — razlika, primene i primeri u grafovima

Kao što se vidi na prethodnoj slici, BFS (pretraga po širini) obilazi graf nivo po nivo. Prvo se posećuju svi čvorovi koji su direktno povezani sa početnim čvorom, a tek zatim njihovi potomci. Ovaj algoritam koristi red (queue) za pamćenje čvorova.

Sa druge strane, DFS (pretraga po dubini) ide što dublje može duž jedne grane pre nego što se vrati nazad i nastavi sa sledećom granom. DFS se najčešće implementira pomoću stek strukture ili rekurzije.

Upravo zbog ove razlike u strategiji, BFS i DFS daju različite redoslede obilaska, iako rade nad istim grafom. Razumevanje ove vizualizacije je ključno za pravilnu primenu ovih algoritama u praksi.

Matrica susedstva — alternativno predstavljanje grafa


Pored liste suseda, graf se može predstaviti i pomoću matrice susedstva. To je dvodimenzionalni niz adj[n][n] gde:

  • adj[u][v] = 1 ako postoji grana između čvorova u i v
  • adj[u][v] = 0 ako ne postoji

Primer za neusmeren graf sa 4 čvora: 


    0 1 2 3
0 [ 0 1 1 0 ]
1 [ 1 0 0 1 ]
2 [ 1 0 0 0 ]
3 [ 0 1 0 0 ]

Kada koristiti koju reprezentaciju?


Lista suseda Matrica susedstva
Efikasna za retke grafove (malo grana) Dobra za guste grafove
Memorija: O(V + E) Memorija: O(V²)
Brza iteracija kroz susede Brza provera da li postoji grana (O(1))

U takmičarskom programiranju najčešće se koristi lista suseda, jer su grafovi obično veliki, ali sa relativno malo grana.

BFS — Breadth First Search (pretraga po širini)


Kada i zašto koristiti BFS


Algoritam BFS (pretraga po širini) koristimo kada želimo da istražimo čvorove grafa po nivoima, tj. prvo sve čvorove koji su najbliži polaznom, pa zatim sledeće i tako dalje. Ova osobina je od ključne važnosti kada tražimo najkraći put (u pogledu broja grana) između dva čvora u grafu, što je česta potreba u realnim problemima.

Na primer, zamislimo problem:

  • U lavirintu želimo da pronađemo najkraći put od ulaza do izlaza.
  • Na društvenoj mreži želimo da pronađemo najmanji broj koraka između dva korisnika (koliko „prijateljstava“ ih razdvaja).
  • U mreži računara istražujemo koji su čvorovi dostupni u minimalnom broju skokova od izvornog čvora.
BFS u ovakvim situacijama prvo istražuje sve susede početnog čvora, zatim njihove susede i tako dalje, što mu omogućava da pronađe najkraći broj prelaza kad god graf nema težine na granama.

BFS obilazi graf po nivoima. Prvo posećuje sve susede početnog čvora, zatim njihove susede, itd.

Koristi se za pronalaženje najkraćeg puta u ne-težinskom grafu.

Implementacija koristi red (queue).

Vizuelno objašnjenje BFS obilaska

Breadth-First Search (BFS) obilazi graf po nivoima. To znači da prvo obilazi sve čvorove udaljene 1 korak, zatim sve čvorove udaljene 2 koraka, itd.

Primer grafa:

        0
      /   \
     1     2
    / \     \
   3   4     5

Ako krenemo iz čvora 0, obilazak ide po nivoima:

  • Nivo 0: 0
  • Nivo 1: 1, 2
  • Nivo 2: 3, 4, 5

0 → 1 → 2 → 3 → 4 → 5

Zbog toga BFS garantuje da prvi put kada dođemo do nekog čvora, došli smo do njega najkraćim putem (po broju grana).


Praćenje udaljenosti (dist niz)

Da bismo zaista pronašli najkraće rastojanje, koristimo niz dist.

  • dist[i] = -1 znači da čvor još nije posećen
  • dist[start] = 0 jer je početni čvor udaljen 0 od sebe
  • Za svakog suseda važi:
    dist[sused] = dist[v] + 1

Pošto BFS obilazi graf po nivoima, vrednosti u dist nizu prirodno rastu po nivoima. 



#include <bits/stdc++.h>
using namespace std;

vector<int> graf[100];
int distanca[100];

void bfs(int start){

    queue<int> q;

    // Inicijalizacija dist niza
    for(int i = 0; i < 100; i++)
        distanca[i] = -1;

    q.push(start);
    distanca[start] = 0;

    while(!q.empty()){

        int v = q.front();
        q.pop();

        for(int sused : graf[v]){
            if(distanca[sused] == -1){
                distanca[sused] = distanca[v] + 1;
                q.push(sused);
            }
        }
    }
}

Tabela stanja tokom izvršavanja BFS

Sledeća tabela prikazuje kako se menja red (queue) i niz udaljenosti tokom izvršavanja algoritma za graf iz primera.

Korak Izvađen čvor Stanje reda Dist niz
Početak - [0] [0, -1, -1, -1, -1, -1]
1 0 [1, 2] [0, 1, 1, -1, -1, -1]
2 1 [2, 3, 4] [0, 1, 1, 2, 2, -1]
3 2 [3, 4, 5] [0, 1, 1, 2, 2, 2]
4 3 [4, 5] [0, 1, 1, 2, 2, 2]
5 4 [5] [0, 1, 1, 2, 2, 2]
6 5 [] [0, 1, 1, 2, 2, 2]

Vidimo da se vrednosti u dist nizu povećavaju po nivoima:

  • Čvor 0 ima udaljenost 0
  • Čvorovi 1 i 2 imaju udaljenost 1
  • Čvorovi 3, 4 i 5 imaju udaljenost 2

Prvi put kada dođemo do čvora, već smo pronašli njegovu najkraću udaljenost od početnog čvora. To je ključna osobina BFS algoritma.


Primer formiranja grafa


int main(){

    graf[0] = {1, 2};
    graf[1] = {0, 3, 4};
    graf[2] = {0, 5};
    graf[3] = {1};
    graf[4] = {1};
    graf[5] = {2};

    bfs(0);

    return 0;
}


Vizuelna animacija — BFS korak po korak

U nastavku je detaljan prikaz kako BFS prolazi kroz graf nivo po nivo. Posmatramo graf iz prethodnog primera i pokrećemo BFS iz čvora 0.

Struktura grafa

        0
       / \
      1   2
     / \   \
    3   4   5

Tabela izvršavanja BFS algoritma

Korak Izvađen čvor Stanje reda (queue) Dist niz Objašnjenje
Početak - [0] [0, -1, -1, -1, -1, -1] U red ubacujemo početni čvor 0 i postavljamo dist[0] = 0.
1 0 [1, 2] [0, 1, 1, -1, -1, -1] Otkrivamo susede 1 i 2. Njihova udaljenost je 1.
2 1 [2, 3, 4] [0, 1, 1, 2, 2, -1] Otkrivamo 3 i 4. Njihova udaljenost je 2.
3 2 [3, 4, 5] [0, 1, 1, 2, 2, 2] Otkrivamo 5. Njegova udaljenost je 2.
4 3 [4, 5] [0, 1, 1, 2, 2, 2] Nema novih čvorova.
5 4 [5] [0, 1, 1, 2, 2, 2] Nema novih čvorova.
6 5 [] [0, 1, 1, 2, 2, 2] Red je prazan — BFS se završava.

Objašnjenje po nivoima

Nivo 0: čvor 0

Nivo 1: čvorovi 1 i 2

Nivo 2: čvorovi 3, 4 i 5

BFS obilazi graf po nivoima jer koristi red (FIFO strukturu). To znači da se svi čvorovi udaljeni 1 obrađuju pre čvorova udaljenih 2, a svi udaljeni 2 pre onih udaljenih 3 itd.

Zašto je pronađena udaljenost najkraća?

Kada prvi put dođemo do nekog čvora, došli smo do njega najmanjim mogućim brojem grana.

Razlog je što BFS:

  • Prvo obilazi sve kraće puteve
  • Zatim prelazi na duže
  • Nikada se ne vraća na kraći put kasnije

Zato je BFS idealan algoritam za nalaženje najkraćih puteva u grafovima bez težina.

BFS sa računanjem udaljenosti (najkraći put)


Jedna od najvažnijih primena BFS algoritma je pronalaženje najkraće udaljenosti od početnog čvora do svih ostalih čvorova u netežinskom (neponderisanom) grafu.

Koristimo niz dist gde važi:

  • dist[v] = minimalan broj grana od početnog čvora do čvora v
  • Početno: sve vrednosti postavljamo na -1 (čvor nije posećen)
  • dist[start] = 0 jer je početni čvor udaljen 0 od sebe

Pošto BFS obilazi graf po nivoima, prvi put kada dođemo do čvora garantovano smo pronašli njegovu najkraću udaljenost. 



#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {

    int n, m;
    cin >> n >> m;
    // n = broj čvorova u grafu
    // m = broj grana

    // Kreiramo listu susedstva
    // adj[i] sadrži sve čvorove koji su povezani sa čvorom i
    vector<vector<int>> adj(n);

    // Učitavanje svih grana grafa
    for(int i = 0; i < m; i++) {

        int u, v;
        cin >> u >> v;
        // u i v predstavljaju čvorove koje povezuje grana

        adj[u].push_back(v);
        // dodajemo v u listu suseda čvora u

        adj[v].push_back(u);
        // dodajemo u u listu suseda čvora v
        // ovu liniju ukloniti ako je graf usmeren
    }

    // početni čvor iz kojeg računamo udaljenosti
    int start = 0; 
    // pretpostavlja se indeksiranje čvorova od 0 do n-1

    // dist[i] čuva najkraću udaljenost od start do i
    vector<int> dist(n, -1);
    // -1 znači da čvor još nije posećen

    queue<int> q;
    // red koji koristimo u BFS algoritmu

    dist[start] = 0;
    // udaljenost početnog čvora od samog sebe je 0

    q.push(start);
    // ubacujemo početni čvor u red

    // BFS petlja
    while(!q.empty()) {

        int u = q.front();
        // uzimamo čvor sa početka reda

        q.pop();
        // uklanjamo ga iz reda

        // prolazimo kroz sve susede čvora u
        for(int v : adj[u]) {

            // ako sused još nije posećen
            if(dist[v] == -1) {

                // njegova udaljenost je udaljenost od u + 1
                dist[v] = dist[u] + 1;

                // dodajemo ga u red kako bismo kasnije
                // obišli i njegove susede
                q.push(v);
            }
        }
    }

    // Ispis rezultata
    // prikazujemo najkraću udaljenost od start do svakog čvora
    for(int i = 0; i < n; i++) {

        cout << "Udaljenost od " 
             << start 
             << " do " 
             << i 
             << " je " 
             << dist[i] 
             << endl;
    }

    return 0;
}

Ako je neki čvor i dalje jednak -1 nakon izvršavanja algoritma, to znači da nije dostižan iz početnog čvora (graf nije potpuno povezan).

Detaljno objašnjenje — BFS sa računanjem udaljenosti

BFS algoritam omogućava pronalaženje najkraće udaljenosti od početnog čvora do svih ostalih čvorova u neponderisanom grafu.

Pošto sve grane imaju implicitnu težinu 1, najkraći put znači:

Put sa najmanjim brojem grana.

Šta predstavlja niz dist?

Koristimo niz dist[v] gde važi:

  • dist[v] = minimalan broj grana od početnog čvora do čvora v
  • Početno: sve vrednosti su -1 (čvor nije posećen)
  • dist[start] = 0

Vrednost -1 znači da do tog čvora još nismo došli.

Primer grafa

        0
       / \
      1   2
     / \   \
    3   4   5

Pokrećemo BFS iz čvora 0.

Vizuelna tabela izvršavanja

Korak Izvađen čvor Stanje reda dist niz Nivo
Početak - [0] [0, -1, -1, -1, -1, -1] 0
1 0 [1, 2] [0, 1, 1, -1, -1, -1] 1
2 1 [2, 3, 4] [0, 1, 1, 2, 2, -1] 2
3 2 [3, 4, 5] [0, 1, 1, 2, 2, 2] 2
4 3 [4, 5] [0, 1, 1, 2, 2, 2] --
5 4 [5] [0, 1, 1, 2, 2, 2] --
6 5 [] [0, 1, 1, 2, 2, 2] --

Šta primećujemo?

  • Nivo 0 → čvor 0
  • Nivo 1 → čvorovi 1 i 2
  • Nivo 2 → čvorovi 3, 4 i 5

BFS obilazi graf po nivoima jer koristi red (FIFO). Prvo se obrađuju svi čvorovi udaljeni 1, zatim svi udaljeni 2, itd.

Zašto je prvi dolazak do čvora najkraći put?

Kada prvi put dođemo do čvora v: 

dist[v] = dist[u] + 1

To znači da smo do njega stigli najkraćim mogućim putem, jer BFS nikada ne preskače nivoe.

Ne postoji način da kasnije pronađemo kraći put, pošto bi on morao imati manje grana, a svi kraći putevi su već obrađeni ranije.

Važna napomena

Ako nakon završetka algoritma važi: 

dist[i] == -1

to znači da čvor i nije dostižan iz početnog čvora.

Vremenska složenost

Za graf predstavljen listom susedstva:

O(n + m)

  • n — broj čvorova
  • m — broj grana

Ključna osobina BFS algoritma

Prvi put kada dođemo do čvora, već smo pronašli njegovu najkraću udaljenost.

Ova osobina važi samo za neponderisane grafove.

BFS na gridu (lavirint problem)


Graf ne mora uvek biti eksplicitno zadat. U problemima sa matricom (npr. lavirint), svako polje možemo posmatrati kao čvor, a prelazak na susedno polje kao granu.

Dozvoljena su kretanja: gore, dole, levo i desno. Svako pomeranje predstavlja jednu granu (jedan korak).

Ako je polje označeno znakom '.', smatramo da je prolazno. Ostali znakovi (npr. '#') mogu predstavljati zid. 


#include <iostream>
#include <queue>
using namespace std;

int main() {

    int n, m;
    cin >> n >> m;
    // n = broj redova matrice
    // m = broj kolona matrice

    char grid[1000][1000];
    // matrica koja predstavlja lavirint

    int dist[1000][1000];
    // dist[i][j] = minimalan broj koraka
    // od početnog polja do polja (i,j)

    // Učitavanje matrice i inicijalizacija dist niza
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < m; j++) {

            cin >> grid[i][j];
            // učitavamo karakter koji predstavlja polje

            dist[i][j] = -1;
            // -1 znači da polje još nije posećeno
        }
    }

    // BFS koristi red (queue)
    queue<pair<int,int>> q;

    // početna pozicija u lavirintu
    int startX = 0;
    int startY = 0;

    // početno polje ima udaljenost 0
    dist[startX][startY] = 0;

    // ubacujemo početno polje u red
    q.push({startX, startY});

    // Pomaci u 4 pravca kretanja
    // indeks 0 → dole
    // indeks 1 → gore
    // indeks 2 → desno
    // indeks 3 → levo
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};

    // Glavna BFS petlja
    while(!q.empty()) {

        // uzimamo trenutno polje iz reda
        auto [x, y] = q.front(); 
        // C++17 structured binding:
        // x = red, y = kolona

        q.pop();

        // proveravamo sva 4 susedna polja
        for(int d = 0; d < 4; d++) {

            int nx = x + dx[d];
            int ny = y + dy[d];
            // nx, ny predstavljaju novo polje

            // Provera da li smo unutar granica matrice
            if(nx >= 0 && nx < n && ny >= 0 && ny < m) {

                // Ako je polje prolazno i nije posećeno
                if(grid[nx][ny] == '.' && dist[nx][ny] == -1) {

                    // udaljenost je +1 korak od trenutnog polja
                    dist[nx][ny] = dist[x][y] + 1;

                    // ubacujemo novo polje u red
                    // kako bismo kasnije istražili njegove susede
                    q.push({nx, ny});
                }
            }
        }
    }

    return 0;
}

Pošto BFS obilazi polja po nivoima, dist[i][j] predstavlja minimalan broj koraka potrebnih da se dođe do tog polja od početne pozicije.

Ako neko polje ostane jednako -1, to znači da do njega nije moguće doći.

BFS na gridu je idealan za probleme minimalnog broja koraka. Ako problem zahteva optimizaciju sume (npr. minimalan zbir težina), dinamičko programiranje ili Dijkstra algoritam su bolji izbor.

Ako vas interesuje optimizacija puta kroz mrežu (npr. minimizacija sume) umesto samo broj koraka, pogledajte i Grid DP — dinamičko programiranje na matrici .

Vizuelni primer BFS pretrage u lavirintu

Razmotrimo sledeći jednostavan lavirint. Polje S predstavlja početnu poziciju, . su prolazna polja, a # su zidovi. 

S . . #
# . . #
# . . .
# # . E

Cilj je da pronađemo minimalan broj koraka od početnog polja S do svakog dostupnog polja u lavirintu.

Nakon izvršavanja BFS algoritma, matrica udaljenosti može izgledati ovako: 

0 1 2 X
X 2 3 X
X 3 4 5
X X 5 6
  • 0 označava početno polje
  • svaki broj predstavlja minimalan broj koraka od početne pozicije
  • X označava zid ili nedostižno polje

BFS obilazi polja po nivoima:

  • prvo sva polja udaljena 1 korak
  • zatim sva polja udaljena 2 koraka
  • zatim sva polja udaljena 3 koraka itd.

Zbog toga BFS uvek pronalazi najkraći put u grafovima bez težina, što ga čini idealnim algoritmom za probleme lavirinta i mreža.

Poređenje BFS i DFS

Iako oba algoritma služe za obilazak grafa, njihov način rada i primena su različiti.

Osobina BFS DFS
Struktura podataka Red (queue) Stek (stack) / Rekurzija
Način obilaska Po nivoima Dubinski (ide što dublje)
Najkraći put (netežinski graf) Da Ne garantuje
Tipična primena Najkraći put, minimalan broj koraka Komponente povezanosti, ciklusi
Memorija Može trošiti više (čuva nivo) Obično manja

Intuitivno:

  • BFS istražuje "širinu" grafa.
  • DFS istražuje "dubinu" grafa.

Ako vam je cilj minimalan broj koraka — koristite BFS.
Ako vam je cilj da obiđete sve komponente ili proverite cikluse — DFS je često prirodniji izbor.

DFS — Depth First Search (pretraga u dubinu)



Kada i zašto koristiti DFS


Algoritam DFS (pretraga u dubinu) koristi strategiju istraživanja jednog pravca u grafu „do kraja“ pre nego što se vrati i istraži druge pravce. Takav pristup je posebno koristan kada želimo da:

  • proverimo da li uopšte postoji put između čvorova;
  • odredimo da li graf sadrži ciklus;
  • pronađemo sve čvorove koji su deo iste komponente povezanosti;
  • izvedemo topološko sortiranje kada radimo sa usmerenim acikličkim grafovima.
Na primer:
  • u problemu pretrage lavirinta, DFS može istražiti jedan put do kraja i vratiti se ako je to bio „ćorsokak“;
  • u sistemu zadataka sa zavisnostima (npr. kompajliranje modula), DFS se koristi da se utvrdi redosled u kome se zadaci mogu izvršiti bez kršenja zavisnosti.
Ovaj stil pretrage naglašava dubinu, što može biti korisno kada nas više interesuje istraga kompletnog pod-grafa ili strukture nego pronalaženje najkraćeg puta.

Simulacija DFS korak-po-korak

Koristimo isti graf kao u BFS primeru:

        0
      /   \
     1     2
    / \     \
   3   4     5

DFS ide što dublje pre nego što se vrati nazad. Pretpostavimo da obilazimo susede redom kako su navedeni.

Početak

Krećemo iz čvora 0.

Korak 1

0 → prelazimo na 1 (prvi sused)

Korak 2

1 → prelazimo na 3

Korak 3

3 nema novih suseda → vraćamo se nazad na 1

Korak 4

Iz 1 prelazimo na 4

Korak 5

4 nema novih suseda → vraćamo se na 1 → zatim na 0

Korak 6

Iz 0 prelazimo na 2

Korak 7

2 → prelazimo na 5

Mogući redosled obilaska:

0 → 1 → 3 → 4 → 2 → 5

Vidimo da DFS ide duboko kroz jednu granu pre nego što se vrati. Za razliku od BFS-a, ne obilazi čvorove po nivoima.

DFS ide što dublje u graf dok ne dođe do kraja, pa se zatim vraća nazad (backtracking) i nastavlja pretragu iz prethodnog čvora. Najčešća implementacija DFS algoritma koristi rekurziju, što znači da funkcija poziva samu sebe za susedne čvorove.

DFS se često koristi za:

  • proveru povezanosti grafa
  • pronalaženje ciklusa
  • topološko sortiranje (usmereni grafovi)
  • otkrivanje komponenti povezanosti
  • pretragu lavirinta, stabala i drugih struktura


// Uključivanje svih standardnih C++ biblioteka
#include <bits/stdc++.h>
using namespace std;

// Lista susedstva grafa
// graf2[i] sadrži sve čvorove koji su povezani sa čvorom i
vector<int> graf2[100];

// Niz koji označava da li je čvor već posećen
// true  → čvor je već obrađen
// false → čvor još nije posećen
bool vidjen[100];

// DFS funkcija koja obilazi graf počevši od čvora v
void dfs(int v){

    // Označavamo trenutni čvor kao posećen
    vidjen[v] = true;

    // Ispisujemo trenutni čvor
    cout << v << " ";

    // Prolazimo kroz sve susede čvora v
    for(int sused : graf2[v]){

        // Ako sused još nije posećen
        // pozivamo DFS rekurzivno za taj čvor
        if(!vidjen[sused])
            dfs(sused);
    }
}

Poziv funkcije:


int main(){

    // Ručno formiranje neusmerenog grafa
    // Svaki čvor ima listu svojih suseda
    graf2[1] = {2, 3, 4};
    graf2[2] = {1, 3};
    graf2[3] = {1, 2, 4};
    graf2[4] = {1, 3};

    // Pokretanje DFS algoritma iz čvora 1
    // DFS će obilaziti graf što dublje
    dfs(1);

    return 0;
}


BFS vs DFS — poređenje


Karakteristika BFS DFS
Struktura podataka Red (queue) Rekurzija ili stek
Redosled pretrage Nivo po nivo (širina grafa) Ide što dublje pa se vraća nazad
Najkraći put? DA (ako graf nema težine) NE
Vremenska složenost O(V + E) O(V + E)
Primeri primene Najkraći put, pretraga u širinu Topološko sortiranje, ciklusi, komponente


Vežbe i zadaci


Probaj sledeće zadatke:

  • Izračunati udaljenost (broj koraka) svakog čvora od startnog koristeći BFS.
  • Prebrojati koliko čvorova postoji u komponenti povezanosti pomoću DFS-a.
  • Odrediti da li je graf povezan.
  • Napisati program koji proverava da li postoji ciklus u neusmerenom grafu.

Ova znanja su osnova za naredne teme kao što su: Dijkstra algoritam, MST (Kruskal i Prim) i topološko sortiranje.



Detekcija ciklusa pomoću DFS


Jedna od važnih primena DFS algoritma je detekcija ciklusa u grafu.

U neusmerenom grafu ciklus postoji ako tokom DFS obilaska naiđemo na već posećen čvor koji nije roditelj trenutnog čvora. 


#include <iostream>
#include <vector>
using namespace std;

// Lista susedstva grafa
// adj[i] sadrži sve čvorove povezane sa čvorom i
vector<vector<int>> adj;

// Niz koji označava da li je čvor već posećen
vector<bool> visited;

// Promenljiva koja označava da li graf sadrži ciklus
bool hasCycle = false;

// DFS funkcija
// u      - trenutni čvor
// parent - čvor iz kog smo došli u trenutni čvor
void dfs(int u, int parent) {

    // Označavamo trenutni čvor kao posećen
    visited[u] = true;

    // Prolazimo kroz sve susede čvora u
    for(int v : adj[u]) {

        // Ako sused još nije posećen
        // nastavljamo DFS obilazak
        if(!visited[v]) {

            dfs(v, u);

        }
        // Ako je sused već posećen
        // i nije roditelj trenutnog čvora
        // tada postoji ciklus u grafu
        else if(v != parent) {

            hasCycle = true;
        }
    }
}

int main() {

    int n, m;

    // n - broj čvorova
    // m - broj grana
    cin >> n >> m;

    // Kreiramo listu susedstva za n čvorova
    adj.resize(n);

    // Inicijalizujemo niz visited na false
    visited.assign(n, false);

    // Učitavanje grana grafa
    for(int i = 0; i < m; i++) {

        int u, v;

        // učitavamo krajeve grane
        cin >> u >> v;

        // Pošto je graf neusmeren,
        // dodajemo granu u oba smera
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // Pokrećemo DFS za svaki čvor
    // (potrebno ako graf nije povezan)
    for(int i = 0; i < n; i++) {

        if(!visited[i])
            dfs(i, -1);
    }

    // Ispis rezultata
    if(hasCycle)
        cout << "Graf sadrzi ciklus\n";
    else
        cout << "Graf nema ciklus\n";
}

Kod neusmerenog grafa moramo ignorisati granu ka roditelju, jer ona ne predstavlja ciklus. Kada tokom DFS obilaska naiđemo na već posećen čvor koji nije roditelj trenutnog čvora, to znači da postoji alternativni put do tog čvora i time je formiran ciklus u grafu.

Prikaz detekcije ciklusa u neusmerenom grafu pomoću DFS algoritma gde čvor B posećuje čvor C koji je već posećen i nije roditelj, što ukazuje na postojanje ciklusa u grafu.
Slika 2: DFS detekcija ciklusa u neusmerenom grafu: tokom obilaska iz čvora B pronalazimo već posećen čvor C koji nije roditelj, što znači da u grafu postoji ciklus.

Zadaci za vežbu — BFS i DFS


1. BFS — Najkraća udaljenost od početnog čvora

Tekst zadatka

Dat je neusmeren graf sa n čvorova. Potrebno je pomoću BFS algoritma izračunati najkraću udaljenost (broj grana) od početnog čvora s do svih ostalih čvorova u grafu.

Primer

Ulaz:
Graf:
1 - 2
1 - 3
2 - 4
3 - 4
Start = 1

Izlaz:
dist[1] = 0
dist[2] = 1
dist[3] = 1
dist[4] = 2

2. BFS — Provera povezanosti grafa

Tekst zadatka

Dat je neusmeren graf. Proveriti da li je graf povezan.


3. DFS — Broj čvorova u komponenti povezanosti

Tekst zadatka

Dat je neusmeren graf i početni čvor s. Pomoću DFS algoritma izračunati koliko čvorova pripada komponenti povezanosti u kojoj se nalazi čvor s.

Primer


Ulaz:
Graf:
1 - 2
2 - 3
4 - 5

Start = 1

Izlaz:
Broj čvorova u komponenti = 3


4. DFS — Detekcija ciklusa u neusmerenom grafu

Tekst zadatka

Dat je neusmeren graf. Potrebno je odrediti da li graf sadrži ciklus koristeći DFS algoritam.

Primer


Ulaz:
Graf:
1 - 2
2 - 3
3 - 1

Izlaz:
Graf SADRŽI ciklus


Zadaci iz prakse (realni problemi) — BFS i DFS


5. Najkraći put u mreži gradskih puteva (BFS)

Tekst zadatka

Grad je predstavljen kao ne-težinski graf u kome su čvorovi raskrsnice, a grane predstavljaju dvosmerne puteve između njih. Dato je N raskrsnica i lista puteva. Potrebno je pronaći najmanji broj puteva koje treba preći da bi se stiglo od raskrsnice S do raskrsnice T.

Primer


Ulaz:
5 6
1 2
1 3
2 4
3 4
4 5
2 5

S = 1, T = 5

Izlaz:
2

Objašnjenje:
Najkraći put je 1 → 2 → 5 (dve grane).


6. Evakuacija područja – provera povezanosti (DFS)

Tekst zadatka

Tokom elementarne nepogode, područje je podeljeno na zone. Zone su povezane prolazima i predstavljene su kao graf. Potrebno je proveriti da li su sve zone dostupne iz komandnog centra (zona 1). Ako neka zona nije dostupna, evakuacija nije moguća.

Primer


Ulaz:
6 4
1 2
2 3
3 4
5 6

Izlaz:
NE

Objašnjenje:
Zone 5 i 6 nisu povezane sa zonom 1.


Zadaci srednje težine — BFS i DFS


7. BFS — Rekonstrukcija najkraćeg puta (parent niz)

Tekst zadatka

Dat je neusmeren graf i dva čvora s i t. Pomoću BFS algoritma potrebno je pronaći najkraći put od čvora s do čvora t i ispisati sve čvorove koji se nalaze na tom putu.

Primer


Ulaz:
Graf:
1 - 2
1 - 3
2 - 4
3 - 4

Start = 1
Kraj = 4

Izlaz:
1 2 4


8. DFS — Broj komponenti povezanosti

Tekst zadatka

Dat je neusmeren graf sa n čvorova. Potrebno je pomoću DFS algoritma izračunati broj komponenti povezanosti u grafu.

Primer


Ulaz:
Graf:
1 - 2
2 - 3
4 - 5

Izlaz:
Broj komponenti = 2


Sledeća lekcija


Preporuka za nastavak:

Topološko sortiranje



Vraćanje na vodič za Grafove i stabla

← Mapa učenja — Grafovi i stabla

Algoritmi
Matrice
Java
Linkovi
​Politika Privatnosti
Kontakt

© 2025 by Slobodan svetprogramiranja.com

Sva prava zadržana
SVET PROGRAMIRANJA

Unesite lozinku

Ovo rešenje je za nastavnike.