06/11/19- estrutura de dados 2

grafos/graphs
vértice/vertix
edge/aresta
+= "ou"

d(G)=|V|+|E|
se tiver muito vértice com pouca conexões, V domina
se tiver muitas arestas com poucos pontos para ligar, E domina

2*|E| -> pois todo E teria 2 extremos, logicamente


2 tipos de implementação de grafos

1: matriz de adjacência
    bom se tiverem muitas conexões
    bom se as conexões forem todas na 2 direções-> só precisa guardar metade dos espaçoes
    bom para pesquisar se o vértice A tem conexão com o vértice B
    ruim se precisar saber todas as conexões do vértice A: precisa passar por toda a tabela


2: lista encadeada
    bom se tiverem pouca conexões
    bom se as conexões forem unidirecionais
    bom para listar todas as conexões de A
    ruim para procurar se A é ligado a B -> precisa passar por toda a lista encadeada


#include <stdio.h>
#include <stdlib.h>

/*Estrutura para um nó em uma lista encadeada: */
typedef struct noA {
   int id;          /*Identificador armazenado no nó. */
   struct noA *next; /* Próximo nó na lista encadeada. */
} NoA;

/*Estrutura de Grafo com lista de adjacências: */
typedef struct grafoA {
   int E; /* Quantidade de arestas. */
   int V; /* Quantidade de vértices. */
   NoA **Adj; /* Lista de adjacências. */
} GrafoA;

/*Estrutura de Grafo com matriz de adjacências: */
typedef struct grafoM {
   int E; /* Quantidade de arestas. */
   int V; /* Quantidade de vértices. */
   int **Mat; /* Matrix de adjacências. */
} GrafoM;

/*Função para criar um grafo com lista de adjacências.*/
GrafoA* criar_grafo_adj (int tamanho) {
   int v;
   GrafoA *G = (GrafoA *)malloc(sizeof(GrafoA));
   G->E = 0;
   G->V = tamanho;
   G->Adj = (NoA **)malloc(tamanho * sizeof(NoA *));
   for (v = 0; v < G->V; v++) {
      G->Adj[v] = NULL;
   }
   return G;
}

/*Função para criar um grafo com matriz de adjacências.*/
GrafoM* criar_grafo_mat (int tamanho)
{
   int v;
   GrafoM *G = (GrafoM *)malloc(sizeof(GrafoM));
   G->E = 0;
   G->V = tamanho;
   G->Mat = (int **)malloc(tamanho * sizeof(int *));
   for (v = 0; v < G->V; v++)
   {
      G->Mat[v] = (int *)malloc(tamanho * sizeof(int));
   }
   return G;
}

/*Função para destruir um grafo construído com lista de adjacências.*/
void liberar_grafo_adj (GrafoA *G)
{
   int v;
   for (v = 0; v < G->V; v++)
   {
      if (G->Adj[v] != NULL)
      {
         free(G->Adj[v]);
      }
   }
   free(G->Adj);
   free(G);
}

/*Função para destruir um grafo construído com lista de adjacências.*/
void liberar_grafo_mat (GrafoM *G)
{
   int v;
   for (v = 0; v < G->V; v++)
   {
      if (G->Mat[v] != NULL)
      {
         free(G->Mat[v]);
      }
   }
   free(G->Mat);
   free(G);
}

void zera_grafo_mat (GrafoM *G)
{
   int v;
   for (v = 0; v < G->V; v++)
   {
      if (G->Mat[v] == NULL)
      {
         G->Mat[v]=0;
      }
   }
}

void insere_valor_grafo_mat (GrafoM *G, int x, int y, int valor)
{
   G->Mat[]=valor;
}




/* */
int main () {

   int Va = 10; /*Número de vértices*/

   GrafoA* Ga = criar_grafo_adj (Va);

   int Vm = 10; /*Número de vértices*/

   GrafoM* Gm = criar_grafo_mat (Vm);

   liberar_grafo_adj (Ga);
   liberar_grafo_mat (Gm);

   return 0;
}