Badanie własności drzewa z wykorzystaniem algorytmu DFS (Depth First Search):
- odległość od korzenia
- wielkość podrzewa
Przykładowy opis algotyrmu w języku c++:
-
//przykladowe dane 1
-
// 4 1 2 2 -> 4 wierzcholki | opis wejscia -> kto jest ojcem wierzcholka
-
//(dla W[1]->brak ojca - nie wystepuje na wejsciu)
-
-
//przykladowe dane 2
-
// 12 1 1 1 4 5 6 6 6 7 9 8
-
-
#include <algorithm>
-
#include <iomanip>
-
#include <iostream>
-
#include <vector>
-
using namespace std;
-
-
void DFS(int);
-
-
vector <int> V[100]; //lista ojcow
-
int Odl[100]; //tabela odleglosci od korzenia
-
int Wlk[100]; //wielkość poddrzewa
-
bool Odw[100]; //tabela odwiedzonych
-
-
int i,n,x,j;
-
-
int main()
-
{
-
ios_base::sync_with_stdio(false);
-
cin>>n;
-
-
//umieszczamy dane o wierzcholkach w wektorze
-
for ( i=2 ; i<=n ; i++ )
-
{
-
cin>>x;
-
V[x].push_back(i);
-
}
-
-
for ( i=1 ; i<=n ; i++ )
-
{
-
cout<<i<<" -> ";
-
for ( j=0 ; j<V[i].size() ; j++ )
-
cout<<V[i][j]<<" ";
-
cout<<endl;
-
}
-
-
//uruchamiamy funkcję DFS
-
DFS(1);
-
-
/*** WYNIKI ***/
-
/* Przegląd tablicy odległosci od punktu 1 */
-
cout<<endl;
-
for ( i=1 ; i<=n ; i++ )
-
cout << Odl[i] << " ";
-
-
/* Przegląd tablicy odwiedzonych */
-
cout<<endl;
-
for ( i=1 ; i<=n ; i++ )
-
cout << Odw[i] << " ";
-
-
/* Wielkosc podrzew */
-
cout<<endl;
-
for ( i=1 ; i<=n ; i++ )
-
cout << Wlk[i] << " ";
-
}
-
-
-
void DFS(int x)
-
{
-
int w;
-
Wlk[x]=1;
-
Odw[x]=1;
-
for(int k=0 ; k<V[x].size() ; k++)
-
{
-
w=V[x][k];
-
if (!Odw[w])
-
{
-
Odl[w]=Odl[x]+1;
-
cout<<"\nDFS("<<w<<")";
-
DFS(w);
-
}
-
Wlk[x]+=Wlk[V[x][k]];
-
}
-
}
-
-
Przykładowe drzewo (dane 2 z powyższego zadania)
