DFS - matrix + LinkedList

gistfile1.txt

#include <iostream>
#include <vector>
#define FIN "graf.in"
#define FIN2 "graf-liste.in"

using namespace std;

class Graf {

      private:
      vector<vector<int>> matrix;
      vector<bool> visitat;
      int n;//numarul de noduri	

      public:
      //constructorul clasei
      Graf(int n): n(n), matrix(n, vector<int>(n)), visitat(n, false){}

      void citeste() {

      	  for(int i = 0; i < n; ++i) {
      	  	for(int j = 0; j < n; ++j) {
      	  		cin>>matrix[i][j];
      	  	}	
      	  }
      }

      void DFS(int nod) {

           visitat[nod] = true; 

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

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

           	  if(matrix[nod][vecin] == 1 && !visitat[vecin]) {

           	  	  DFS( vecin );

           	  }
           }
      }

      bool esteVizitat(int i) const {

      	  return visitat[ i ];
      }

      int getN() const {
      	  return n;
      }

};

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

class GrafLinkedList {

     private:
     Nod**cap; //cap[i] = primul vecin al nodului i
     //pointer catre pointer
     bool *visitat;
     int n;

     /*
1 2
1 3
2 4
2 5
3 5
4 6
5 6
     */     
     void adaugaMuchie(int u, int v) {

     	  Nod*nou = new Nod( v );//nou = new Nod(3)

     	  nou->urmator = cap[ u ]; //nou->urmator = cap[1]

     	  cap[ u ] = nou;//cap[1] = nou; cap[1]-->2,3
     	  //cap[2] = nou 
     	              //cap[2] -->4,5

     	  //cap[3] -> 5
     	  //cap[4] -> 6
     	  //cap[5] -->6
     }

     public:
     GrafLinkedList(int n): n(n) {

     	  cap = new Nod*[n]();
     	  
     	  visitat = new bool[n]();
     };	

     //destructorul clasei
     ~GrafLinkedList() {


     };

     void citeste() {

     	  int m;
     	  cout<<"Numarul de muchii: ";
     	  cin>>m;

     	  cout<<"Introduceti muchii (u,v) :";
     	  for(int i = 0; i < m; ++i) {
     	  	 int u, v;
     	  	 cin>>u>>v;
     	  	 u--;
     	  	 v--;
     	  	 adaugaMuchie(u, v);
     	  	 adaugaMuchie(v, u);
     	  }
     }

     void DFS(int nod) {

     	  visitat[nod] = true;

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

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

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

     	  	   	   DFS(p->vecin);
     	  	   }
     	  }
     }

     bool esteVizitat(int i) const {

     	  return visitat[ i ]; 
     }

     int getN() const {

     	 return n;
     } 

};

//DFS = Depth First Search
int main(int argc, char const *argv[])
{
	int n;

	freopen(FIN2, "r", stdin);

	cout<<"Numarul de noduri:\n";
	cin>>n;

	GrafLinkedList g(n);

	g.citeste();

	cout<<"Parcurgere DFS: \n";

	for(int i = 0; i < g.getN(); i++) {

		if(!g.esteVizitat(i)) {

			g.DFS( i );
		}	
	}


	cout<<endl;

	return 0;
}

/*
Liste de adiacenta:


fiecare nod are o lista de vecini

0---> 1,2 (lista simpla inlantuita)  Nod*p = cap[0]

1 --->0,3,4 (lista simpla inlantuita) Nod*p = cap[1]

2 ----> 0, 4 (lista simpla inlantuita) Nod*p = cap[2]

3---->1, 5 (lista simpla inlantuita) Nod*p = cap[3]

4 ---> 1, 2, 5 (lista simpla inlantuita) Nod*p = cap[4]

5 ---> 3, 4 (lista simpla inlantuita) Nod*p = cap[5]

*/