Parcurgerea grafurilor

Parcurgerea unui graf este operația prin care se vizitează, într-o ordine stabilită, toate nodurile accesibile dintr-un nod de pornire, fiecare o singură dată. Parcurgerea se mai numește și traversare și stă la baza multor algoritmi pe grafuri: determinarea componentelor conexe, a lanțurilor de lungime minimă, a existenței unui ciclu.

Programa cere două metode:

• parcurgerea în lățime (Breadth First, prescurtat BF) — după nodul de pornire se vizitează toți vecinii lui, apoi nodurile încă nevizitate adiacente cu aceștia, nivel după nivel;
• parcurgerea în adâncime (Depth First, prescurtat DF) — de la nodul curent se trece la primul vecin nevizitat, apoi la primul vecin nevizitat al acestuia, iar când nodul curent nu mai are vecini nevizitați se revine la nodul anterior de pe drumul parcurs.

Noțiuni preliminare

Subiectele despre parcurgeri cer, de obicei, câteva definiții înaintea algoritmului:

• graful este o pereche G = (X, U), în care X este o mulțime finită și nevidă de noduri, iar U o mulțime de perechi de noduri distincte; la graful neorientat perechile sunt neordonate și se numesc muchii, la graful orientat sunt ordonate și se numesc arce;
• două noduri sunt adiacente dacă formează o muchie, respectiv dacă sunt legate printr-un arc; nodurile adiacente cu un nod x sunt vecinii lui x;
• parcurgerea unui graf pornind din nodul x este vizitarea, într-o ordine stabilită, a tuturor nodurilor accesibile din x, fiecare o singură dată.

Terminologia completă este în subcapitolul Grafuri orientate și neorientate. Terminologie.

Graful folosit în exemple

Ambele parcurgeri pornesc din nodul 1 și examinează vecinii unui nod în ordinea crescătoare a etichetelor, ordinea în care apar pe linia nodului în matricea de adiacență.

Datele de intrare ale programelor au forma: pe prima linie n și m, pe următoarele m linii extremitățile câte unei muchii, iar pe ultima linie nodul de pornire. Pentru graful G:

10 11
1 2
1 5
2 3
2 6
3 4
4 8
5 6
5 9
6 7
7 10
9 10
1

Parcurgerea în lățime

Descrierea algoritmului

Parcurgerea în lățime folosește două structuri auxiliare:

• vectorul viz, cu viz[i] = 1 dacă nodul i a fost deja vizitat și viz[i] = 0 în caz contrar; el împiedică vizitarea aceluiași nod de două ori;
• vectorul coada, în care se memorează nodurile vizitate, în ordinea vizitării; nodurile se adaugă la sfârșitul cozii și se prelucrează de la începutul ei. Coada se implementează cu doi indici: p, poziția nodului care se prelucrează, și u, poziția ultimului nod adăugat.

Etapele algoritmului:

1. Nodul de pornire pl se marchează ca vizitat și se pune în coadă.
2. Cât timp coada nu este vidă, se prelucrează nodul coada[p] de la începutul cozii.
3. Fiecare vecin j al lui coada[p] care nu a fost vizitat se marchează ca vizitat și se adaugă la sfârșitul cozii; apoi p crește cu 1.
4. Parcurgerea se încheie când coada devine vidă. Ordinea vizitării este ordinea nodurilor în coadă.

Un nod se marchează ca vizitat în momentul în care intră în coadă, nu când este extras. Altfel, un nod vecin cu două noduri aflate deja în coadă ar fi adăugat de două ori.

Exemplificarea etapelor

Pentru graful G, pornind din nodul 1:

Ordinea parcurgerii în lățime este 1 2 5 3 6 9 4 7 10 8. La pasul în care se extrage nodul 2, vecinul 1 nu mai intră în coadă, fiindcă este vizitat; la extragerea nodului 5, vecinul 6 este deja în coadă, deci nici el nu se mai adaugă.

Programul

BF(pl):
    coada[1] ← pl; viz[pl] ← 1
    p ← 1; u ← 1
    cât timp p ≤ u execută
        pentru j ← 1, n execută
            dacă a[coada[p]][j] = 1 și viz[j] = 0
            atunci
                u ← u + 1
                coada[u] ← j
                viz[j] ← 1
            sfdacă
        sfpentru
        p ← p + 1
    sfcât timp

programul principal:
    citește graful și nodul pl
    BF(pl)
    pentru i ← 1, u execută
        scrie coada[i]
    sfpentru

#include <iostream>
using namespace std;

const int MAX = 101;
int a[MAX][MAX], viz[MAX], coada[MAX], n, m, p, u;

void citire() {
    int x, y;
    cin >> n >> m;
    for (int k = 1; k <= m; k++) {
        cin >> x >> y;
        a[x][y] = a[y][x] = 1;
    }
}

/* Parcurgerea in latime din nodul pl. Coada are elementele de la
   coada[p] la coada[u]; la sfarsit, coada[1..u] contine nodurile
   in ordinea vizitarii. */
void BF(int pl) {
    coada[1] = pl;
    viz[pl] = 1;
    p = 1;
    u = 1;
    while (p <= u) {                    // mai sunt noduri de prelucrat
        for (int j = 1; j <= n; j++)
            if (a[coada[p]][j] == 1 && viz[j] == 0) {
                u++;
                coada[u] = j;           // vecinul intra la sfarsitul cozii
                viz[j] = 1;             // si se marcheaza imediat
            }
        p++;                            // se trece la urmatorul nod din coada
    }
}

int main() {
    int pl;
    citire();
    cin >> pl;
    BF(pl);
    for (int i = 1; i <= u; i++)        // nodurile, in ordinea vizitarii
        cout << coada[i] << " ";
    return 0;
}

Pentru graful G și nodul de pornire 1, programul afișează 1 2 5 3 6 9 4 7 10 8.

Complexitatea

Fiecare nod intră în coadă cel mult o dată și este extras cel mult o dată. La extragerea unui nod se examinează vecinii lui:

• cu matricea de adiacență, examinarea vecinilor unui nod parcurge toată linia, adică n elemente, deci timpul total este de ordinul O(n²);
• cu listele de adiacență, se examinează numai vecinii efectivi; suma lungimilor listelor este 2m la graful neorientat, deci timpul total este de ordinul O(n + m).

Memoria suplimentară este O(n): vectorul viz și coada.

Lanțul de lungime minimă

Parcurgerea în lățime vizitează nodurile în ordinea crescătoare a numărului de muchii prin care se ajunge la ele din nodul de pornire. Un nod intră în coadă prima dată pe un lanț cu număr minim de muchii, deci parcurgerea determină lanțurile de lungime minimă de la nodul de pornire la toate celelalte noduri.

Pentru aceasta se mai rețin doi vectori:

• d[j] — lungimea lanțului minim de la pl la j; când j este adăugat din nodul coada[p], d[j] = d[coada[p]] + 1;
• tata[j] — nodul coada[p] din care a fost adăugat j; lanțul se reconstituie mergând din tata în tata, de la destinație înapoi spre pl.

Pentru graful G și nodul de pornire 1:

Enunț. Se citesc un graf neorientat și două noduri x și y. Să se afișeze lungimea unui lanț de lungime minimă de la x la y și nodurile lui, sau mesajul nu exista lant dacă y nu este accesibil din x.

#include <iostream>
using namespace std;

const int MAX = 101;
int a[MAX][MAX], viz[MAX], coada[MAX], d[MAX], tata[MAX], n, m;

void citire() {
    int x, y;
    cin >> n >> m;
    for (int k = 1; k <= m; k++) {
        cin >> x >> y;
        a[x][y] = a[y][x] = 1;
    }
}

/* Parcurgerea in latime din pl, care retine pentru fiecare nod
   lungimea lantului minim (d) si nodul din care a fost atins (tata). */
void BF(int pl) {
    int p = 1, u = 1;
    coada[1] = pl;
    viz[pl] = 1;
    while (p <= u) {
        for (int j = 1; j <= n; j++)
            if (a[coada[p]][j] == 1 && viz[j] == 0) {
                u++;
                coada[u] = j;
                viz[j] = 1;
                d[j] = d[coada[p]] + 1;
                tata[j] = coada[p];
            }
        p++;
    }
}

/* Afiseaza lantul de la x la y: intai lantul pana la tata[y],
   apoi nodul y. */
void afiseazaLant(int x, int y) {
    if (y != x)
        afiseazaLant(x, tata[y]);
    cout << y << " ";
}

int main() {
    int x, y;
    citire();
    cin >> x >> y;
    BF(x);
    if (viz[y] == 0)
        cout << "nu exista lant";
    else {
        cout << "lungime " << d[y] << ": ";
        afiseazaLant(x, y);
    }
    return 0;
}

Pentru graful G, x = 1 și y = 10, programul afișează lungime 3: 1 5 9 10.

Parcurgerea în adâncime

Descrierea algoritmului

Parcurgerea în adâncime înaintează cât se poate de departe de nodul de pornire, pe o singură direcție, și revine numai când nodul curent nu mai are vecini nevizitați. Nodurile de pe drumul parcurs se păstrează într-o stivă: vârful stivei este nodul curent, iar revenirea înseamnă eliminarea lui din stivă.

Etapele algoritmului:

1. Nodul de pornire x se vizitează, se marchează și se pune în stivă.
2. Cât timp stiva nu este vidă, se consideră nodul k din vârful stivei și se caută primul lui vecin nevizitat.
3. Dacă există un asemenea vecin i, el se vizitează, se marchează și se pune în stivă, deci devine nodul curent.
4. Dacă nu există, nodul k se elimină din stivă, iar parcurgerea continuă cu nodul de sub el.
5. Parcurgerea se încheie când stiva devine vidă.

Stiva se poate înlocui cu autoapelul: subprogramul parcurgereInAdancime(x) vizitează nodul x și se autoapelează pentru fiecare vecin nevizitat. Stiva apelurilor recursive păstrează drumul de revenire, iar încheierea unui apel este revenirea la nodul anterior.

Exemplificarea etapelor

Pentru graful G, pornind din nodul 1:

Programul

parcurgereInAdancime(x):
    scrie x
    viz[x] ← 1
    pentru j ← 1, n execută
        dacă a[x][j] = 1 și viz[j] = 0 atunci
            parcurgereInAdancime(j)
        sfdacă
    sfpentru

#include <iostream>
using namespace std;

const int MAX = 101;
int a[MAX][MAX], viz[MAX], n, m;

void citire() {
    int x, y;
    cin >> n >> m;
    for (int k = 1; k <= m; k++) {
        cin >> x >> y;
        a[x][y] = a[y][x] = 1;
    }
}

/* Parcurgerea in adancime din nodul x: se viziteaza x, apoi se
   continua din fiecare vecin inca nevizitat. */
void parcurgereInAdancime(int x) {
    cout << x << " ";
    viz[x] = 1;
    for (int j = 1; j <= n; j++)
        if (a[x][j] == 1 && viz[j] == 0)
            parcurgereInAdancime(j);
}

int main() {
    int x;
    citire();
    cin >> x;
    parcurgereInAdancime(x);
    return 0;
}

Pentru graful G și nodul de pornire 1, programul afișează 1 2 3 4 8 6 5 9 10 7.

Varianta cu stivă explicită urmează exact tabelul de mai sus: vârful stivei este nodul curent, iar pentru el se caută primul vecin nevizitat.