Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <stack>
- #include <queue>
- using namespace std;
- void aggiungiArco ( vector <vector <int>> &grafo, int u, int v );
- void BFS ( vector <vector <int>> &grafo, int sorgente );
- void DFS ( vector <vector <int>> &grafo, int sorgente );
- /**
- Input di esempio:
- 8 8
- 0 1
- 0 2
- 1 2
- 1 3
- 2 3
- 2 5
- 3 4
- 7 6
- */
- int main( void )
- {
- int numeroVertici, numeroArchi;
- cin >> numeroVertici >> numeroArchi;
- vector <vector <int>> grafo ( numeroVertici );
- /// Lettura grafo
- for ( int i = 0; i < numeroArchi; i++ ) {
- int u, v;
- cin >> u >> v;
- aggiungiArco( grafo, u, v );
- }
- cout << "BFS: " << endl;
- BFS ( grafo, 0 );
- cout << endl << "DFS: " << endl;
- DFS ( grafo, 0 );
- return 0;
- }
- void aggiungiArco ( vector <vector <int>> &grafo, int u, int v ) {
- grafo [ u ].push_back ( v );
- }
- void BFS ( vector <vector <int>> &grafo, int sorgente ) {
- /// Array di visitati a false
- vector <bool> visitato ( grafo.size(), false );
- /// Definisco la frangia come coda
- queue <int> frangia;
- /// Visito il nodo sorgente
- frangia.push ( sorgente );
- visitato[ sorgente ] = true;
- while ( !frangia.empty() ) {
- int corrente = frangia.front();
- frangia.pop();
- cout << corrente << " ";
- /// Per ognuno dei vicini del nodo corrente
- for ( int &vicino : grafo [ corrente ] ) {
- /// Se non sono stati visitati
- if ( ! visitato [ vicino ] ) {
- /// Li aggiungo alla frangia ( nodi da scorrere )
- frangia.push( vicino );
- /// Li marco come visitati
- visitato[ vicino ] = true;
- }
- }
- }
- }
- void DFS ( vector <vector <int>> &grafo, int sorgente ) {
- /// Array di visitati a false
- vector <bool> visitato ( grafo.size(), false );
- /// Definisco la frangia come coda
- stack <int> frangia;
- /// Visito il nodo sorgente
- frangia.push ( sorgente );
- visitato[ sorgente ] = true;
- while ( !frangia.empty() ) {
- int corrente = frangia.top();
- frangia.pop();
- cout << corrente << " ";
- /// Per ognuno dei vicini del nodo corrente
- for ( int &vicino : grafo [ corrente ] ) {
- /// Se non sono stati visitati
- if ( ! visitato [ vicino ] ) {
- /// Li aggiungo alla frangia ( nodi da scorrere )
- frangia.push( vicino );
- /// Li marco come visitati
- visitato[ vicino ] = true;
- }
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement