Parcurgerea în lățime

Parcurgerea în lățime, BF, vizitează mai întâi vecinii sursei, apoi vecinii lor încă nevizitați. Folosește o coadă. În graful cu muchiile 1–2, 1–3, 2–4, pornind din 1 și examinând vecinii în ordine crescătoare, ordinea este 1, 2, 3, 4. Distanțele în număr de muchii sunt 0, 1, 1, 2.

Parcurgerea în lățime (BF) pornește dintr-un vârf-sursă, vizitează toți vecinii lui, apoi vecinii încă nevizitați ai acestora, nivel cu nivel. Folosește o coadă: vârfurile intră în ordinea descoperirii și sunt procesate în aceeași ordine. Un vârf se marchează atunci când intră în coadă, nu când iese, ca să nu fie adăugat de două ori. Din acest motiv, în orice moment vârfurile din coadă sunt la distanța $d$ sau $d+1$ de sursă, iar primul moment în care un vârf este descoperit dă distanța minimă, în număr de muchii, de la sursă la el. Vârfurile inaccesibile rămân nemarcate și au distanța $-1$ (sau infinit). Pe matricea de adiacență, timpul este $O(n^2)$; cu liste de adiacență, $O(n+m)$.

Exemplul 1 — distanța pe matrice. Coada este un tablou cu indicii prim și ultim. Graful are muchiile 1–2, 1–3, 2–4:

#include <iostream>
using namespace std;
int main() {
    int n = 4, a[5][5] = {}, c[5], dist[5], prim = 1, ultim = 0;
    a[1][2] = a[2][1] = a[1][3] = a[3][1] = a[2][4] = a[4][2] = 1;
    for (int i = 1; i <= n; ++i) dist[i] = -1;
    c[++ultim] = 1;
    dist[1] = 0;
    while (prim <= ultim) {
        int u = c[prim++];
        for (int v = 1; v <= n; ++v)
            if (a[u][v] && dist[v] == -1) {
                dist[v] = dist[u] + 1;
                c[++ultim] = v;
            }
    }
    cout << dist[4];
}

Se afișează 2. Pornind din 1, coada trece prin $[1]$, apoi $[2,3]$, apoi $[3,4]$. Vârful 4 este descoperit din 2 la distanța 2, deci cel mai scurt lanț de la 1 la 4 are două muchii.

Exemplul 2 — ordinea vizitării, distanțele și lanțul minim. Graful are 6 vârfuri și muchiile $[1,2]$, $[1,3]$, $[2,4]$, $[3,4]$, $[4,5]$; vârful 6 este izolat. Pe lângă distanțe, se memorează pentru fiecare vârf descoperit predecesorul lui, tata, ceea ce permite reconstituirea lanțului minim:

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main() {
    int n = 6, e[5][2] = {{1, 2}, {1, 3}, {2, 4}, {3, 4}, {4, 5}};
    vector<int> a[7];
    for (auto& m : e) { a[m[0]].push_back(m[1]); a[m[1]].push_back(m[0]); }
    int dist[7], tata[7] = {};
    for (int i = 1; i <= n; ++i) dist[i] = -1;
    queue<int> q;
    q.push(1);
    dist[1] = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        cout << u << " ";
        for (int v : a[u])
            if (dist[v] == -1) { dist[v] = dist[u] + 1; tata[v] = u; q.push(v); }
    }
    cout << "\n";
    for (int i = 1; i <= n; ++i) cout << dist[i] << " ";
    cout << "\n";
    for (int v = 5; v; v = tata[v]) cout << v << " ";
}

Se afișează 1 2 3 4 5, apoi 0 1 1 2 3 -1, apoi 5 4 2 1. Vârful 6 nu este vizitat și are distanța $-1$. Vârful 4 are doi posibili predecesori, 2 și 3, la aceeași distanță; se păstrează 2, pentru că a fost scos primul din coadă, iar lanțul minim de la 1 la 5 este 1–2–4–5, citit de la 5 spre 1. Dacă lista vecinilor lui 1 ar fi fost {3, 2}, ordinea vizitării și lanțul ar fi fost altele, dar distanțele ar fi rămas aceleași.

Exemplul 3 — în formatul examenului. Pentru graful din al doilea exemplu, parcurgerea în lățime din vârful 1, cu vecinii examinați în ordine crescătoare, vizitează vârfurile în ordinea:

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

Răspunsul corect este a). Din 1 se descoperă 2 și 3, din 2 se descoperă 4, din 3 nu se descoperă nimic nou, iar din 4 se descoperă 5. Varianta b) este ordinea unei parcurgeri în adâncime. Varianta c) ar rezulta dacă vecinii s-ar examina descrescător. Varianta d) include vârful 6, care nu este accesibil din 1.

Cazuri-limită și limitări. Dacă sursa este un vârf izolat, coada conține doar sursa; după ce este scoasă nu se descoperă nimic, iar toate celelalte distanțe rămân $-1$. Distanța minimă în număr de muchii este corectă numai pentru grafuri fără costuri pe muchii: dacă muchiile ar avea costuri diferite, parcurgerea în lățime nu ar găsi lanțul de cost minim. Cu liste de adiacență, fiecare vârf intră în coadă cel mult o dată, iar fiecare muchie este examinată de două ori, câte o dată din fiecare capăt; de aici timpul $O(n+m)$.

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. Ca la parcurgerea în adâncime, un vector de vizitare împiedică trecerea de două ori prin același nod, iar ordinea vizitării depinde de ordinea în care sunt cercetați vecinii; cu matricea de adiacență, vecinii se cercetează în ordinea crescătoare.

Exemple rezolvate

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

Exemplul 1: BFS din nodul 1, cu distanțe.

1. Coada: 1. Scoți 1 și adaugi 2 și 4 (distanța 1).
2. Scoți 2 și adaugi 5 (distanța 2). Scoți 4 și adaugi 3 (distanța 2).
3. Scoți 5 și adaugi 6 (distanța 3). Scoți 3: vecinul 6 e deja vizitat. Scoți 6 și adaugi 7 (distanța 4).
4. Ordinea: 1, 2, 4, 5, 3, 6, 7.

#include <iostream>
using namespace std;

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

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 prim = 1, ultim = 1;          // coada c[prim..ultim]
    c[1] = 1;
    viz[1] = 1;
    while (prim <= ultim) {
        int x = c[prim++];            // scot primul nod din coada
        for (int y = 1; y <= n; y++)
            if (a[x][y] == 1 && viz[y] == 0) {
                viz[y] = 1;
                d[y] = d[x] + 1;
                c[++ultim] = y;       // adaug y la finalul cozii
            }
    }
    for (int i = 1; i <= ultim; i++)
        cout << c[i] << " ";
    cout << "\n";
    for (int x = 1; x <= n; x++)
        cout << d[x] << " ";
    cout << "\n";
    return 0;
}

Programul afișează ordinea vizitării, apoi distanțele nodurilor 1, 2, …, 7 față de nodul 1:

1 2 4 5 3 6 7
0 1 2 1 2 3 4

Exemplul 2: un drum minim. Afișează un drum cu cel mai mic număr de muchii de la nodul 1 la nodul 7.

1. În BFS reții, pentru fiecare nod y, nodul x din care a fost adăugat în coadă: t[y] = x.
2. Pornești din 7 și urci prin t până la 1: 7, 6, 5, 2, 1. Afișat de la start, drumul este 1, 2, 5, 6, 7, cu 4 muchii.
3. Mai există un drum de lungime 4 (1, 4, 3, 6, 7); BFS îl dă pe cel găsit primul, în ordinea cozii.

#include <iostream>
using namespace std;

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

void drum(int x) {                    // afiseaza drumul de la start la x
    if (t[x] != 0)
        drum(t[x]);
    cout << x << " ";
}

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 prim = 1, ultim = 1;
    c[1] = 1;
    viz[1] = 1;
    while (prim <= ultim) {
        int x = c[prim++];
        for (int y = 1; y <= n; y++)
            if (a[x][y] == 1 && viz[y] == 0) {
                viz[y] = 1;
                t[y] = x;
                c[++ultim] = y;
            }
    }
    drum(7);
    cout << "\n";
    return 0;
}

Programul afișează:

1 2 5 6 7

Funcția drum este recursivă ca să afișeze nodurile de la start spre final, deși vectorul t le dă de la final spre start.

Exemplul 3: nodurile aflate la o distanță dată. Câte noduri se află la distanța 2 de nodul 1? Din vectorul d de la exemplul 1: nodurile 3 și 5 au d = 2, deci răspunsul este 2. Nodul 6 nu este la distanța 2: vecinii lui sunt 3, 5 și 7, iar niciunul nu este vecin cu 1, deci distanța lui este 3.

Greșeli frecvente

• Greșit: nodul se marchează ca vizitat când iese din coadă.
  Corect: nodul se marchează când intră în coadă; altfel același nod poate intra în coadă de mai multe ori.
• Greșit: BF folosește o stivă.
  Corect: folosește o coadă.
• Greșit: distanța 1–4 în exemplu este 1.
  Corect: sunt două muchii, prin 2.
• Greșit: ordinea exactă a vârfurilor de pe același nivel este independentă de ordinea listelor de vecini.
  Corect: poate varia.

Înainte și după