Clasa a XI-a lecția 31

BFS - folosind vectorul de tati

• Determinarea inaltimii unui arbore
• Afisarea nodurilor in ordinea parcurgerii

Pentru a parcurge in latime un graf pentru care stim vectorii de tati, vom proceda in felul urmator.

• Identificam nodul radacina in vectorul de tati (este nodul pentru care tatal este 0) ;
• Pornim pargurgerea grafului din nodul radacina si adaugam nodurile parcurse intr-o coada.
• In timp ce parcurgem nodurile putem marca nivelul pe care se gaseste fiecare nod, nodul radacina va fi marcat ca avand nivelul 1 in graf.
• Algoritmul de parcurgere va cauta pentru fiecare nod, descendentii acestuia in vectorul de tati cautare ce se realizeaza pentru un singur nod in O(n), respectiv pentru toate cele n noduri O(n^2). Pentru fiecare nod

/*
Se citeste vectorul de tati asociat unui arbore cu radacina.
1. Afisati cate nivele are arborele?
2. Afisati nodurile arborelui parcurgand arborele in latime, pornind din nodul radacina
*/

#include <fstream>

using namespace std;
ifstream fin( "inaltime.in" );
ofstream fout( "inaltime.out" );

int t[101];
int c[101], niv[101];         // in viz punem nivelul
int n;
void bfs( int r ){
  int p, u;
  p = u = 1;
  c[1] = r;                             // pun in coada radacina
  niv[1] = 1;                           // nivelul primului nod introdus este 1
  while( p <= u ){
    for( int i = 1; i <= n; i++ )       // parcurg vectorul de tati si caut nodurile pentru care c[p] e tata
      if( t[i] == c[p] ){               // daca i e descendent al lui c[p] = daca nodul i il are ca tata pe c[p]
        c[++u] = i;                     // il pun in coada
        niv[u] = niv[p] + 1;            // il marchez ca vizitat, i are nivelul lui nod + 1
      }
    p++;                              // trec la urm element din coada
  }
}

int main(){
  int i, r;

  // citesc vectorul de tati si identific radacina
  fin >> n;
  for( i = 1; i <= n; i++ ){
    fin >> t[i];
    if( t[i] == 0 )
      r = i;
  }

  // parcurg graful in latime pornind din nodul radacina
  bfs( r );
  
  // nivelul ultimului element vizitat este chiar inaltimea arborelui
  fout << niv[n] << " ";       
  
  // afisez nodurile memorate in vectorul coada, in ordinea parcurgerii
  for( int i = 1; i <= n; i++ )
    fout << c[i] << " ";
  return 0;
}

DFS - folosind vectorul de tati

Pentru a determina inaltimea unui graf, putem de asemenea sa parcurgem graful in adancime si sa marcam nivelul unui nod ca fiind nivelul cu 1 mai mult decat ascendentul lui.

#include <fstream>

using namespace std;
ifstream fin( "inaltime.in" );
ofstream fout( "inaltime.out" );

int t[101];
int niv[101];         // in viz punem nivelul
int n, nivmax;
void dfs( int r ){
  for( int i = 1; i <= n; i++ )
    if( t[i] == r ){       // daca daca r e tatal lui i
      niv[i] = niv[r] + 1;
      if (niv[i] > nivmax )
        nivmax = niv[i];
      dfs(i);
  }
}

int main(){
  int i, r;

  // citesc vectorul de tati si identific radacina
  fin >> n;
  for( i = 1; i <= n; i++ ){
    fin >> t[i];
    if( t[i] == 0 )
      r = i;
  }

  // parcurg graful in adancime pornind din nodul radacina

  niv[r] = 1;
  dfs( r );

  // nivelul maxim atins in parcurgerea dfs
  fout << nivmax << " ";

  return 0;
}

Aplicatii

Arbore

Se dau cele n-1 muchii ale unui arbore cu n noduri și un nod k . Afișați vectorul de tați al arborelui cu rădăcina în k.

Parcurgere cu DFS

// Parcurgem in agancime arborele si marcam pentru fiecare nod tatal intr-un vector de tati
// Nodul radacina va avea 0 ca tata.

#include <iostream>
#include <fstream>

using namespace std;
ifstream fin( "arbore.in" );
ofstream fout( "arbore.out" );
int a[101][101];
int t[101],viz[101];
int n, k;
void dfs( int k ){
  viz[k] = 1;
  for( int i = 1; i <= n; i++ )
    if( a[k][i] == 1 && !viz[i] ){
      t[i] = k;
      dfs(i);
    }
}
int main(){
  int i, x, y;
  fin >> n >> k;
  for( i = 1; i <= n - 1; i++ ){  // citim cele n-1 muchii
    fin >> x >> y;
    a[x][y] = a[y][x] = 1;        // le marcam in matricea de adiacenta
  }
  dfs(k);                         // parcurgem in adancime graful si marcam pentru fiecare nod tatal
  for( i = 1; i <= n; i++ )       // afisam vectorul de tati
    fout << t[i] << " ";
  
  return 0;
}

Parcurgere cu BFS

// Parcurgem in latime arborele si marcam pentru fiecare nod tatal intr-un vector de tati
// Nodul radacina va vea 0 ca tata.
#include <fstream>

using namespace std;
ifstream fin("arbore.in");
ofstream fout("arbore.out");

int A[101][101],viz[101],c[101], t[101];
int n,k;
void bfs( int r ){
  int p, u, nod;
  p = u = 0;
  c[p] = r;
  viz[r] = 1;
  while( p <= u ){
    nod = c[p];  // nodul pentru care pun
    for( int i = 1; i <= n; i++ )     // parcurg linia nod
      if( A[nod][i] == 1 && !viz[i] ){// daca i e vecin cu nod
        c[++u] = i;                   // il pun in coada
        viz[nod] = 1;                 // il marchez ca vizitat
        t[i] = nod;                   // tatal nodului i este nod
      }
    p++;                              // trec la urm element din coada
  }
}

int main(){
    int x, y;
    fin >> n >> k;
    t[k] = 0;
    for( int i = 1; i < n; i++ ){
        fin >> x >> y;
        A[x][y] = A[y][x] = 1;

    }
    bfs( k );
    for( int i = 1; i <= n; i++ )
      fout << t[i] <<" ";
    return 0;
}

Inaltime

Se dă vectorul de tați al unui arbore cu rădăcină cu n noduri. Determinați înălțimea arborelui.

DFS - folosind vectorul de tati

Pentru a determina inaltimea unui graf, putem de asemenea sa parcurgem graful in adancime si sa marcam nivelul unui nod ca fiind nivelul cu 1 mai mult decat ascendentul lui.

#include <fstream>

using namespace std;
ifstream fin( "inaltime.in" );
ofstream fout( "inaltime.out" );

int t[101];
int niv[101];         // in viz punem nivelul
int n, nivmax;
void dfs( int r ){
  for( int i = 1; i <= n; i++ )
    if( t[i] == r ){       // daca daca r e tatal lui i
      niv[i] = niv[r] + 1;
      if (niv[i] > nivmax )
        nivmax = niv[i];
      dfs(i);
  }
}

int main(){
  int i, r;

  // citesc vectorul de tati si identific radacina
  fin >> n;
  for( i = 1; i <= n; i++ ){
    fin >> t[i];
    if( t[i] == 0 )
      r = i;
  }

  // parcurg graful in adancime pornind din nodul radacina

  niv[r] = 1;
  dfs( r );

  // nivelul maxim atins in parcurgerea dfs
  fout << nivmax << " ";

  return 0;
}

AfisareFii

Se dă vectorul de tați al unui arbore cu rădăcină cu n noduri și k noduri distincte din arbore. Afișați fiii fiecăruia dintre cele k noduri.

#include <fstream>

using namespace std;
ifstream fin( "afisarefii.in" );
ofstream fout( "afisarefii.out" );

int t[101];
int f[101];
int main(){
  int n, i, k, j, x;
  fin >> n;
  for( i = 1; i <= n; i++ ){
    fin >> t[i];
    f[t[i]] ++;            // numar in f cate noduri au ca tata pe t[i]
  }
  fin >> k;
  for( i = 1; i <= k; i++ ){
    fin >> x;
    fout << f[x] << " ";
    for( j = 1; j <= n; j++ ) // afisam nodurile care il au ca tata pe x
      if( t[j] == x )
        fout << j << " ";
    fout << endl;
  }
  return 0;
}

Frunze

Cerința : Se dă vectorul de tați al unui arbore cu rădăcină cu n noduri. Determinați rădăcina arborelui și frunzele acestuia. Date de intrare: Fișierul de intrare frunze.in conține pe prima linie numărul de noduri n. Pe linia următoare se află vectorul de tați al arborelui, valorile fiind separate prin spații. Date de ieșire: Fișierul de ieșire frunze.out va conține pe prima linie rădăcina arborelui. A doua linia va conține numărul de frunze din arbore, iar următoarea linie frunzele, în ordine crescătoare și separate printr-un spațiu. Restricții și precizări 1 ≤ n ≤ 100 în vectorul de tați rădăcina este marcată cu 0

Exemplu frunze.in 7 4 1 7 0 7 7 1 frunze.out 4 4 2 3 5 6

#include <fstream>

using namespace std;
ifstream fin( "frunze.in" );
ofstream fout( "frunze.out" );

int t[101];
int f[101];
int main(){
  int n, i;

  fin >> n;
  for( i = 1; i <= n; i++ ){
    fin >> t[i];
    f[t[i]] ++;            // numar in f cate noduri au ca tata pe t[i]
    if( t[i] == 0 )        // daca i e radacina arborelui
      fout << i << "\n";   // il afisez
  }

  int frunze = 0;          // numar frunzele arborelul
  for( i = 1; i <= n; i++ )
      if( f[i] == 0 )      // i e frunza daca nu apare ca tata la niciun nod
        frunze ++;
  fout << frunze << "\n";
  for( i = 1; i <= n; i++ )// afisez toate nodurile frunza
    if( f[i] == 0 )
      fout << i << " ";
    fout << "\n";

  return 0;
}

Tema Teorie

kNivel

Se dă vectorul de tați al unui arbore cu rădăcină cu n noduri și o valoare k. Determinați nodurile situate pe nivelul k în arbore.

NrFii

Se dă vectorul de tați al unui arbore cu rădăcină cu n noduri. Determinați nodul din arbore cu număr maxim de fii. Dacă în arbore sunt mai multe noduri cu număr maxim de fii, afișați-le pe toate, în ordine crescătoare.

Subarbore

Se dă vectorul de tați al unui arbore cu rădăcină cu n noduri și un nod k. Afișați, în ordine crescătoare, nodurile din subarborele cu rădăcina în k.

SubarboreNumarare

Se dă vectorul de tați al unui arbore cu rădăcină cu n noduri și un nod k. Determinați câte noduri conține subarborele cu rădăcina în k.

Laborator

Nivele

Se dă vectorul de tați al unui arbore cu rădăcină cu n noduri și k noduri din arbore. Determinați pentru fiecare dintre cele k noduri nivelul pe care se află.

tata

Se dă un vector t=(t[1], t[2], ..., t[n]) care memorează numere naturale cuprinse între 0 și n. Să se verifice dacă t este sau nu vector de tați asociat unui arbore cu rădăcină.