BFS și DFS în C++: parcurgerea unui graf

Ce înseamnă să parcurgi un graf

Pornim dintr-un vârf s și descoperim toate vârfurile la care putem ajunge folosind muchiile. Fiecare vârf trebuie prelucrat o singură dată, chiar dacă există mai multe căi către el. Tabloul viz reține dacă un vârf a fost deja descoperit. Fără această evidență, chiar muchia 1-2 ne-ar permite să revenim la nesfârșit între cele două capete.

Folosim grafuri neorientate simple și matricea de adiacență. Numerotarea este 1..n, cu 1 <= n <= 100. Citim n m, apoi m muchii distincte cu capete valide și diferite, apoi sursa s, tot în 1..n. Muchiile nu au costuri. O singură parcurgere vizitează numai componenta sursei, nu neapărat întregul graf.

BFS: întâi vecinii apropiați

BFS, parcurgerea în lățime, folosește o coadă. Primul vârf introdus este primul extras. Adăugăm sursa și o marcăm imediat. La extragerea lui x, examinăm vecinii în ordine crescătoare și îi adăugăm doar pe cei încă nemarcați. Marcarea se face la introducere, ca doi vecini diferiți să nu introducă același vârf de două ori.

Imagine indisponibilă: BFS pornește din 1, descoperă 2 și 3, apoi 4; vârful 5 rămâne nevizitat, iar coada activă se golește după procesarea lui 4.

În desen avem muchiile 1-2, 1-3, 2-4, 3-4 și vârful izolat 5. Coada activă pornește cu 1, devine 2 3, apoi 3 4, apoi 4, apoi goală. Când procesăm 3, nu mai adăugăm 4: acesta a fost deja marcat de la 2. Ordinea afișată este 1 2 3 4.

Indicii cozii au altă convenție decât numerele vârfurilor: elementele active sunt în intervalul [st, dr). q[st++] extrage, iar q[dr++] = y introduce. Fiecare vârf intră cel mult o dată, deci coada are cel mult n elemente. La final afișăm tot istoricul introducerilor, păstrat în q[0..dr-1].

Varianta clasică, cu tablouri

#include <iostream>

int main() {
    int n, m;
    std::cin >> n >> m;
    int a[101][101] = {};
    for (int i = 0; i < m; ++i) {
        int x, y;
        std::cin >> x >> y;
        a[x][y] = a[y][x] = 1;
    }
    int s;
    std::cin >> s;
    int viz[101] = {};
    int q[101] = {};
    int st = 0, dr = 0;
    q[dr++] = s;
    viz[s] = 1;
    while (st < dr) {
        int x = q[st++];
        for (int y = 1; y <= n; ++y) {
            if (a[x][y] && !viz[y]) {
                viz[y] = 1;
                q[dr++] = y;
            }
        }
    }
    for (int i = 0; i < dr; ++i) {
        if (i > 0) std::cout << ' ';
        std::cout << q[i];
    }
    std::cout << '\n';
}

Varianta echivalentă cu std::vector

#include <iostream>
#include <vector>

int main() {
    int n, m;
    std::cin >> n >> m;
    std::vector<std::vector<int>> a(n + 1, std::vector<int>(n + 1, 0));
    for (int i = 0; i < m; ++i) {
        int x, y;
        std::cin >> x >> y;
        a[x][y] = a[y][x] = 1;
    }
    int s;
    std::cin >> s;
    std::vector<int> viz(n + 1, 0);
    std::vector<int> q(n + 1, 0);
    int st = 0, dr = 0;
    q[dr++] = s;
    viz[s] = 1;
    while (st < dr) {
        int x = q[st++];
        for (int y = 1; y <= n; ++y) {
            if (a[x][y] && !viz[y]) {
                viz[y] = 1;
                q[dr++] = y;
            }
        }
    }
    for (int i = 0; i < dr; ++i) {
        if (i > 0) std::cout << ' ';
        std::cout << q[i];
    }
    std::cout << '\n';
}

DFS: mergem în adâncime

Următoarele două programe folosesc DFS, parcurgerea în adâncime. Apelul dfs(x) marchează și salvează imediat vârful, apoi intră recursiv în primul vecin nevizitat. După încheierea acelui apel, continuă examinarea celorlalți vecini. Înțelegerea stivei apelurilor te ajută să urmărești revenirile.

Pentru același exemplu și sursa 1, DFS afișează 1 2 4 3. Din 1 merge în 2, apoi în 4, apoi în 3; abia apoi revine. Rezultatul diferă de BFS, dar ambele vizitează exact aceleași patru vârfuri. Ordinea unei parcurgeri depinde de ordinea examinării vecinilor. Aici ea este stabilită explicit de bucla 1..n.

În variantele clasice, matricea are capacitatea 101 x 101, iar tablourile auxiliare au 101 poziții. Variantele cu std::vector alocă după n+1, păstrând aceiași indici și același algoritm. Matricea din DFS este transmisă prin referință constantă în varianta dinamică; nu copiem graful la fiecare apel. Contorul k se transmite prin referință în ambele versiuni.

Varianta clasică, cu tablouri

#include <iostream>

void dfs(int x, int n, const int a[][101], int viz[], int ordine[], int& k) {
    viz[x] = 1;
    ordine[k++] = x;
    for (int y = 1; y <= n; ++y)
        if (a[x][y] && !viz[y]) dfs(y, n, a, viz, ordine, k);
}

int main() {
    int n, m;
    std::cin >> n >> m;
    int a[101][101] = {};
    for (int i = 0; i < m; ++i) {
        int x, y;
        std::cin >> x >> y;
        a[x][y] = a[y][x] = 1;
    }
    int s;
    std::cin >> s;
    int viz[101] = {};
    int q[101] = {};
    int k = 0;
    dfs(s, n, a, viz, q, k);
    for (int i = 0; i < k; ++i) {
        if (i > 0) std::cout << ' ';
        std::cout << q[i];
    }
    std::cout << '\n';
}

Varianta echivalentă cu std::vector

#include <iostream>
#include <vector>

void dfs(int x, int n, const std::vector<std::vector<int>>& a, std::vector<int>& viz, std::vector<int>& ordine, int& k) {
    viz[x] = 1;
    ordine[k++] = x;
    for (int y = 1; y <= n; ++y)
        if (a[x][y] && !viz[y]) dfs(y, n, a, viz, ordine, k);
}

int main() {
    int n, m;
    std::cin >> n >> m;
    std::vector<std::vector<int>> a(n + 1, std::vector<int>(n + 1, 0));
    for (int i = 0; i < m; ++i) {
        int x, y;
        std::cin >> x >> y;
        a[x][y] = a[y][x] = 1;
    }
    int s;
    std::cin >> s;
    std::vector<int> viz(n + 1, 0);
    std::vector<int> q(n + 1, 0);
    int k = 0;
    dfs(s, n, a, viz, q, k);
    for (int i = 0; i < k; ++i) {
        if (i > 0) std::cout << ' ';
        std::cout << q[i];
    }
    std::cout << '\n';
}

Cost și limite

Cu matrice, fiecare vârf procesat examinează n poziții. Timpul în cazul cel mai defavorabil este O(n²), iar matricea necesită O(n²) memorie. Coada, vizitarea și ordinea ocupă O(n) spațiu auxiliar. DFS adaugă o stivă de apeluri de adâncime cel mult n. Limita mică din lecție este intenționată; pentru grafuri foarte mari, un DFS recursiv poate epuiza stiva.

Cu liste de vecini, BFS și DFS pot avea timp O(n+m). Nu aplicăm această estimare programelor cu matrice. Nici BFS, nici DFS nu trebuie să presupună că graful este conex. Dacă sursa este 5 în exemplu, ambele afișează doar 5.

Exersează

1. Simulează BFS și DFS din 1 pe lanțul 1-2-3-4.
2. Ce se întâmplă dacă marcăm un vârf numai după ce îi explorăm vecinii în DFS?
3. De ce 4 nu apare de două ori în coada exemplului?

Răspunsuri: ambele afișează 1 2 3 4; putem intra într-o recursie repetată printr-un vârf încă nemarcat; marcarea lui 4 la prima introducere blochează a doua introducere. Pentru a acoperi un graf neconex, continuă cu componentele conexe.