Informatyka

Cookies

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++:

 

  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. void DFS(int);
  15.  
  16. vector <int> V[100];  //lista ojcow
  17. int Odl[100];   //tabela odleglosci od korzenia
  18. int Wlk[100];   //wielkość poddrzewa
  19. bool Odw[100];  //tabela odwiedzonych
  20.  
  21. int i,n,x,j;
  22.  
  23. int main()
  24. {
  25.         ios_base::sync_with_stdio(false);
  26.         cin>>n;
  27.  
  28. //umieszczamy dane o wierzcholkach w wektorze  
  29.         for ( i=2 ; i<=n ; i++ )
  30.                 {
  31.                         cin>>x;
  32.                         V[x].push_back(i);
  33.                 }
  34.                
  35.         for ( i=1 ; i<=n ; i++ )       
  36.                 {
  37.                         cout<<i<<" -> ";
  38.                         for ( j=0 ; j<V[i].size() ; j++ )      
  39.                                 cout<<V[i][j]<<" ";
  40.                         cout<<endl;    
  41.                 }
  42.                
  43.         //uruchamiamy funkcję DFS     
  44.         DFS(1);
  45.  
  46. /*** WYNIKI ***/       
  47.         /* Przegląd tablicy odległosci od punktu 1 */
  48.         cout<<endl;    
  49.         for ( i=1 ; i<=n ; i++ )
  50.                 cout << Odl[i] << " ";
  51.                
  52.         /* Przegląd tablicy odwiedzonych */   
  53.         cout<<endl;    
  54.         for ( i=1 ; i<=n ; i++ )
  55.                 cout << Odw[i] << " ";
  56.                
  57.         /* Wielkosc podrzew */ 
  58.         cout<<endl;    
  59.         for ( i=1 ; i<=n ; i++ )
  60.                 cout << Wlk[i] << " ";                         
  61. }
  62.  
  63.  
  64. void DFS(int x)
  65. {
  66.         int w;
  67.         Wlk[x]=1;
  68.         Odw[x]=1;
  69.         for(int k=0 ; k<V[x].size() ; k++)
  70.         {
  71.                 w=V[x][k];
  72.                 if (!Odw[w])
  73.                         {
  74.                                 Odl[w]=Odl[x]+1;
  75.                                 cout<<"\nDFS("<<w<<")";
  76.                                 DFS(w);
  77.                         }      
  78.                 Wlk[x]+=Wlk[V[x][k]];
  79.         }      
  80. }
  81.  
  82.  

Przykładowe drzewo  (dane 2 z powyższego zadania)

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