IcaroPeretti

GrafoDirecionado

Dec 2nd, 2020
449
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <list>
  3. #include <algorithm>
  4.  
  5. /*
  6.     Algoritmo para representação de grafos direcionados (digrafos)
  7. */
  8.  
  9. using namespace std;
  10.  
  11. class Grafo
  12. {
  13.     int v; //Numero de vertices
  14.     list<int> *adj; //Ponteiro para um array contendo as listas de adjacencias
  15.    
  16.     public:
  17.         Grafo(int v); //Construtor
  18.         void adicionarAresta(int v1,int v2); //Adiciona aresta no grafo, conecta v1 com v2
  19.        
  20.         //Obtem o grau de saida de um vertice (nodo)
  21.         //numero de arestas que saem de V
  22.         int obterGrauSaida(int v);
  23.        
  24.         //Verifica se um vertice é vizinho de outro
  25.         bool existeVizinho(int v1,int v2); //Verifica se v2 é vizinho de v1
  26. };
  27.  
  28. Grafo::Grafo(int v)
  29. {
  30.     this->v = v; //atribui o numero de vertices
  31.     adj = new list<int>[v]; //Cria as listas, cada vértice possui uma lista
  32. }
  33.  
  34. void Grafo::adicionarAresta(int v1,int v2)
  35. {
  36.     //adicionar vertice v2 a lista de vertices adjacentes de v1
  37.     adj[v1].push_back(v2);
  38. }
  39.  
  40. int Grafo::obterGrauSaida(int v)
  41. {
  42.     //Basta retornar o tamanho da lista que e a quantidade de vizinhos
  43.     return adj[v].size();
  44. }
  45.  
  46. bool Grafo::existeVizinho(int v1,int v2)
  47. {
  48.     if(find(adj[v1].begin(),adj[v1].end(),v2) != adj[v1].end())
  49.     {
  50.         return true;
  51.     }
  52.     return false;
  53. }
  54.  
  55.  
  56.  
  57. int main()
  58. {
  59.     //Cria um grafo com 4 vertices
  60.     Grafo grafo(4);
  61.    
  62.     grafo.adicionarAresta(0,1);
  63.     grafo.adicionarAresta(0,3);
  64.     grafo.adicionarAresta(1,2);
  65.     grafo.adicionarAresta(3,1);
  66.     grafo.adicionarAresta(3,2);
  67.    
  68.     cout << "Grau de saida do vertice 1: " << grafo.obterGrauSaida(1);
  69.     cout << "\nGrau de saida do vertice 3: " << grafo.obterGrauSaida(3);
  70.     cout << "\nGrau de saida do vertice 0: " << grafo.obterGrauSaida(0);
  71.    
  72.     //Verifica se existe vizinho
  73.     if(grafo.existeVizinho(0,1))
  74.     {
  75.         cout << "\n1 e vizinho de 0\n";
  76.     }
  77.     else
  78.     {
  79.         cout << "1 nao e vizinho de 0";
  80.     }
  81.  
  82.     if(grafo.existeVizinho(1,0))
  83.     {
  84.         cout << "\n0 e vizinho de 1\n";
  85.     }
  86.     else
  87.     {
  88.         cout << "0 nao e vizinho de 1\n";
  89.     }
  90.  
  91.    
  92.     if(grafo.existeVizinho(2,0))
  93.     {
  94.         cout << "\n2 e vizinho de 0\n";
  95.     }
  96.     else
  97.     {
  98.         cout << "2 nao e vizinho de 0\n";
  99.     }
  100.  
  101.  
  102.     return 0;
  103. }
  104.  
RAW Paste Data