Parcurgere in latime , matricea este stocata in liste de adiacenta

BFS-LinkedListAdj.cpp

#include <iostream>
#include <queue>

using namespace std;

struct Node {

  int vecin;
  Node*urmator;
  Node(int vecin): vecin(vecin), urmator(nullptr) {}
};

class GrafLinkedList {

      private:

      Node**cap;//pointer catre pointer ;
      bool*vizitat; //
      int n; //numarul de  noduri


      void adaugaMuchie(int u, int v) {
           Node *nou = new Node( v );
           nou->urmator = cap[u];
           cap[u] = nou;
      }

      public:

      GrafLinkedList( int n ): n( n ) {
          cap = new Node*[n]();
          vizitat = new bool[n]();
      }

      //destructorul clasei care dezaloca spatiul din HEAP
      ~GrafLinkedList() {
           for(int i = 0; i < n; ++i) {

               Node* p = cap[i];

               while(p) {

                 Node*tmp = p;
                 p = p->urmator;
                 delete tmp;
               }
           }

           delete[] cap;
           delete[] vizitat;
      }

      void citeste() {

           int m;

           cout<<"Numarul de muchii: ";
           cin>>m;
           cout<<"muchiile-->>"<<m<<"<---";

           cout<<"Introduceti muchiile (u,v) nodurile de la 1 la "<<n<<endl;

           for(int i = 0; i < m; ++i) {
               int u, v;
               cin>>u>>v;
               cout<<u<<" "<<v<<endl;
               u--;
               v--;
               adaugaMuchie(u, v); //(1,2)
               adaugaMuchie(v, u);//(2,1)
           }

      }

      void BFS(int start) {

           queue<int> coada;//declaram o coada

           coada.push(start);//adaugam in coada

           vizitat[ start ] = true; //marcam ca fiind cizitat

           //cat timp coada nu este vida
           while(!coada.empty()) {

              int node = coada.front();

              coada.pop();

              cout<<(node+1)<<" ";

              for(Node* p = cap[node]; p != nullptr; p=p->urmator) {

                        if(!vizitat[p->vecin]) {

                            vizitat[p->vecin] = true;

                            coada.push(p->vecin);

                        }
              }
           }
      }


      bool esteVizitat(int i) {return vizitat[i];}

      int getN() {return n;}


};

int main(int argc, char const *argv[]) {

  freopen("graf-muchii.in", "r", stdin);

  int n;

  cout<<"Numarul de noduri:";

  cin>>n;

  GrafLinkedList g(n);

  g.citeste();

  cout<<"Parcurgere BFS (graful este reprezentat prin Liste de adiacenta): ";

  for(int i = 0; i < n; ++i) {

      if(!g.esteVizitat(i)) {
         g.BFS(i);
      }
  }

  cout<<endl;

  return 0;
}

/*
Input:

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

*/

/*
1: 2,3 p[1]
2: 3
3: 1, 2
*/