Programowanie c++

Badanie spójności grafu - graf nieskierowany DFS

Kategoria: Informatyka - strona ogólna kategorii / programowanie c++
Sprawdzenie spójności grafu nieskierownego. 
 
 
Przykładowe dane:
8 12
0 2 0 4
1 3 1 5
2 3 
3 5 
4 5 4 7 4 6
5 6 
6 2
7 3
 
odp: TAK

 

 

Wygląd grafu dla powyższych danych przykładowych
Wygląd grafu dla powyższych danych przykładowych

 

 

  1. //SPRAWDZENIE SPOJNOSCI GRAFU
  2. //rozwiazanie dla grafu nieskierowanego
  3. #include <iostream>
  4. #include <stack>
  5. #include <vector>
  6. using namespace std;
  7.  
  8. bool visited[10000];   //deklarujemy tablice odwiedzin -> zaznaczamy wszystkie wierzcholki jako nieodwiedzone
  9. vector <int> V[10000];
  10.  
  11. int main()
  12. {
  13.   int n,m,i,v1,v2;
  14.   bool spojny;
  15.   stack<int>S;
  16.  
  17.   cin >> n >> m;  //wczytujemy  n-ilosc wierzolkow  m-ilosc krawedzi
  18.  
  19.   // Wczytujemy m krawędzi i umieszczamy w wektorach
  20.   for(i = 0; i < m; i++)
  21.   {
  22.     cin >> v1 >> v2;     // Odczytujemy krawędź od v1 do v2
  23.     V[v1].push_back(v2); // Do wektora A[v1] dodajemy wierzchołek v2
  24.     V[v2].push_back(v1); // Do wektora A[v2] dodajemy wierzchołek v1
  25.   }
  26.  
  27. // POMOCNICZE wypisujemy liste wierzcholkow - sprawdzamy poprawnosc wczytania danych ->START
  28. for(i = 0; i < n; i++)
  29. {
  30. cout<<"\n"<<i<<" -> ";
  31.     for(int j = 0 ; j < V[i].size() ; j++)
  32.      cout << V[i][j]<<", ";
  33. }
  34. // POMOCNICZE wypisujemy liste wierzcholkow - sprawdzamy poprawnosc wczytania danych ->KONIEC
  35.  
  36. cout << "\n";
  37.  
  38. // Za pomoca DFS przechodzimy graf od wierzcholka startowego
  39.   S.push(0);    // Na stos wierzchołek startowy: 0
  40.   while(!S.empty())
  41.   {
  42.     v1 = S.top();            // Pobieramy wierzchołek ze szczytu stosu
  43. S.pop();                       // Usuwamy pobrany wierzchołek ze szczytu stosu
  44.     if(!visited[v1])           // Sprawdzamy, czy wierzchołek był odwiedzony
  45.     { // jezeli nie to ˇ
  46.         visited[v1] = true;       // Odwiedzamy go i na stosie umieszczamy sasiadow
  47.         for(int i=0 ; i < V[v1].size() ; i++)   //V[v1].size() - ilosc wierzcholkow na liscie wektora v1
  48.    if(!visited[V[v1][i]])
  49.      {
  50.         S.push(V[v1][i]);
  51.      }
  52.     }
  53.   }
  54.  
  55.   //przegladamy zawartosc tablicy visited 1-odwiedzony 0-nieodwiedzony !! POMOCNICZE !!
  56.   for(i = 0; i < n; i++)  //!! POMOCNICZE !!
  57.     cout<<visited[i]<<", ";  //!! POMOCNICZE !!
  58.  
  59.   // Sprawdzamy, czy DFS odwiedzil wszystkie wierzcholki
  60.   spojny = true;
  61.   for(i = 0; i < n; i++)
  62.       if(!visited[i])
  63.         {
  64.             spojny = false; break;                
  65.         }
  66.  
  67.   cout << endl;
  68.   // W zalezności od stanu zmiennej spojny wypisujemy odpowiedni komunikat
  69.   if(spojny) cout << "Tak"; else cout << "Nie";
  70. }
 
 
Zobacz działanie powyższego kodu w kompilatorze online >>>. (dane przykładowe zostały umieszczone w zakładce STDIN)