Informatyka

Cookies

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:

  1. //przykladowe dane 1
  2. //  4     1 2 2   -> 4 wierzcholki | opis wejscia -> kto jest ojcem wierzcholka
  3. //(dla W[1]->brak ojca - nie wystepuje na wejsciu)
  4.        
  5. //przykladowe dane 2
  6. //      12    1 1 1 4 5 6 6 6 7 9 8
  7.  
  8. #include <algorithm>
  9. #include <iomanip>
  10. #include <iostream>
  11. #include <vector>
  12. using namespace std;
  13.  
  14. int Srednica(int);
  15.  
  16. vector <int> V[100];    //lista sasiedztwa
  17.  
  18. int odleglosci[100];
  19. bool odwiedzony[100];
  20. int maxodl=0,najdalszy;
  21. int kandydat;
  22. int i,n,x,j;
  23.  
  24. int main()
  25. {
  26. ios_base::sync_with_stdio(false);
  27. cin>>n;
  28.  
  29. //umieszczamy dane o wierzcholkach w wektorze  
  30.         for ( i=2 ; i<=n ; i++ )
  31.                 {
  32.                         cin>>x;
  33.                         V[x].push_back(i);
  34.                         V[i].push_back(x);
  35.                 }
  36.                
  37.         for ( i=1 ; i<=n ; i++ )       
  38.                 {
  39.                         cout<<i<<" -> ";
  40.                         for ( j=0 ; j<V[i].size() ; j++ )      
  41.                                 cout<<V[i][j]<<" ";
  42.                         cout<<endl;    
  43.                 }
  44.                
  45.        
  46.         //wyznaczamy srednice drzewa - najdalej oddalone punkty
  47.         //szukamy najdalej oddalonego wierzcholka od dowolnego wierzcholka - kandydat (bedzie to jeden z liści)
  48.         int KandydatOdl=Srednica(1);
  49.         cout<<"\nmaxodl wierzcholek: "<<kandydat<<" odleglosc: "<<KandydatOdl;
  50.        
  51.         //zerujemy zmienne przed ponownym uruchomieniem funkcji
  52.         for (i=0;i<100;i++)
  53.                 {
  54.                         odleglosci[i]=0;
  55.                         odwiedzony[i]=0;                       
  56.                 }
  57.         maxodl=0;      
  58.        
  59.         //szukamy najdalej oddalonego wierzcholka od kandydata
  60.         int SrednicaDrzewa;
  61.         SrednicaDrzewa=Srednica(kandydat);
  62.         cout<<"\nSrednica drzewa: "<<SrednicaDrzewa+1;
  63.        
  64. }
  65.  
  66.  
  67. int Srednica(int x)
  68. {
  69.         odwiedzony[x]=1;       
  70.         for(int k=0 ; k<V[x].size() ; k++)     
  71.                 if (!odwiedzony[V[x][k]])
  72.                 {
  73.                         cout<<"\nnr wierzcholka -> "<<V[x][k];
  74.                         odleglosci[V[x][k]]=odleglosci[x]+1;
  75.                         if (odleglosci[V[x][k]]>maxodl)
  76.                                 kandydat=V[x][k];
  77.                         maxodl=max(odleglosci[V[x][k]],maxodl);
  78.                         Srednica(V[x][k]);
  79.                 }
  80.         return maxodl;
  81.        
  82. }

 

Szkic drzewa dla danych z przykładu 2:

  • najdluższa ścieżka: 10, 7, 6, 5, 4, 1, 2
  • średnica: 7

 

1
1
4
4
5
5
6
6
8
8
12
12
7
7
10
10
9
9
11
11
2
2
3
3

 

 

 

 

Poniższy link prowadzi do zbiorów zadań opublikowanegych przez Centralną Komisję Egzaminacyjną. ► zobacz zbiór CKE

 

Informacje o egzaminie maturalnym

Informacje o przebiegu i terminach egzaminu maturalnego ► CKE

 

certyfikat zadowolony konsument

Kontakt

I Liceum Ogólnokształcące im.S.Żeromskiego w Lęborku

84-300 Lębork; ul.Dygasińskiego 14

tel.: (59) 862 12 93

sekretariat(at)lo1.lebork.pl

d  dziennik
p  poczta
f  fanpage