Olá, boa tarde! Estudo Sistemas de Informação e estou com alguns problemas na matéria de Grafos e Algoritmos Computacionais. Preciso desenvolver um tipo abstrato de dados grafo com todas as suas operações. Até agora na…

Você pretende implementar em java ou c?

Tenho que fazer em Java ou C#. Mas tenho preferência pelo Java. Mas muito obrigado desde já!

Algoritmos de Grafos

Este código foi escrito em c. Sei que está faltando comentários detalhados, mas acredito que lhe seja útil pelo menos pra ter uma noção então.
O objetivo era através de arquivo de texto capturar os valores e montar o grafo a partir deste.

#define MAXNUMVERTICES 100
#define MAXNUMARESTAS 4500
  
  typedef int TipoValorVertice;
  typedef int TipoApontador;
  typedef float TipoPeso;
  
  typedef struct TipoGrafo {
          TipoPeso Mat[MAXNUMVERTICES + 1] [MAXNUMVERTICES + 1] ;
          int NumVertices;
          int NumArestas;
  } TipoGrafo;

 
void FGVazio(TipoGrafo *Grafo)
     { 
         short i , j ;
         for ( i = 0; i <= Grafo->NumVertices; i++)
       { for ( j = 0; j <=Grafo->NumVertices; j ++) Grafo->Mat[ i ] [ j ] = 0; }
     }
 
void InsereAresta(TipoValorVertice *V1, TipoValorVertice *V2,
   TipoPeso *Peso, TipoGrafo *Grafo)
  { 
    Grafo->Mat[*V1] [*V2] = *Peso;     
  }
  
short ExisteAresta(TipoValorVertice Vertice1 ,
    TipoValorVertice Vertice2 , TipoGrafo *Grafo)
  { 
    return (Grafo->Mat[Vertice1 ] [ Vertice2] > 0);
  }   
  

/* Operadores para obter a lista de adjacentes */
short ListaAdjVazia(TipoValorVertice *Vertice , TipoGrafo *Grafo)
{ 
  
  
  TipoApontador Aux = 0;
  short ListaVazia = 1;
  while (Aux < Grafo->NumVertices && ListaVazia)
  if (Grafo->Mat[*Vertice] [Aux] > 0) ListaVazia = 0;
  else Aux++;
  return ( ListaVazia == 0) ;
}

/* Operadores para obter a lista de adjacentes */
TipoApontador PrimeiroListaAdj (TipoValorVertice *Vertice , TipoGrafo *Grafo)
{ 
  TipoValorVertice Result ;
  TipoApontador Aux = 0;
  short ListaVazia = 1;
  while (Aux < Grafo->NumVertices && ListaVazia)
  { 
    if (Grafo->Mat[*Vertice ] [Aux] > 0) { Result = Aux; ListaVazia = 0; }
    else Aux++;
  }
  if (Aux == Grafo->NumVertices){
          // printf ( "Erro : Lista adjacencia vazia (PrimeiroListaAdj ) \n" ) ;
     }
  return Result ;
}

void RetiraAresta(TipoValorVertice *V1, TipoValorVertice *V2,
   TipoPeso *Peso, TipoGrafo *Grafo)
   { 
     if (Grafo->Mat[*V1] [*V2] == 0) printf ( "Aresta nao existe \n" ) ;
     else { *Peso = Grafo->Mat[*V1] [*V2] ; Grafo->Mat[*V1] [*V2] = 0; }
}

void LiberaGrafo(TipoGrafo *Grafo)
{ /* Nao faz nada no caso de matrizes de adjacencia */ }

void ImprimeGrafo(TipoGrafo *Grafo)
{ short i , j; printf( " " ); 
  
  for ( i = 1; i <= Grafo->NumVertices; i ++) printf ( "  %3d" , i ) ;
  printf (" \n") ;
  for ( i = 1; i <= Grafo->NumVertices; i++)
    {
      printf ("%3d" , i ) ;
      for ( j = 1; j <=Grafo->NumVertices; j++)
         printf ( "%5.1f" , Grafo->Mat[ i ] [ j ] ) ;
         printf ( " \n" ) ;
    }
}


/* Operadores para obter a lista de adjacentes */
void ProxAdj(TipoValorVertice *Vertice , TipoGrafo *Grafo,
                              TipoValorVertice *Adj , TipoPeso *Peso,
                                               TipoApontador *Prox, short *FimListaAdj)
{ /* Retorna Adj apontado por Prox */
   *Adj = *Prox;
   *Peso = Grafo->Mat[*Vertice ] [*Prox] ;
   (*Prox)++;
   while (*Prox < Grafo->NumVertices &&
         Grafo->Mat[*Vertice ] [*Prox] == 0) (*Prox)++;
         if (*Prox == Grafo->NumVertices) *FimListaAdj = 1;
}


// Pega grafo em disco
void carregaDeArquivo(TipoGrafo *grafo) {
  
  FILE *arq = fopen("grafo_exemplo.txt", "r");
  int numVertices, numArestas;

  // testa se o arquivo foi aberto com sucesso
  if(arq != NULL){
    printf("Arquivo foi aberto com sucesso. \n");    
    fscanf(arq,"%d ", &numVertices);        
    fscanf(arq,"%d ", &numArestas);
    
    //printf("%d, %d \n",numVertices, numArestas);  
 
    grafo->NumVertices = numVertices;
    grafo->NumArestas = numArestas;
    
    TipoValorVertice ori, dest;
    TipoPeso peso;
    while (!feof(arq))
 	{
  		fscanf(arq,"%d ", &ori);        
        fscanf(arq,"%f ", &peso);
        fscanf(arq,"%d ", &dest);
  		InsereAresta(&ori, &dest, &peso, grafo);  		
        printf("%d %5.2f %d \n", ori, peso, dest);

  	} 
  }    
  else{
    printf("Nao foi possivel abrir o arquivo."); 
    system("PAUSE");
    exit(1);   
  }  
    
    
}

  
int main(int argc, char *argv[])
{
 // cria o tipo grafo
 TipoGrafo grafo;
 
 // faz a matriz de adjacência ficar zerada
 FGVazio(&grafo);
  
 // carrega o grafo do arquivo *.txt
 carregaDeArquivo(&grafo);
 
 // Exibe o grafo obtido   
 ImprimeGrafo(&grafo);
  
 
  system("PAUSE");	
  return 0;
}

3 Respostas

Topicos relacionados