Advertisement
informaticage

Graph visits

Feb 14th, 2020
376
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.65 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <stack>
  4. #include <queue>
  5.  
  6. using namespace std;
  7.  
  8. void aggiungiArco ( vector <vector <int>> &grafo, int u, int v );
  9. void BFS ( vector <vector <int>> &grafo, int sorgente );
  10. void DFS ( vector <vector <int>> &grafo, int sorgente );
  11.  
  12. /**
  13.     Input di esempio:
  14.     8 8
  15.     0 1
  16.     0 2
  17.     1 2
  18.     1 3
  19.     2 3
  20.     2 5
  21.     3 4
  22.     7 6
  23. */
  24.  
  25. int main( void )
  26. {
  27.     int numeroVertici, numeroArchi;
  28.     cin >> numeroVertici >> numeroArchi;
  29.  
  30.     vector <vector <int>> grafo ( numeroVertici );
  31.  
  32.     /// Lettura grafo
  33.     for ( int i = 0; i < numeroArchi; i++ ) {
  34.         int u, v;
  35.         cin >> u >> v;
  36.         aggiungiArco( grafo, u, v );
  37.     }
  38.  
  39.     cout << "BFS: " << endl;
  40.     BFS ( grafo, 0 );
  41.  
  42.     cout << endl << "DFS: " << endl;
  43.     DFS ( grafo, 0 );
  44.     return 0;
  45. }
  46.  
  47. void aggiungiArco ( vector <vector <int>> &grafo, int u, int v ) {
  48.     grafo [ u ].push_back ( v );
  49. }
  50.  
  51. void BFS ( vector <vector <int>> &grafo, int sorgente ) {
  52.     /// Array di visitati a false
  53.     vector <bool> visitato ( grafo.size(), false );
  54.  
  55.     /// Definisco la frangia come coda
  56.     queue <int> frangia;
  57.  
  58.     /// Visito il nodo sorgente
  59.     frangia.push ( sorgente );
  60.     visitato[ sorgente ] = true;
  61.  
  62.     while ( !frangia.empty() ) {
  63.         int corrente = frangia.front();
  64.         frangia.pop();
  65.         cout << corrente << " ";
  66.  
  67.         /// Per ognuno dei vicini del nodo corrente
  68.         for ( int &vicino : grafo [ corrente ] ) {
  69.             /// Se non sono stati visitati
  70.             if ( ! visitato [ vicino ] ) {
  71.                 /// Li aggiungo alla frangia ( nodi da scorrere )
  72.                 frangia.push( vicino );
  73.                 /// Li marco come visitati
  74.                 visitato[ vicino ] = true;
  75.             }
  76.         }
  77.     }
  78. }
  79.  
  80. void DFS ( vector <vector <int>> &grafo, int sorgente ) {
  81.     /// Array di visitati a false
  82.     vector <bool> visitato ( grafo.size(), false );
  83.  
  84.     /// Definisco la frangia come coda
  85.     stack <int> frangia;
  86.  
  87.     /// Visito il nodo sorgente
  88.     frangia.push ( sorgente );
  89.     visitato[ sorgente ] = true;
  90.  
  91.     while ( !frangia.empty() ) {
  92.         int corrente = frangia.top();
  93.         frangia.pop();
  94.         cout << corrente << " ";
  95.  
  96.         /// Per ognuno dei vicini del nodo corrente
  97.         for ( int &vicino : grafo [ corrente ] ) {
  98.             /// Se non sono stati visitati
  99.             if ( ! visitato [ vicino ] ) {
  100.                 /// Li aggiungo alla frangia ( nodi da scorrere )
  101.                 frangia.push( vicino );
  102.                 /// Li marco come visitati
  103.                 visitato[ vicino ] = true;
  104.             }
  105.         }
  106.     }
  107. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement