Bella at 09:02, 15 May 2020

2020-05-15T09:02:06Z

New page

== 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

<syntaxhighlight>
/*
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;
}
</syntaxhighlight>
== 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.

<syntaxhighlight>
#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;
}

</syntaxhighlight>

= Aplicatii =
==[https://www.pbinfo.ro/?pagina=probleme&id=636 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 ===
<syntaxhighlight>
// 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;
}
</syntaxhighlight>

=== Parcurgere cu BFS ===

<syntaxhighlight>
// 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;
}
</syntaxhighlight>

== [https://www.pbinfo.ro/?pagina=probleme&id=639 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.

<syntaxhighlight>
#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;
}

</syntaxhighlight>

== [https://www.pbinfo.ro/?pagina=probleme&id=652 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.

<syntaxhighlight>
#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;
}
</syntaxhighlight>

== [https://www.pbinfo.ro/probleme/637/frunze 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

<syntaxhighlight>
#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;
}
</syntaxhighlight>

= Tema Teorie =
==[https://www.pbinfo.ro/probleme/650/knivel 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.
<syntaxhighlight></syntaxhighlight>

==[https://www.pbinfo.ro/probleme/640/nrfii 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.

<syntaxhighlight></syntaxhighlight>
==[https://www.pbinfo.ro/probleme/641/subarbore 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.

<syntaxhighlight></syntaxhighlight>
==[https://www.pbinfo.ro/probleme/648/subarborenumarare 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 =
== [https://www.pbinfo.ro/?pagina=probleme&id=638 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ă.

<syntaxhighlight>
</syntaxhighlight>

== [https://www.pbinfo.ro/?pagina=probleme&id=2749 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ă.
<syntaxhighlight>
</syntaxhighlight>

Clasa a XI-a lecția 31 - Revision history

Bella at 09:02, 15 May 2020