Algorytm poszukiwania średnicy drzewa. Średnicą drzewa nazywamy odległośc między najbardziej oddalonymi od siebie wierzchołkami drzewa.
Do poszukiwania średnicy drzewa wykorzystaliśmy algorytm DFS.
Wejście:
- liczba n - oznaczająca ilośc wierzchołków w drzewie,
- n-1 liczb - wskazujące kto jest ojcem danego wierzchołka (wierzchołek 1 nie ma ojca - jest korzeniem)
Wyjście:
- najdłuższa ścieżka w drzewie (dla naszych danych przykładowych wynik wynosi 6)
Dane przykładowe:
12
1 1 1 4 5 6 6 6 7 9 8
Opis algortymu:
Uruchamiamy funkcję DFS (nazwa funkcji to Srednica) z dowolnego wierzchołka (w naszym przypadku rozpoczęliśmy od korzenia - 1) i szukamy punktu, który jest najdalej oddalony od naszego wierzchołka startowego. Dla wszystkich wierzchołków otrzymamy odległość od korzenia. Najdalej oddalone są wierzchołki 10,11,12 (odległość=5). Dowolny z nich posłuży nam jako wierzchołek startowy przy wyszukiwaniu najdłuższej ścieżki.
Zerujemy tablice odwiedzonych i odległości oraz zmienną maxodl.
Następnie ponownie uruchamiamy funkcję Srednica (DFS) - jako wierzochołek startowy podajemy jeden z najdalej oddalonych od korzenia (wierzchołek 10). Algorytm ponownie odwiedzi wszystkie wierzchołki i wywoła rekurencyjnie funkcję Srednica z tych wierzchołków.
Po zakończeniu algorytm zwraca wartość SrednicaDrzewa+1 - jest to średnica naszego drzewa.
Przykładowy algorytm:
-
//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;
-
-
int Srednica(int);
-
-
vector <int> V[100]; //lista sasiedztwa
-
-
int odleglosci[100];
-
bool odwiedzony[100];
-
int maxodl=0,najdalszy;
-
int kandydat;
-
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);
-
V[i].push_back(x);
-
}
-
-
for ( i=1 ; i<=n ; i++ )
-
{
-
cout<<i<<" -> ";
-
for ( j=0 ; j<V[i].size() ; j++ )
-
cout<<V[i][j]<<" ";
-
cout<<endl;
-
}
-
-
-
//wyznaczamy srednice drzewa - najdalej oddalone punkty
-
//szukamy najdalej oddalonego wierzcholka od dowolnego wierzcholka - kandydat (bedzie to jeden z liści)
-
int KandydatOdl=Srednica(1);
-
cout<<"\nmaxodl wierzcholek: "<<kandydat<<" odleglosc: "<<KandydatOdl;
-
-
//zerujemy zmienne przed ponownym uruchomieniem funkcji
-
for (i=0;i<100;i++)
-
{
-
odleglosci[i]=0;
-
odwiedzony[i]=0;
-
}
-
maxodl=0;
-
-
//szukamy najdalej oddalonego wierzcholka od kandydata
-
int SrednicaDrzewa;
-
SrednicaDrzewa=Srednica(kandydat);
-
cout<<"\nSrednica drzewa: "<<SrednicaDrzewa+1;
-
-
}
-
-
-
int Srednica(int x)
-
{
-
odwiedzony[x]=1;
-
for(int k=0 ; k<V[x].size() ; k++)
-
if (!odwiedzony[V[x][k]])
-
{
-
cout<<"\nnr wierzcholka -> "<<V[x][k];
-
odleglosci[V[x][k]]=odleglosci[x]+1;
-
if (odleglosci[V[x][k]]>maxodl)
-
kandydat=V[x][k];
-
maxodl=max(odleglosci[V[x][k]],maxodl);
-
Srednica(V[x][k]);
-
}
-
return maxodl;
-
-
}
Szkic drzewa dla danych z przykładu 2:
- najdluższa ścieżka: 10, 7, 6, 5, 4, 1, 2
- średnica: 7
