Arbori în C++: proprietăți și verificare cu BFS

Ce este un arbore

Un arbore este un graf neorientat conex și fără cicluri. Un ciclu simplu revine în vârful de plecare fără să repete celelalte vârfuri; într-un graf simplu are cel puțin trei muchii. Arborele leagă toate vârfurile fără să păstreze o rută alternativă care ar închide un ciclu.

Între oricare două vârfuri ale unui arbore există exact un lanț elementar. Existența rezultă din conexitate. Dacă ar exista două lanțuri elementare distincte între aceleași capete, porțiunile pe care diferă ar forma un ciclu. Această unicitate explică de ce eliminarea oricărei muchii separă arborele în două componente.

Un arbore cu n vârfuri are exact n-1 muchii. Pentru un graf simplu cu cel puțin un vârf, putem folosi și criteriul echivalent: este arbore dacă este conex și are n-1 muchii. Atenție la conjuncție: verificăm ambele condiții. Numărul muchiilor, luat singur, nu este suficient.

Imagine indisponibilă: Un arbore cu cinci vârfuri are muchiile 1-2, 1-3, 2-4 și 2-5; prin alegerea rădăcinii 1, vârful 2 devine părintele lui 4 și al lui 5.

Rădăcină, părinți și frunze

Un arbore neorientat nu are în mod obligatoriu o rădăcină. Noi alegem un vârf, de exemplu 1, pentru a descrie relații ierarhice. Părintele unui vârf diferit de rădăcină este vecinul aflat pe lanțul unic către rădăcină. Copiii sunt vecinii aflați mai departe de aceasta. Rădăcina nu are părinte.

În desen, părinții lui 2 și 3 sunt 1, iar părinții lui 4 și 5 sunt 2. Adâncimea este numărul de muchii până la rădăcină: zero pentru 1, unu pentru 2 și 3, doi pentru 4 și 5. Într-un arbore înrădăcinat, numim frunză un vârf fără copii; aici frunzele sunt 3, 4, 5.

Pentru un arbore neorientat cu cel puțin două vârfuri, frunzele sunt vârfurile de grad unu. Convenția înrădăcinată are o nuanță: o rădăcină de grad unu are un copil, deci nu este frunză în sensul „fără copii”. Arborele cu un singur vârf este valid; dacă îl înrădăcinăm, rădăcina nu are copii.

Verificarea unui graf dat

Citim n m și cele m muchii ale unui graf neorientat simplu. Presupunem 1 <= n <= 100, 0 <= m <= n*(n-1)/2, capete diferite și valide în 1..n, fără muchii repetate. Construim matricea de adiacență și pornim BFS din vârful 1.

Fiecare vârf este introdus cel mult o dată în coadă, deci valoarea finală dr este numărul de vârfuri accesibile din 1. Graful este conex exact când dr == n. Combinăm această verificare cu m == n-1 și afișăm DA sau NU.

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 viz[101] = {};
    int q[101] = {};
    int st = 0, dr = 0;
    q[dr++] = 1;
    viz[1] = 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;
            }
        }
    }
    std::cout << (m == n - 1 && dr == n ? "DA" : "NU") << '\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;
    }
    std::vector<int> viz(n + 1, 0);
    std::vector<int> q(n + 1, 0);
    int st = 0, dr = 0;
    q[dr++] = 1;
    viz[1] = 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;
            }
        }
    }
    std::cout << (m == n - 1 && dr == n ? "DA" : "NU") << '\n';
}

Tabloul clasic a[101][101] rezervă capacitatea maximă; folosim indicii 1..n. Varianta cu std::vector alocă n+1 linii și coloane și păstrează aceeași convenție. Ambele folosesc coada de la indicele zero. Limita de 100 permite o prezentare simplă; nu confundăm această alegere cu o soluție potrivită oricărui graf mare.

Contraexemple și complexitate

Consideră un triunghi pe 1,2,3 și vârful izolat 4. Avem patru vârfuri și trei muchii, deci m=n-1, însă graful nu este conex și conține un ciclu. Programul afișează NU. În schimb, steaua cu muchiile 1-2, 1-3, 1-4 este conexă și are trei muchii, deci afișează DA.

De ce ajung cele două condiții? Orice graf conex conține o structură care leagă toate vârfurile cu n-1 muchii, obținută păstrând muchia prin care descoperim fiecare vârf nou. Dacă graful întreg are exact acel număr de muchii, nu mai rămâne nicio muchie suplimentară care să închidă un ciclu.

Parcurgerea cu matrice costă O(n²) timp în cazul cel mai defavorabil. Matricea ocupă O(n²) memorie, iar coada și vizitarea adaugă O(n). Pentru tabloul fix, memoria este rezervată la capacitatea maximă indiferent de dimensiunea logică. Un graf fără cicluri, dar neconex, este o pădure; fiecare componentă a sa este un arbore.

Exersează

1. Câte muchii are un arbore cu opt vârfuri?
2. Este arbore un graf cu un vârf și fără muchii?
3. Ce se întâmplă dacă adaugi o muchie nouă între două vârfuri ale unui arbore?

Răspunsuri: șapte; da; se formează un ciclu, deoarece exista deja un lanț unic între acele vârfuri. Poți recapitula componentele conexe și reconstruirea traseului pentru a calcula ulterior părinții și adâncimile unui arbore înrădăcinat.