Parcurgerea grafurilor

Parcurgerea în adâncime și în lățime: cum funcționează, ce ordine dau și la ce folosești fiecare.

Problema

A parcurge un graf înseamnă a vizita fiecare vârf accesibil dintr-un vârf de start, exact o dată.

Greu este „exact o dată". Într-un graf pot exista cicluri, iar dacă nu ții evidența vârfurilor deja vizitate, ajungi să te învârți în cerc la nesfârșit. De aceea orice parcurgere are un vector:

bool vizitat[101];

Unde stă față de programă. Programa de bacalaureat din 2022 nu numește parcurgerea în adâncime și parcurgerea în lățime ca algoritmi de învățat. Ideea de a vizita vârfurile pe rând, ținând minte pe care le-ai vizitat deja, îți folosește totuși la problemele despre conexitate și drumuri. La corectare, orice rezolvare corectă se punctează, indiferent de metodă.

Parcurgerea în adâncime

Ideea: de la vârful curent mergi la primul vecin nevizitat și continui de acolo cât de departe se poate. Când nu mai ai unde merge, te întorci și încerci alt vecin.

Se scrie recursiv, în câteva linii:

void df(int x) {
    vizitat[x] = true;
    cout << x << " ";
    for (int y = 1; y <= n; y++)
        if (a[x][y] == 1 && !vizitat[y])
            df(y);
}

Marchezi vârful la intrare, înainte de orice apel. Altfel același vârf ar fi vizitat de mai multe ori înainte să apuce să fie marcat.

Pentru graful cu muchiile [1,2], [1,3], [2,4], [3,4], pornind din 1: se vizitează 1, apoi 2, apoi 4, apoi 3. Parcurgerea coboară cât se poate de adânc înainte să revină.

Ordinea depinde de ordinea în care iei vecinii. Cu bucla for crescătoare, iei mereu cel mai mic vecin nevizitat. Așa rezultatul e previzibil, lucru important la Subiectul I.

Parcurgerea în lățime

Ideea: vizitezi întâi toți vecinii vârfului de start, apoi toți vecinii acestora, și așa mai departe, în cercuri concentrice.

Ai nevoie de o coadă, adică o listă de vârfuri în așteptare: scoți de la un capăt și adaugi la celălalt. Fără STL, care nu intră în programă, o ții într-un vector cu doi indici:

int coada[101], prim, ultim;

void bf(int start) {
    prim = ultim = 1;
    coada[1] = start;
    vizitat[start] = true;

    while (prim <= ultim) {
        int x = coada[prim++];
        cout << x << " ";
        for (int y = 1; y <= n; y++)
            if (a[x][y] == 1 && !vizitat[y]) {
                vizitat[y] = true;
                coada[++ultim] = y;
            }
    }
}

Pentru același graf, pornind din 1: se vizitează 1, apoi 2 și 3 (vecinii direcți), apoi 4.

Marchezi vârful când îl adaugi în coadă, nu când îl scoți. Altfel un vârf cu doi vecini deja în coadă ar fi adăugat de două ori.

Diferența, și de ce contează

Parcurgerea în lățime are o proprietate esențială: vârfurile sunt vizitate în ordinea distanței față de start. De aceea o folosești pentru „care este numărul minim de muchii de la x la y".

Distanța o calculezi cu un vector în plus:

int dist[101];
...
if (a[x][y] == 1 && !vizitat[y]) {
    vizitat[y] = true;
    dist[y] = dist[x] + 1;
    coada[++ultim] = y;
}

dist[y] este lungimea celui mai scurt lanț de la start la y. Vârfurile rămase cu vizitat fals nu sunt accesibile deloc.

Parcurgerea în adâncime nu îți dă asta. Ea găsește un drum, nu neapărat pe cel mai scurt.

La ce se folosesc

Componente conexe: merg ambele, dar parcurgerea în adâncime e mai scurt de scris.

Există drum de la x la y? Merg ambele. Pornești din x și verifici vizitat[y].

Drumul minim în număr de muchii: numai în lățime.

Toate vârfurile accesibile dintr-un vârf: merg ambele.

Costul

Cu matrice de adiacență, ambele parcurgeri costă n², pentru că la fiecare vârf vizitat parcurgi toată linia. Cu liste de vecini, costul scade la n + m, adică proporțional cu dimensiunea reală a grafului.

O atenționare la parcurgerea în adâncime

Parcurgerea este recursivă, deci adâncimea apelurilor poate ajunge la n. Pentru n de ordinul sutelor de mii, programul se poate opri brusc. E aceeași limită discutată la recursivitate. La dimensiunile de la bac nu este o problemă.

Un exemplu complet

Se citește un graf neorientat și două vârfuri x și y. Să se afișeze numărul minim de muchii dintre ele, sau -1 dacă nu există drum.

#include <iostream>
using namespace std;

int a[101][101], n, m;
bool vizitat[101];
int dist[101], coada[101];

int main() {
    int x, y;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int p, q;
        cin >> p >> q;
        a[p][q] = a[q][p] = 1;
    }
    cin >> x >> y;

    int prim = 1, ultim = 1;
    coada[1] = x;
    vizitat[x] = true;

    while (prim <= ultim) {
        int c = coada[prim++];
        for (int i = 1; i <= n; i++)
            if (a[c][i] == 1 && !vizitat[i]) {
                vizitat[i] = true;
                dist[i] = dist[c] + 1;
                coada[++ultim] = i;
            }
    }

    if (vizitat[y]) cout << dist[y];
    else cout << -1;

    return 0;
}

dist[x] rămâne 0, ceea ce este corect: distanța de la un vârf la el însuși.

De reținut

• Orice parcurgere are nevoie de vectorul vizitat, altfel ciclurile o blochează.
• În adâncime: recursiv, marchezi la intrare.
• În lățime: cu coadă, marchezi la adăugare, nu la scoatere.
• Numai parcurgerea în lățime dă drumul minim în număr de muchii.
• Vârfurile nevizitate la final nu sunt accesibile din start.