SISergiu Ilincameditații informatică
Meniu

clasa a XI-a · Grafuri · lecția 11

Parcurgerea grafurilor: în lățime (BFS) și în adâncime (DFS)

60 minmate-info

Înainte de lecția asta: XI.10 Grafuri neorientate (2): conexitate, graf complet, bipartit, hamiltonian, eulerian

Ce vei ști după lecție

  • Parcurgi un graf în lățime (BFS) cu o coadă și în adâncime (DFS) recursiv.
  • Scrii de mână ordinea de vizitare BFS / DFS pornind dintr-un vârf (grilă de Bac).
  • Folosești parcurgerile pentru conexitate, componente conexe și lanțul de lungime minimă.

Lecția are și o fișă de lucru, de rezolvat după ce o citești. Mergi la fișă ↓

Clasa a XI-aLecția 11 din 21 · mai sunt 10Urmează: XI.12 · Grafuri orientate: arce, grade, drumuri, circuite, tare conexitateVezi toate lecțiile
Cuprins

Fișiere PDF și de lucru

1. Ideea: cum „vizitezi” un graf

Ai o hartă cu drumuri și vrei să afli ce orașe poți atinge din orașul 1. Sunt două strategii naturale:

  • DFS (în adâncime): mergi cât poți înainte pe un drum; când ajungi într-un capăt mort, te întorci un pas și încerci altă variantă. Ca într-un labirint cu un fir de ață.
  • BFS (în lățime): vizitezi mai întâi toți vecinii (la distanța 1), apoi vecinii lor (distanța 2), și tot așa. Ca o undă pe apă.

Graful exemplu

Folosim peste tot graful acesta, dat prin n = 7, m = 6 și muchiile 1 2, 1 3, 2 4, 3 4, 4 5, 6 7. Vecinii se iau în ordinea crescătoare a numerelor.

2. DFS în adâncime, pas cu pas

Regula: vizitezi vârful x; pentru fiecare vecin y nevizitat, repeți operația pentru y.

DFS

Pas Vârf curent Vecini Ce se întâmplă Ordine
1 1 2, 3 marchez 1; primul vecin nevizitat: 2 1
2 2 1, 4 marchez 2; 1 e vizitat; merg în 4 1 2
3 4 2, 3, 5 marchez 4; 2 e vizitat; merg în 3 1 2 4
4 3 1, 4 marchez 3; ambii vizitați; mă întorc în 4 1 2 4 3
5 4 5 merg în 5 1 2 4 3 5
6 5 4 marchez 5; nimic nou; mă întorc până în 1 1 2 4 3 5

Stiva recursivității

#include <iostream>
using namespace std;

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

void dfs(int x)
{
    viz[x] = 1;
    cout << x << ' ';                     // „vizităm” vârful
    for (int y = 1; y <= n; y++)
        if (a[x][y] == 1 && !viz[y])      // vecin încă nevizitat
            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);
    return 0;
}

De ce așa?

De ce viz[]? Fără marcaj, graful 1-2 ar face dfs(1) → dfs(2) → dfs(1) → … la infinit. Marcăm vârful înainte de a coborî mai adânc. De ce recursivitate? Revenirea („mă întorc în 4”) vine gratis: când dfs(3) se termină, execuția continuă în dfs(4) exact de unde rămăsese (vezi stiva din figură).

La fel, cu liste de adiacență (mai rapid pe grafuri mari):

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> L[101];
int viz[101], n, m;

void dfs(int x)
{
    viz[x] = 1;
    cout << x << ' ';
    for (int i = 0; i < (int)L[x].size(); i++)
    {
        int y = L[x][i];
        if (!viz[y]) dfs(y);
    }
}

int main()
{
    cin >> n >> m;
    for (int k = 1; k <= m; k++)
    {
        int x, y;
        cin >> x >> y;
        L[x].push_back(y);
        L[y].push_back(x);
    }
    for (int i = 1; i <= n; i++) sort(L[i].begin(), L[i].end());    // vecini în ordine crescătoare
    int start;
    cin >> start;
    dfs(start);
    return 0;
}

De știut

Complexitate: cu matrice O(n²) (pentru fiecare vârf scanezi o linie întreagă), cu liste O(n + m) (fiecare vârf și fiecare muchie sunt atinse de un număr constant de ori). Pentru n = 100 000 doar varianta cu liste e practică.

3. BFS în lățime și distanțele minime

Regula: punem vârful de start într-o coadă. Cât timp coada nu e goală: scoatem primul vârf x; pentru fiecare vecin y nevizitat, îl marcăm, îi punem distanța d[x] + 1 și îl băgăm în coadă.

BFS Coada

De ce BFS dă distanțele minime? Coada păstrează vârfurile în ordinea distanței: mai întâi toate cele cu distanța 1, apoi 2, etc. Prima dată când un vârf e descoperit, este descoperit pe drumul cel mai scurt.

Trace pentru d[] (-1 = nevizitat):

Pas scot coada după d[1..5]
0 1 0, -1, -1, -1, -1
1 1 2 3 0, 1, 1, -1, -1
2 2 3 4 0, 1, 1, 2, -1
3 3 4 0, 1, 1, 2, -1 (4 e deja marcat)
4 4 5 0, 1, 1, 2, 3
5 5 (gol) 0, 1, 1, 2, 3
#include <iostream>
using namespace std;

int a[101][101], d[101], coada[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 start;
    cin >> start;

    for (int i = 1; i <= n; i++) d[i] = -1;      // -1 = nevizitat
    int prim = 0, ultim = 0;
    coada[ultim++] = start;
    d[start] = 0;
    while (prim < ultim)
    {
        int x = coada[prim++];                    // scot primul
        for (int y = 1; y <= n; y++)
            if (a[x][y] && d[y] == -1)
            {
                d[y] = d[x] + 1;
                coada[ultim++] = y;               // adaug la sfârșit
            }
    }
    for (int i = 1; i <= n; i++) cout << d[i] << ' ';
    return 0;
}

De ce așa?

De ce d[y] == -1 ca „nevizitat”? Distanța 0 e validă (pentru start), deci nu putem folosi 0 ca „necunoscut”. De ce coada este un vector cu doi indici? Fiecare vârf intră o singură dată, deci nu depășim n elemente: prim și ultim ajung. De ce rămân -1 la vârfurile 6 și 7? Nu sunt în componenta lui 1: nu se poate ajunge la ele.

Drumul minim efectiv: vectorul de părinți

Pe lângă d[y], reținem tata[y] = x (de unde l-am descoperit). Apoi reconstruim drumul de la destinație înapoi.

Drumul minim

#include <iostream>
using namespace std;

int a[101][101], d[101], tata[101], coada[101], n, m;

void afisDrum(int x)
{
    if (x == 0) return;
    afisDrum(tata[x]);                  // mai întâi drumul până la părinte
    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 start, final;
    cin >> start >> final;

    for (int i = 1; i <= n; i++) d[i] = -1;
    int prim = 0, ultim = 0;
    coada[ultim++] = start;
    d[start] = 0;                        // tata[start] = 0 (global)
    while (prim < ultim)
    {
        int x = coada[prim++];
        for (int y = 1; y <= n; y++)
            if (a[x][y] && d[y] == -1)
            {
                d[y] = d[x] + 1;
                tata[y] = x;
                coada[ultim++] = y;
            }
    }
    if (d[final] == -1) cout << "nu exista";
    else afisDrum(final);
    return 0;
}

De ce așa?

De ce reconstruim „înapoi” și afișăm „înainte”? Din final știm doar părintele (tata[final]), nu și urmașul. Mergem înapoi până la start (unde tata = 0), iar afișarea se face după apelul recursiv ca ordinea să fie de la start la final. Aceeași idee ca la afișarea unui număr în baza 2 (lecția XI.3).

Intrare / ieșire

Program Intrare Ieșire
DFS graful exemplu + start 1 1 2 4 3 5
BFS, distanțe graful exemplu + start 1 0 1 1 2 3 -1 -1
drum minim 1 → 5 graful exemplu + 1 5 1 2 4 5
drum minim 1 → 7 graful exemplu + 1 7 nu exista

4. DFS sau BFS?

DFS și BFS

DFS BFS
structură stiva recursivității coadă
cum explorează în adâncime pe niveluri
distanțe minime nu da (graf fără costuri)
componente conexe da da
ciclu / bipartit / conexitate tare foarte potrivit posibil
memorie adâncimea (poate fi n) cel mult un nivel

Sfat

„Drum cel mai scurt” într-un graf fără costuri → BFS. „Se poate ajunge?”, „câte componente?”, „are ciclu?” → DFS (mai scurt de scris).

5. Componentele conexe: număr și dimensiuni

Același dfs din main, numărând vârfurile din fiecare insulă: afișăm dimensiunea celei mai mari.

#include <iostream>
using namespace std;

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

void dfs(int x)
{
    viz[x] = 1;
    marime++;                            // încă un vârf în insula curentă
    for (int y = 1; y <= n; y++)
        if (a[x][y] && !viz[y]) 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 comp = 0, maxim = 0;
    for (int i = 1; i <= n; i++)
        if (!viz[i])
        {
            comp++;
            marime = 0;
            dfs(i);
            if (marime > maxim) maxim = marime;
        }
    cout << comp << ' ' << maxim;
    return 0;
}

De ce așa?

De ce marime = 0 înainte de fiecare dfs? Variabila e globală și se adună în toate apelurile; pentru fiecare insulă numărăm de la zero.

6. Greșeli frecvente

Greșeala Efect Corect
nu marchezi viz[x] recursivitate infinită viz[x] = 1 la intrare
marchezi la scoaterea din coadă, nu la introducere un vârf intră de mai multe ori marchezi când îl pui în coadă
d[] inițializat cu 0 nu mai deosebești „nevizitat” inițializezi cu -1
coadă prea mică depășire coada[n + 1] ajunge (fiecare vârf o dată)
citești start/final după BFS ordinea datelor greșită după m muchii
BFS pentru drum cu costuri rezultat greșit Dijkstra (lecția XI.19)

7. La BAC

La BAC

BFS/DFS nu apar ca întrebări „scrie algoritmul”, dar sunt în spatele multor itemi: „care este lungimea celui mai scurt lanț între x și y”, „câte componente conexe”, „care vârfuri sunt la distanța k de x”, „în ce ordine sunt vizitate vârfurile”. Pe grafuri mici le rezolvi cu o coadă pe hârtie, ca în tabelul de la BFS. La subiectul cu programare (II/III) se cer des componente conexe și drumuri minime, ca aici.

8. Exersează pe hârtie

1. Pe graful cu n = 6 și muchiile [1,2], [1,3], [2,4], [3,4], [4,5], [5,6], scrie ordinea DFS din 1 (vecinii în ordine crescătoare).

2. Pe același graf scrie ordinea BFS din 1 și vectorul d[1..6].

3. Care este lungimea celui mai scurt lanț între 1 și 6 în graful de la exercițiul 1? Scrie un asemenea lanț.

4. Un graf are 8 vârfuri și muchiile [1,2], [2,3], [4,5], [6,7], [7,8], [6,8]. Câte componente conexe are? Dar câte muchii minime trebuie adăugate ca să fie conex?

5. Desenează un graf cu 5 vârfuri în care DFS din 1 și BFS din 1 dau aceeași ordine. Poate fi un lanț? Dar un graf complet?

6. (BAC) Într-un arbore cu rădăcina 1 și muchiile [1,2], [1,3], [2,4], [2,5], [3,6], scrie ordinea BFS și ordinea DFS.

7. Pe graful exemplu din lecție, ce se afișează dacă dfs afișează vârful după apelurile recursive (la ieșire, nu la intrare)?

8. Ce număr maxim de elemente poate avea coada la BFS pe un graf cu n vârfuri? Dă un exemplu în care se atinge.

9. Modifică programul de BFS pentru a afișa și numărul de vârfuri care pot fi atinse din start (inclusiv el).

10. Dacă graful este un lanț 1–2–3–…–n, câți pași (apeluri) face DFS din 1? Ce adâncime are stiva?

9. Mai departe (pentru cine vrea mai mult)

DFS fără recursivitate. Folosești o stivă explicită (stack<int>): pui startul; cât timp stiva nu e goală, iei vârful x; dacă nu e vizitat, îl marchezi și pui toți vecinii nevizitați. Util când adâncimea ar da depășire de stivă (n ≈ 10⁶).

BFS pe grilă (algoritmul lui Lee). O matrice cu zid / liber este un graf în care fiecare celulă are până la 4 vecini; BFS dă drumul minim prin labirint (lecția XI.17).

Testul de ciclu și arborele DFS. Dacă DFS întâlnește un vecin deja vizitat care nu este părintele, graful (neorientat) are un ciclu.

Parcurgere multi-sursă. Pui în coadă de la început mai multe vârfuri-sursă cu d = 0; BFS-ul dă pentru fiecare vârf distanța până la cea mai apropiată sursă (de exemplu „care e cea mai apropiată farmacie?”).

Rezumat

  • DFS: vizitezi, apoi pentru fiecare vecin nevizitat apelezi recursiv; marchezi viz[x] la intrare. Complexitate O(n²) cu matrice, O(n + m) cu liste.
  • BFS: coadă + vector de distanțe d (-1 = nevizitat); găsește drumul minim fără costuri; tata[] reconstruiește drumul.
  • Componentele conexe: apelezi o parcurgere din fiecare vârf nevizitat.
  • Marchezi vârful când îl pui în coadă / când intri în el, nu mai târziu.

Fișa de lucru

Ai citit lecția? Printează fișa sau deschide-o pe ecran și rezolvă exercițiile în ordine.

Fișă de lucru · 6 pagini · 100 min

Parcurgeri BFS/DFS și grafuri orientate

  • Scrii de mână ordinea DFS și BFS, vectorul distanțelor `d` și vectorul de tați.
  • Citești un graf orientat din matrice: grade, drumuri, circuite, componente tare conexe.
  • Folosești BFS/DFS ca unealtă: lanț minim, vârfuri la distanța k, tare conexitate, ordine topologică.

Fișa acoperă și: XI.12

Te-ai blocat la un exercițiu?

Probleme de lucru

Începe cu acestea, în ordine. Problemele se deschid pe pbinfo.ro, unde trimiți soluția și primești punctajul.

  • bfs#19

    ușoară
  • dfs#539

    ușoară
  • nrcompconexe#4276

    ușoară

Temă

Rezolvă-le singur și bifează ce ai terminat. Bifele rămân salvate în acest browser.

  • lantminim#484

    BFS + vectorul de tați pentru reconstituirea lanțului.

    medie
  • lungimeminima#538

    medie
  • dmax#126

    medie
  • estearbore#4204

    ușoară
  • bazine#963

    ușoară
  • epidemie#549

    medie

Pentru cei care vor mai mult

  • ccmax#4067

    medie

Grile din subiectele de BAC

Exerciții de tip grilă din variantele de Bacalaureat. Se rezolvă pe pbinfo.ro, care îți verifică imediat răspunsul.

Citește și exersează în plus

Te-ai blocat la lecția asta?

Scrie-mi ce nu iese și vedem împreună de unde se blochează.

Răspunsuri

Exersează pe hârtie

1. 1 2 4 3 5 6 (din 1 la 2, din 2 la 4, din 4 la 3 (vecinul nevizitat cu cel mai mic număr), apoi la 5 și 6).

2. BFS: 1 2 3 4 5 6; d = 0 1 1 2 3 4.

3. Lungime 4, de exemplu 1 → 2 → 4 → 5 → 6 (4 muchii).

4. Componente: {1,2,3}, {4,5}, {6,7,8}: 3. Pentru conexitate sunt necesare cel puțin 3 − 1 = 2 muchii.

5. Da, pentru amândouă. Lanțul 1–2–3–4–5: DFS și BFS dau 1 2 3 4 5. Graful complet K₅: BFS dă 1 2 3 4 5 (toți sunt vecini ai lui 1); DFS merge 1 → 2 → 3 → 4 → 5 (la fiecare pas cel mai mic vecin nevizitat), deci tot 1 2 3 4 5. Ca să vezi o diferență între cele două parcurgeri, ia arborele cu 7 vârfuri din figura secțiunii 4.

6. BFS: 1 2 3 4 5 6; DFS: 1 2 4 5 3 6.

7. DFS din 1 vizitează 1 → 2 → 4 → 3 (3 se termină primul), apoi 5; apelurile se termină în ordinea 3, 5, 4, 2, 1. Se afișează 3 5 4 2 1.

8. Cel mult n − 1 elemente (de exemplu un graf stea: centrul 1 legat de celelalte n − 1 vârfuri; după scoaterea lui 1 toate cele n − 1 sunt în coadă).

9. Un contor: int atinse = 0; și atinse++ la fiecare vârf adăugat în coadă (inclusiv start); sau numeri câte d[i] != -1 la final.

10. DFS face n apeluri și stiva ajunge la adâncimea n (de aceea la n mare se folosește varianta iterativă).