Parcurgerea în adâncime

Parcurgerea în adâncime (DF) urmează un vecin nevizitat cât poate de departe, apoi revine. Poate fi implementată recursiv sau cu o stivă. În graful cu muchiile 1–2, 1–3, 2–4, dacă vecinii sunt examinați crescător, pornind din 1 se vizitează 1, 2, 4, apoi 3.

Parcurgerea în adâncime (DF) pornește dintr-un vârf-sursă, urmează un vecin nevizitat cât poate de departe, apoi revine și continuă cu următorul vecin nevizitat. Poate fi scrisă recursiv, caz în care stiva apelurilor memorează drumul curent, sau iterativ, cu o stivă proprie. Vârfurile se marchează ca vizitate pentru ca, într-un graf cu cicluri, apelurile să nu se repete la nesfârșit. O parcurgere acoperă numai componenta conexă a sursei. Pe matricea de adiacență costă $O(n^2)$, iar cu liste de adiacență $O(n+m)$. Adâncimea recursiei poate ajunge la $n$, de exemplu pe un lanț.

Exemplul 1 — varianta recursivă. Matricea de adiacență permite examinarea vecinilor în ordine crescătoare. Pentru muchiile $[1,2]$, $[1,3]$ și $[2,4]$, parcurgerea din 1 afișează 1 2 4 3:

#include <iostream>
using namespace std;
int a[5][5] = {}, vazut[5] = {}, n = 4;
void dfs(int u) {
    vazut[u] = 1;
    cout << u << " ";
    for (int v = 1; v <= n; ++v)
        if (a[u][v] && !vazut[v]) dfs(v);
}
int main() {
    a[1][2] = a[2][1] = a[1][3] = a[3][1] = a[2][4] = a[4][2] = 1;
    dfs(1);
}

Din 1 se merge la 2, apoi, din 2, la 4. Vârful 4 nu mai are vecini nevizitați, apelul se încheie, iar parcurgerea revine în 1, de unde urmează vecinul 3. De aceea 3 este vizitat ultimul, deși este vecin direct al lui 1.

Exemplul 2 — varianta iterativă. Se pune sursa în stivă; cât timp stiva nu este goală, se scoate vârful, se ignoră dacă a fost deja vizitat, altfel se marchează, se afișează și se pun în stivă vecinii nevizitați, în ordine descrescătoare, pentru ca cel mai mic vecin să fie scos primul:

#include <iostream>
using namespace std;
int main() {
    int n = 4, a[5][5] = {}, vazut[5] = {}, st[20], vf = 0;
    a[1][2] = a[2][1] = a[1][3] = a[3][1] = a[2][4] = a[4][2] = 1;
    st[++vf] = 1;
    while (vf > 0) {
        int u = st[vf--];
        if (vazut[u]) continue;
        vazut[u] = 1;
        cout << u << " ";
        for (int v = n; v >= 1; --v)
            if (a[u][v] && !vazut[v]) st[++vf] = v;
    }
}

Se afișează tot 1 2 4 3. Stiva evoluează $[1]\to [3,2]\to [3,4]\to [3]$, apoi se golește. Marcarea la extragere cere testul if (vazut[u]) continue, pentru că un vârf poate fi pus în stivă de mai multe ori; marcarea la inserare evită repetările.

Exemplul 4 — numărarea componentelor conexe. Un graf are 6 vârfuri și muchiile $[1,2]$, $[3,4]$, $[4,5]$; vârful 6 este izolat. Pentru că un apel acoperă doar componenta sursei, se pornește câte o parcurgere din fiecare vârf nevizitat:

int comp = 0;
for (int i = 1; i <= n; ++i)
    if (!vazut[i]) {
        dfs(i);
        ++comp;
    }
cout << comp;

Apelul dfs(1) vizitează 1 și 2, dfs(3) vizitează 3, 4 și 5, iar dfs(6) vizitează doar 6; se afișează 3. Fiecare vârf este vizitat o singură dată, așa că ciclul adaugă doar $O(n)$ pași peste costul parcurgerilor.

Vectorul de vizitare. Ambele parcurgeri, în adâncime și în lățime, folosesc un vector viz, cu viz[x] = 1 după ce nodul $x$ a fost vizitat, ca să nu treci de două ori prin același nod; fără el, un ciclu ar face parcurgerea să nu se mai termine. Ordinea în care se cercetează vecinii schimbă ordinea vizitării: cu matricea de adiacență, vecinii se cercetează în ordinea crescătoare a numerelor, iar exercițiile de examen presupun, de obicei, această ordine.

DFS pe scurt. Vizitezi nodul de start, apoi treci la primul lui vecin nevizitat, apoi la primul vecin nevizitat al acestuia și așa mai departe. Când nodul curent nu mai are vecini nevizitați, revii la nodul din care ai venit și continui cu următorul lui vecin. Revenirea se face natural cu o funcție recursivă: fiecare apel dfs(x) rămâne „deschis” până când toți vecinii lui $x$ sunt terminați, exact ca într-o stivă.

BFS pe scurt. Pui nodul de start într-o coadă. Cât timp coada nu e goală, scoți primul nod și adaugi la finalul cozii toți vecinii lui nevizitați, marcându-i imediat. Nodurile intră în coadă pe straturi: întâi cele aflate la distanța 1 de start, apoi cele la distanța 2. De aceea BFS calculează distanța minimă d[y] = d[x] + 1, iar un vector de tați t[y] = x reține drumul. Lecția „Parcurgerea în lățime” o detaliază.

Graful folosit în exemple are 7 noduri și muchiile [1, 2], [1, 4], [2, 5], [3, 4], [3, 6], [5, 6], [6, 7]. Datele de intrare sunt 7 7, urmat de aceste perechi și de nodul de start.

Exemple suplimentare

Exemplul 3 — în formatul examenului. Graful are 6 vârfuri și muchiile $[1,2]$, $[1,3]$, $[2,4]$, $[3,4]$, $[4,5]$, iar vârful 6 este izolat. Parcurgerea în adâncime din 1, cu vecinii examinați în ordine crescătoare, vizitează vârfurile în ordinea:

• a) 1 2 4 3 5
• b) 1 2 3 4 5
• c) 1 3 4 5 2
• d) 1 2 4 5 3

Răspunsul corect este a). Din 1 se merge la 2, din 2 la 4. Din 4 vecinii sunt 2 (vizitat), 3 și 5; se examinează întâi 3, care nu are vecini nevizitați, apoi 5. Varianta b) este parcurgerea în lățime. Varianta c) ar rezulta dacă vecinii s-ar examina în ordine descrescătoare. Varianta d) ar vizita 5 înaintea lui 3, adică ar examina vecinii lui 4 în ordine descrescătoare. Vârful 6 nu apare în niciun răspuns, deoarece nu este accesibil din 1.

Exemple rezolvate

Exemplul 1: DFS din nodul 1.

1. Din 1, primul vecin nevizitat este 2; din 2, nodul 5; din 5, nodul 6; din 6, nodul 3; din 3, nodul 4.
2. Nodul 4 nu mai are vecini nevizitați (1 și 3 sunt vizitați), deci revii la 3, apoi la 6, care mai are vecinul 7.
3. Ordinea: 1, 2, 5, 6, 3, 4, 7.

#include <iostream>
using namespace std;

int a[101][101], viz[101], n, m;

void dfs(int x) {
    viz[x] = 1;
    cout << x << " ";
    for (int y = 1; y <= n; y++)
        if (a[x][y] == 1 && viz[y] == 0)
            dfs(y);
}

int main() {
    cin >> n >> m;
    for (int k = 1; k <= m; k++) {
        int x, y;
        cin >> x >> y;
        a[x][y] = a[y][x] = 1;
    }
    int start;
    cin >> start;
    dfs(start);
    cout << "\n";
    return 0;
}

Pentru graful de mai sus și nodul de start 1 (ultimul număr din datele de intrare), programul afișează:

1 2 5 6 3 4 7

Exemplul 2: nivel de examen, DFS din alt nod. Care este ordinea DFS pentru același graf, pornind din nodul 3, cu vecinii cercetați în ordine crescătoare?

1. Din 3, primul vecin nevizitat este 4; din 4, nodul 1; din 1, nodul 2; din 2, nodul 5; din 5, nodul 6.
2. Din 6, vecinii 3 și 5 sunt vizitați, rămâne 7.
3. Ordinea: 3, 4, 1, 2, 5, 6, 7. Programul de la exemplul 1, cu nodul de start 3, afișează exact această ordine.

Unde apare la examen

La Bacalaureatul la informatică, matematică-informatică, programa de examen cuprinde la grafuri terminologia, proprietățile (conex, componentă conexă, tare conexitate) și metodele de reprezentare; parcurgerile nu sunt numite separat, dar sunt modul obișnuit de a verifica conexitatea și de a afla componentele conexe (anexa 2 la OMECTS 4800/2010).

Pe programa școlară veche, „Parcurgerea grafurilor. Aplicații” este la clasa a XI-a (OMECI 5099/2009); programa nouă de clasa a XI-a, aplicată din 2028–2029, numește explicit algoritmii BFS și DFS (OMEC 4370/2026).

Greșeli frecvente

• Greșit: DF vizitează întâi toate vârfurile de la aceeași distanță.
  Corect: aceasta este ideea BF; în DFS, după primul vecin nevizitat continui imediat din el.
• Greșit: marcarea vârfului poate fi omisă într-un graf cu cicluri.
  Corect: fără marcaj, apelurile se pot repeta.
• Greșit: un singur apel DF acoperă orice graf.
  Corect: acoperă doar componenta sursei; pentru tot graful, pornești câte o parcurgere din fiecare nod nevizitat.
• Greșit: ordinea vecinilor nu contează la urmărirea unei parcurgeri.
  Corect: ordinea DFS și BFS depinde de ordinea în care cercetezi vecinii; la exercițiile de urmărire, folosește ordinea crescătoare, dacă enunțul nu spune altceva.
• Greșit: DFS dă distanțe minime.
  Corect: DFS nu dă distanțe minime: în exemplul 1 ajunge la nodul 4 după 5 muchii, deși 4 este vecin cu 1.

Înainte și după

Întrebări frecvente