Modul 05 — Parcurgeri: BFS & DFS + conexitate

BFS — parcurgerea în lățime (coada)

Din nodul 1, vestea se propagă în valuri. Auriu = nodul procesat acum, albastru = în coadă (a aflat, așteaptă să dea mai departe), verde = vizitat complet.

coada

ordinea

apasă Pas — nodul 1 intră în coadă 👆

1coada = [start]; viz[start] = 1;

2cat timp coada nu e goala:

3 u = scoate PRIMUL din coada // FIFO!

4 pentru fiecare vecin v al lui u:

5 daca viz[v] == 0:

6 viz[v] = 1; adauga v la SFARSITUL cozii

De ce „în lățime"? Coada FIFO garantează că TOATE nodurile la distanța 1 sunt procesate înaintea celor la distanța 2, ș.a.m.d. Bonus uriaș: BFS găsește automat drumul cu numărul MINIM de muchii — de-asta centrul de urgențe din programă trimite echipele cu BFS.

DFS — parcurgerea în adâncime (stiva)

Același graf, celălalt temperament: exploratorul intră pe primul tunel și nu se întoarce decât forțat. Stiva de apeluri = firul Ariadnei.

stiva

ordinea

apasă Pas — DFS(1) intră pe stivă 👆

1void DFS(int u) {

2 viz[u] = 1; cout << u; // vizitez la INTRARE

3 for (fiecare vecin v al lui u)

4 if (!viz[v]) DFS(v); // mă scufund

5} // bucla gata → REVIN (stiva mă întoarce)

Compară ordinile! BFS: 1, 2, 3, 4, 5, 6, 7 (valuri concentrice). DFS: 1, 2, 4, 6, 5, 3, 7 (tunel până la capăt, apoi înapoi). Aceleași noduri, aceleași muchii — strategia schimbă tot. Și recunoști schema DFS? E Backtracking fără condiții de validare!

Conexitate și componente conexe

Rețeaua de comunicații din programă: e conex graful? Dacă nu — câte „insule" are? Rețeta: parcurgi, și dacă au rămas noduri nevizitate, pornești altă parcurgere.

8 dispozitive, 6 legături — apasă și privește insulele colorându-se 👆

1int nrc = 0;

2for (int i = 1; i <= n; i++)

3 if (!viz[i]) {

4 nrc++; // componentă nouă!

5 DFS(i); // o „inundă" pe toată

6 }

7// graf conex ⇔ nrc == 1

Nodul critic (din programă): dacă ștergerea unui dispozitiv RUPE rețeaua în mai multe componente, acel nod e critic. Testul: șterge-l (subgraf — M04!), renumără componentele. Dacă nrc a crescut — legătura dintre dispozitive depindea de el.

BFS vs DFS — pe care îl chemi?

Amândoi vizitează tot, în O(n + m). Diferă CE îți oferă pe drum.

🌊 Chemi BFS când…

…vrei DISTANȚE minime în muchii (echipele de urgență spre toate localitățile), niveluri/valuri, sau „cel mai apropiat X". Structura: coadă FIFO, iterativ.

⛏ Chemi DFS când…

…vrei să găsești UN traseu (tunelul minei din programă), componente conexe, sau explorezi exhaustiv (rudă cu Backtracking). Structura: stiva de apeluri, recursiv — 3 rânduri de cod.

La orientate ambele merg identic — doar că „vecin" înseamnă SUCCESOR. Din parcurgeri se va naște matricea drumurilor și tare-conexitatea (Modulul 06).

Fișa de sinteză

Parcurgerile, condensate.

BFS: coadă FIFO — scot din față, adaug la coadă; vizitez în valuri; găsește drumul cu minim de muchii.

DFS: recursiv — vizitez la intrare, mă scufund la primul vecin nevizitat; stiva mă întoarce singură.

Ambele: O(n + m) cu liste de adiacență; fiecare nod o dată, fiecare muchie de două ori.

Conex ⇔ o singură parcurgere atinge tot; componentele = de câte ori pornești o parcurgere nouă.

Nod critic: ștergerea lui crește numărul componentelor — testezi cu subgraf + renumărare.

Rudenii: BFS ↔ coada (IX·M08) · DFS ↔ recursivitatea (X·M10) și Backtracking (XI·M01).

Exersează: pe pbinfo.ro — parcurgeri BFS/DFS, componente conexe, verificarea conexității; scrie AMBELE parcurgeri pe același graf și compară ordinile, ca în simulatoare.

Unda și scufundarea