Wstęp do algorytmów

DFS - przeszukiwanie grafu w głąb

DFS (Depth First Search)

Przykład badania spójności grafu nieskierowanego przy pomocy funkcji DFS - z wykorzystaniem stosu.

Poniższy program stanowi realizację zadania omawianego na lekcji.

Zakładamy, że wszystkie wierzchołki w grafię będą numerowane w sposób ciągły (1,2,3...) oraz pierwszy wierzchołek na numer "1".

Zadaniem zmiennej maxW jest zapamiętanie najwyższego numeru wierzchołka (do tej wartości będziemy przegladać tablicę odwiedzonych po wykonaniu funkcji DFS).

 

 

Program w pierwszej kolejności wczytuje dane (opis grafu) w formie opisu krawędzi:

  • n - ilość krawędzi;
  • a b - wiechołki połączone krawędzią.

 

Przykładowe dane

7
1 2
1 3
1 4
2 5
2 6
4 7
7 8

 

 

Na podstwie wczytanego opisu grafu program buduje listę sąsiedztwa (wektor V). W celu sprawdzenia poprawności nasza lista sąsiedztwa jest wypisywana na ekran:

1 -> 2 3 4
2 -> 1 5 6
3 -> 1
4 -> 1 7
5 -> 2
6 -> 2
7 -> 4 8
8 -> 7
 
Po wczytaniu danych (i zbudowaniu listy sąsiedztwa) uruchamiamy funkcję DFS (startujemy z wierzchołka "1"). 
Funkcja DFS oznacza swój wierzchołek jako odwiedzony, następnie umieszcza na stosie wszystkich nieodwiedzonych sąsiadów wierzchołka z którego DFS został wywołany ( dla wierzchołka "1" są to 2,3,4 - patrz lista sąseidztwa: 1 -> 2 3 4 ).
Dopóki na stosie (S) znajdują się numery wierzchołków program wykonuje następujące czynności:
  • pobiera ze stosu numer wiechołka - zapis do zmiennej "w",
  • usuwa ze stosu wierzochołek,
  • uruchamia funkcję DFS z parametrem "w".

Kiedy stos (S) zostanie opróżniony przeglądamy listę odwiedzonych. Jeżeli dla wszystkich wiechołków otrzymaliśmy wynik pozytywny wypisujemy komunikat informujący, że badany graf jest spójny.

 

 

DFS
  1. #include<iostream>
  2. #include<stack>
  3. #include<vector>
  4. using namespace std;
  5.  
  6. void DFS(int);
  7.  
  8. vector <int> V[20];
  9. stack <int> S;
  10. bool odw[100];
  11. int maxW=0; //max numer wierzcholka
  12.  
  13. int main()
  14. {
  15.         int n,a,b;
  16.         cin>>n;
  17.         //wczytujemy dane - budujemy liste sasiedztwa
  18.         for (int i=0;i<n;i++)
  19.                 {
  20.                         cin>>a>>b;
  21.                         maxW=max(maxW,a);
  22.                         maxW=max(maxW,b);
  23.                         V[a].push_back(b); V[b].push_back(a);
  24.                 }
  25.         //sprawdzenie listy sasiedztwa - max 20 wierzcholkow           
  26.         cout<<"\nLista sasiedztwa";
  27.         for (int i=1 ; i<=maxW ; i++)
  28.                 {
  29.                 cout<<"\n"<<i<<" -> ";
  30.                 for (int j=0 ; j<V[i].size() ; j++)
  31.                         cout<<V[i][j]<<" ";                    
  32.                 }
  33.                
  34.         //badanie spojnosci grafu
  35.         DFS(1);
  36.         bool spojny=true;
  37.         for (int i=1 ; i<=maxW ; i++)          
  38.                 if (!odw[i]) spojny=false;
  39.        
  40.         if (spojny)    
  41.                 cout<<"\nTen graf jest spojny";
  42.         else
  43.                 cout<<"\nTen graf nie jest spojny";    
  44.                
  45. }
  46.  
  47. void DFS(int k)
  48. {
  49.         int x,w;
  50.         odw[k]=true;
  51.         for ( int i=0 ; i<V[k].size() ; i++ )
  52.         {
  53.                 x=V[k][i];
  54.                 if (!odw[x])   
  55.                         S.push(x);                     
  56.         }
  57.         if (!S.empty())
  58.                 {
  59.                         w=S.top();     
  60.                         S.pop();
  61.                         DFS(w);
  62.                 }
  63. }
  64.  
  65.