Choose your language!

---

|

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

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.

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. :contentReference[oaicite:1]{index=1}

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

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

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

// Niz koji označava da li je čvor već posećen
bool posecen[100];

// BFS funkcija koja obilazi graf počev od čvora start
void bfs(int start){

    // Red koji čuva čvorove za obradu
    queue<int> q;

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

    // Označavamo početni čvor kao posećen
    posecen[start] = true;

    // BFS radi dok red nije prazan
    while(!q.empty()){

        // Uzimamo čvor sa početka reda
        int v = q.front();
        q.pop();

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

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

            // Ako sused još nije posećen,
            // označavamo ga i ubacujemo u red
            if(!posecen[sused]){
                posecen[sused] = true;
                q.push(sused);
            }
        }
    }
}

Primer upotrebe:

int main(){

    // Ručno formiranje neusmerenog grafa
    graf[1] = {2, 3, 4};
    graf[2] = {1, 3};
    graf[3] = {1, 2, 4};
    graf[4] = {1, 3};

    // Pokretanje BFS algoritma iz čvora 1
    bfs(1); // ispis: 1 2 3 4
}

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. :contentReference[oaicite:2]{index=2}

DFS ide što dublje u graf dok ne dođe do kraja, pa se vraća nazad. Najčešća implementacija je pomoću rekurzije.

DFS se često koristi za:

• proveru povezanosti grafa
• pronalaženje ciklusa
• topološko sortiranje (usmereni grafovi)
• otkrivanje komponenti u grafu
• pretragu lavirinta, stabala, šahovskih pozicija...

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

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

// Niz koji označava da li je čvor već posećen
bool vidjen[100];

// DFS funkcija koja obilazi graf počev 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,
        // rekurzivno pozivamo DFS za njega
        if(!vidjen[sused])
            dfs(sused);
    }
}

Poziv funkcije:

int main(){

    // Ručno formiranje neusmerenog grafa
    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(1);
}

BFS vs DFS — poređenje

Karakteristika	BFS	DFS
Struktura	Red (queue)	Rekurzija / stek
Redosled pretrage	Nivo po nivo	Ide do kraja pa se vraća
Najkraći put?	DA (bez težina)	NE
Vremenska složenost	O(V+E)	O(V+E)
Primeri primene	Najkraći put, širina grafa	Topsort, 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: Dijkstra, MST (Kruskal/Prim), topološko sortiranje.

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

Prikaži uputstvo

Uputstvo

• Koristi BFS jer graf nema težine.
• Održavaj niz dist[] za udaljenosti.
• Početni čvor ima udaljenost 0.
• Svaki put kada ubaciš čvor u red, postavi mu udaljenost.

Prikaži rešenje

// BFS – najkraće udaljenosti
queue q;
vector dist(n+1, -1);

dist[s] = 0;
q.push(s);

while(!q.empty()){
    int v = q.front(); q.pop();
    for(int u : graf[v]){
        if(dist[u] == -1){
            dist[u] = dist[v] + 1;
            q.push(u);
        }
    }
}

---

2. BFS — Provera povezanosti grafa

Tekst zadatka

Dat je neusmeren graf. Proveriti da li je graf povezan, odnosno da li se iz jednog početnog čvora može stići do svih ostalih čvorova.

Primer

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

Izlaz:
Graf NIJE povezan

Prikaži uputstvo

Uputstvo

• Pokreni BFS iz proizvoljnog čvora.
• Prebroj koliko je čvorova posećeno.
• Ako broj posećenih čvorova nije n, graf nije povezan.

Prikaži rešenje

// BFS – provera povezanosti
int cnt = 0;
queue q;
q.push(1);
posecen[1] = true;

while(!q.empty()){
    int v = q.front(); q.pop();
    cnt++;
    for(int u : graf[v]){
        if(!posecen[u]){
            posecen[u] = true;
            q.push(u);
        }
    }
}

if(cnt == n) cout << "Graf je povezan";
else cout << "Graf NIJE 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

Prikaži uputstvo

Uputstvo

• Pokreni DFS iz čvora s.
• Svaki put kada uđeš u čvor, uvećaj brojač.
• DFS će obići celu komponentu povezanosti.

Prikaži rešenje

// DFS – broj čvorova u komponenti
int cnt = 0;

void dfs(int v){
    posecen[v] = true;
    cnt++;
    for(int u : graf[v]){
        if(!posecen[u])
            dfs(u);
    }
}

---

4. DFS — Detekcija ciklusa u neusmerenom grafu

Tekst zadatka

Dat je neusmeren graf. Odrediti da li u grafu postoji ciklus koristeći DFS algoritam.

Primer

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

Izlaz:
Graf SADRŽI ciklus

Prikaži uputstvo

Uputstvo

• Koristi DFS sa parametrom roditelj.
• Ako naiđeš na posećen čvor koji nije roditelj – postoji ciklus.

Prikaži rešenje

// DFS – detekcija ciklusa
bool dfs(int v, int parent){
    posecen[v] = true;
    for(int u : graf[v]){
        if(!posecen[u]){
            if(dfs(u, v)) return true;
        }
        else if(u != parent){
            return true;
        }
    }
    return false;
}

Zadaci iz prakse (realni problemi) — BFS i DFS

1. 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 dvosmerni putevi 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).

Prikaži uputstvo

Uputstvo

• Graf je ne-težinski → koristi se BFS.
• Voditi niz dist[v] koji pamti minimalan broj koraka do čvora v.
• Početni čvor ima udaljenost 0.
• Čim se prvi put stigne do čvora T, pronađen je najkraći put.
• Vremenska složenost: O(V + E).

Prikaži rešenje

Rešenje (BFS)

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

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

int bfs(int S, int T) {
    queue q;
    q.push(S);
    distanca[S] = 0;

    while(!q.empty()) {
        int v = q.front(); q.pop();
        if(v == T) return distanca[v];

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

2. 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 (zone 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.

Prikaži uputstvo

Uputstvo

• Potrebno je proveriti povezanost grafa.
• Pokrenuti DFS iz čvora 1.
• Nakon DFS-a proveriti da li su svi čvorovi posećeni.
• Ako postoji barem jedan neposećen čvor → odgovor je NE.
• Vreme: O(V + E).

Prikaži rešenje

Rešenje (DFS)

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

vector graf[100];
bool posecen[100];

void dfs(int v) {
    posecen[v] = true;
    for(int sused : graf[v]) {
        if(!posecen[sused])
            dfs(sused);
    }
}

int main() {
    int N, M;
    cin >> N >> M;

    for(int i=0;i> a >> b;
        graf[a].push_back(b);
        graf[b].push_back(a);
    }

    dfs(1);

    for(int i=1;i<=N;i++) {
        if(!posecen[i]) {
            cout << "NE";
            return 0;
        }
    }
    cout << "DA";
    return 0;
}
  

Napomena

Ovaj zadatak modeluje realne probleme poput evakuacije, dostupnosti infrastrukture ili komunikacionih mreža.

Sledeća lekcija

Preporuka za nastavak:

Topološko sortiranje

Vraćanje na vodič za Grafove i stabla

← Mapa učenja — Grafovi i stabla