Diametrul unui arbore prin două parcurgeri BFS C++

Diametrul unui arbore este lungimea celui mai lung drum simplu dintre două vârfuri. Un drum simplu nu repetă vârfuri. Aici fiecare muchie are lungimea 1, deci lungimea drumului este numărul muchiilor, nu numărul vârfurilor de pe el.

Ce date presupunem

Citim 1≤n≤100 și n-1 muchii care formează un arbore neorientat: graful este conex și nu are cicluri. Vârfurile sunt numerotate 1..n. Afișăm diametrul în muchii. Pentru un singur vârf, răspunsul este 0.

Nu verificăm separat dacă intrarea este arbore. Metoda următoare folosește această proprietate, deci nu trebuie aplicată automat unui graf general. Într-un arbore există un singur drum simplu între oricare două vârfuri.

Două porniri diferite

BFS, de la Breadth-First Search, înseamnă parcurgere în lățime: vizităm vârfurile pe niveluri de distanță. O coadă extrage vârfurile în ordinea introducerii, iar un vecin nou primește distanța vârfului curent plus unu.

Pornim întâi din vârful 1 și găsim un vârf cât mai îndepărtat, numit capat. Pornim a doua oară din capat; cea mai mare distanță obținută este diametrul. Într-un arbore fără ponderi, un vârf aflat la distanță maximă de un start este un capăt al unui diametru. Proprietatea se bazează pe unicitatea drumurilor; dacă ramura lui s-ar termina înaintea ambelor capete ale unui drum mai lung, unul dintre acele capete ar fi mai departe de start.

În arborele cu muchii 1-2,2-3,3-4,2-5, drumul 1-2-3-4 are trei muchii și este un diametru. Două parcurgeri în lățime găsesc lungimea 3.Mărește schema ↗

Varianta cu tablou clasic

#include <iostream>
#include <queue>
#include <utility>
using namespace std;
pair<int,int> departe(int s,int n,int a[][101]) {
    int dist[101]; for(int i=1;i<=n;++i) dist[i]=-1;
    queue<int> q; q.push(s); dist[s]=0; int ultim=s;
    while(!q.empty()) {
        int u=q.front(); q.pop(); ultim=u;
        for(int v=1;v<=n;++v) if(a[u][v] && dist[v]==-1) {
            dist[v]=dist[u]+1; q.push(v);
        }
    }
    return {ultim,dist[ultim]};
}
int main() {
    int n; cin >> n; int a[101][101]={};
    for(int i=1;i<n;++i) { int u,v; cin >> u >> v; a[u][v]=a[v][u]=1; }
    int capat=departe(1,n,a).first;
    cout << departe(capat,n,a).second << '\n';
}

Varianta echivalentă cu std::vector

Păstrăm limitele intrării și aceleași rezultate. Tabloul clasic rezervă capacitatea maximă; vectorul construiește numărul de elemente necesare. Indicii folosiți de algoritm rămân aceiași.

#include <vector>

#include <iostream>
#include <queue>
#include <utility>
using namespace std;
pair<int,int> departe(int s,int n,const vector<vector<int>>& a) {
    vector<int> dist(n+1); for(int i=1;i<=n;++i) dist[i]=-1;
    queue<int> q; q.push(s); dist[s]=0; int ultim=s;
    while(!q.empty()) {
        int u=q.front(); q.pop(); ultim=u;
        for(int v=1;v<=n;++v) if(a[u][v] && dist[v]==-1) {
            dist[v]=dist[u]+1; q.push(v);
        }
    }
    return {ultim,dist[ultim]};
}
int main() {
    int n; cin >> n; vector<vector<int>> a(n+1,vector<int>(n+1));
    for(int i=1;i<n;++i) { int u,v; cin >> u >> v; a[u][v]=a[v][u]=1; }
    int capat=departe(1,n,a).first;
    cout << departe(capat,n,a).second << '\n';
}

De ce ultimul extras este suficient

BFS extrage în ordine nedescrescătoare a distanței, deci ultimul vârf extras are distanță maximă. Dacă mai multe au aceeași distanță, oricare este potrivit pentru această problemă. Funcția întoarce o pereche: first este vârful, second este distanța.

Pentru drumul 1–2–3–4, prima parcurgere ajunge la 4, iar a doua găsește distanța 3 până la 1. Pentru o stea cu centrul 1 și frunzele 2,3,4, diametrul este 2, între două frunze.

Matricea de adiacență cere O(n²) memorie și O(n²) timp pentru o parcurgere. Două parcurgeri păstrează același ordin de timp. Cu liste de adiacență costul ar fi liniar, dar nu acesta este codul prezentat.

Exersează

Verifică un vârf, o muchie, un drum de patru vârfuri și steaua de mai sus: diametrele sunt 0,1,3,2. Desenează un exemplu în care vârful 1 nu este capăt al diametrului, pentru a vedea de ce este necesară prima parcurgere.

Continuă cu proprietățile arborilor, distanțele prin BFS și reprezentarea grafurilor.

Întrebări frecvente

Ce este diametrul unui arbore?

Lungimea celui mai lung drum simplu dintre două vârfuri. În această lecție, fiecare muchie are lungimea 1, deci diametrul numără muchiile, nu vârfurile drumului.

Cum găsesc diametrul unui arbore prin două BFS-uri?

BFS este parcurgerea în lățime. Pornește dintr-un vârf oarecare și găsește un vârf cel mai îndepărtat; pornește apoi din acesta. Distanța maximă a celei de-a doua parcurgeri este diametrul arborelui neponderat.

Pot aplica aceeași regulă oricărui graf?

Nu ca garanție exactă. Argumentul celor două parcurgeri folosește structura de arbore, conexă și fără cicluri. Pentru un singur vârf, diametrul este 0.