1. Ideea din spatele BFS
Arunci o piatra intr-un lac. Valurile se extind uniform in toate directiile simultan. BFS functioneaza la fel: pleaca din nodul sursa si "valurile" sale ating toate nodurile de la distanta 1, apoi 2 etc. Niciun val nu sare peste un nivel.
BFS — coada → nivel cu nivel → gaseste drumul MINIM (ca numar de muchii) in grafuri neponderate.
DFS — stiva/recursivitate → adanc pe o ramura intai → nu garanteaza drum minim, dar mai simplu de implementat recursiv.
2. Algoritmul BFS — pasii si urmarirea
INITIALIZEAZA coada cu s
MARCHEAZA s ca vizitat
CAT TIMP coada nu e goala:
nod ← SCOATE primul element din coada
PENTRU FIECARE vecin al lui nod:
DACA vecin NU e vizitat:
MARCHEAZA vecin ca vizitat
ADAUGA vecin in coada
Graful are 6 noduri cu muchiile: 1-2, 1-3, 2-4, 2-5, 3-6. Pornind din nodul 1:
Initial: coada=[1], vizitat=[1] Pas 1: extras=1, adaugati=[2, 3], coada=[2, 3], vizitat=[1, 2, 3] Pas 2: extras=2, adaugati=[4, 5], coada=[3, 4, 5], vizitat=[1, 2, 3, 4, 5] Pas 3: extras=3, adaugati=[6], coada=[4, 5, 6], vizitat=[1, 2, 3, 4, 5, 6] Pas 4: extras=4, adaugati=[], coada=[5, 6], vizitat=[1, 2, 3, 4, 5, 6] Pas 5: extras=5, adaugati=[], coada=[6], vizitat=[1, 2, 3, 4, 5, 6] Pas 6: extras=6, adaugati=[], coada=[], vizitat=[1, 2, 3, 4, 5, 6]
Ordinea de vizitare: 1, 2, 3, 4, 5, 6 — exact nivel cu nivel.
Nivel 0: 1 Nivel 1: 2, 3 Nivel 2: 4, 5, 6
3. Implementare BFS in Python
Graful este reprezentat ca dictionar de liste de adiacenta. Coada este un deque din modulul collections.
# BFS simplu - ordine de vizitare from collections import deque def bfs(graf, start): vizitat = set() coada = deque([start]) vizitat.add(start) ordine = [] while coada: nod = coada.popleft() ordine.append(nod) for vecin in sorted(graf[nod]): if vecin not in vizitat: vizitat.add(vecin) coada.append(vecin) return ordine # Graful din exemplu (noduri 1-6) G = { 1: [2, 3], 2: [1, 4, 5], 3: [1, 6], 4: [2], 5: [2], 6: [3] } rezultat = bfs(G, 1) print("Ordinea BFS pornind din nodul 1:", rezultat)
Ordinea BFS pornind din nodul 1: [1, 2, 3, 4, 5, 6]
Marcam nodul vizitat cand il adaugam in coada (nu cand il scoatem). Daca am marca la scoatere, acelasi nod ar putea fi adaugat de mai multe ori de catre vecini diferiti, ducand la parcurgere gresita sau bucla infinita in grafuri cu cicluri.
4. Distante minime si reconstructia drumului
dist[v] != -1 inseamna vizitat.
# BFS - distante minime de la sursa from collections import deque def bfs_distante(graf, start): dist = {start: 0} coada = deque([start]) while coada: nod = coada.popleft() for vecin in sorted(graf[nod]): if vecin not in dist: dist[vecin] = dist[nod] + 1 coada.append(vecin) return dist G = { 1: [2, 3], 2: [1, 4, 5], 3: [1, 6], 4: [2], 5: [2], 6: [3] } distante = bfs_distante(G, 1) for nod in sorted(distante): print(f"dist[{nod}] = {distante[nod]}")
dist[1] = 0 dist[2] = 1 dist[3] = 1 dist[4] = 2 dist[5] = 2 dist[6] = 2
Adaugam vectorul de parinti pentru a reconstitui drumul efectiv:
# BFS - drum minim cu reconstructie from collections import deque def drum_minim(graf, start, stop): dist = {start: 0} parinte = {start: None} coada = deque([start]) while coada: nod = coada.popleft() if nod == stop: break for vecin in sorted(graf[nod]): if vecin not in dist: dist[vecin] = dist[nod] + 1 parinte[vecin] = nod coada.append(vecin) # Reconstruire drum: mers inapoi prin parinti drum = [] crt = stop while crt is not None: drum.append(crt) crt = parinte[crt] drum.reverse() return drum, dist.get(stop, -1) G = { 1: [2, 3], 2: [1, 4, 5], 3: [1, 6], 4: [2], 5: [2], 6: [3] } drum, lungime = drum_minim(G, 1, 4) print("Drum minim de la 1 la 4:", " -> ".join(map(str, drum))) print("Lungime drum:", lungime)
Drum minim de la 1 la 4: 1 -> 2 -> 4 Lungime drum: 2
5. Complexitate, reprezentari si proprietati
• Fiecare nod este introdus si scos din coada exact o singura data → V operatii.
• Fiecare muchie este examinata de exacta doua ori (o data din fiecare capat) → 2E operatii.
• Total: O(V + E).
Complexitate spatiu: O(V)
Coada contine cel mult V noduri simultan. Vectorii de distante si parinti au V intrari.
Lista de adiacenta — spatiu O(V + E), traversare vecini O(grad(nod)). Recomandata pentru grafuri rare (putine muchii).
Matrice de adiacenta — spatiu O(V²), verificare muchie O(1), traversare vecini O(V). Practica doar la V mic sau grafuri dense.
In subiecte BAC cls. XI, grafurile au V ≤ 10..20 → ambele sunt acceptabile, dar lista de adiacenta este standard la olimpiada.
- Gaseste drumul minim ca numar de muchii in grafuri neponderate.
- Intr-un graf ponderat (muchii cu costuri diferite), BFS NU garanteaza drum minim — se foloseste Dijkstra.
- BFS poate determina daca un graf este conex: daca dintr-un nod oarecare BFS viziteaza toate V nodurile, graful este conex.
- BFS poate determina numarul de componente conexe: se repeta BFS din fiecare nod nevizitat.
6. BFS in C++ EXCLUSIV INTENSIV
In C++ folosim #include <queue> pentru coada STL si vector<vector<int>> pentru lista de adiacenta. Conventie olimpiada: indexare de la 1, distanta initiala -1 inseamna nevizitat.
Exemplu 1: Calcul distante minime
#include <iostream> #include <vector> #include <queue> using namespace std; int main() { int n = 6; vector<vector<int>> adj(n + 1); adj[1] = {2, 3}; adj[2] = {1, 4, 5}; adj[3] = {1, 6}; adj[4] = {2}; adj[5] = {2}; adj[6] = {3}; vector<int> dist(n + 1, -1); queue<int> q; dist[1] = 0; q.push(1); while (!q.empty()) { int nod = q.front(); q.pop(); for (int vecin : adj[nod]) { if (dist[vecin] == -1) { dist[vecin] = dist[nod] + 1; q.push(vecin); } } } for (int i = 1; i <= n; i++) cout << "dist[" << i << "] = " << dist[i] << "\n"; return 0; }
dist[1] = 0 dist[2] = 1 dist[3] = 1 dist[4] = 2 dist[5] = 2 dist[6] = 2
Exemplu 2: Reconstructie drum minim
#include <iostream> #include <vector> #include <queue> #include <algorithm> using namespace std; int main() { int n = 6; vector<vector<int>> adj(n + 1); adj[1] = {2, 3}; adj[2] = {1, 4, 5}; adj[3] = {1, 6}; adj[4] = {2}; adj[5] = {2}; adj[6] = {3}; vector<int> dist(n + 1, -1); vector<int> parinte(n + 1, -1); queue<int> q; dist[1] = 0; q.push(1); while (!q.empty()) { int nod = q.front(); q.pop(); for (int vecin : adj[nod]) { if (dist[vecin] == -1) { dist[vecin] = dist[nod] + 1; parinte[vecin] = nod; q.push(vecin); } } } int dest = 4; vector<int> drum; for (int crt = dest; crt != -1; crt = parinte[crt]) drum.push_back(crt); reverse(drum.begin(), drum.end()); cout << "Drum minim de la 1 la 4: "; for (int i = 0; i < (int)drum.size(); i++) { if (i) cout << " -> "; cout << drum[i]; } cout << "\nLungime drum: " << dist[dest] << "\n"; return 0; }
Drum minim de la 1 la 4: 1 -> 2 -> 4 Lungime drum: 2
Observatie: dist[v] == -1 joaca rolul de "nevizitat". Este idiomul standard C++ pentru BFS la olimpiada si BAC.