Esse script é de um grafo que usa fila.

• Download Grafo.c
• Enviar nova versão

Esconder código-fonte

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

#define MAX 10
#define TAMANHO_NOME 30

#define SAO_PAULO 0
#define NOVA_YORK 1
#define LOS_ANGELES 2
#define LONDRES 3
#define FRANKFURT 4
#define TOKIO 5
#define SYDNEY 6

//globais
int GrafoCidades[MAX][MAX]; //grafo
int CorCidades[MAX];  //cidades acessadas
char NomeCidades[MAX][TAMANHO_NOME]; //nome das cidades

int inicio=0; //inicio fila
int tamanho; //fila para o modulo
int fila[500]; //tamanho fila (bem maior para caber as combinacoes)

//prototipos
void CaminhoNoGrafo(int cidadeInicio); //grafo
void inserirFILA(int x);    //insere na fila ( fila circular )
int removerFILA();   //remove (fila circular)

//----------------------------------------------------------------------------
int main()
{
     
   int i,j;
   
   //inicia grafo com tudo -1
   for (i=0; i< MAX; i++)
   {
       for (j=0; j< MAX; j++)
       {
          GrafoCidades[i][j]= -1;
       }
   }

   //monta o grafo
   GrafoCidades[SAO_PAULO][NOVA_YORK]= 350;
   GrafoCidades[SAO_PAULO][LONDRES]= 400;
   GrafoCidades[NOVA_YORK][LOS_ANGELES]= 150;
   //GrafoCidades[NOVA_YORK][FRANKFURT]= 250;
   //GrafoCidades[NOVA_YORK][LONDRES]= 120;
   GrafoCidades[LONDRES][FRANKFURT]= 80;
   //GrafoCidades[LONDRES][SYDNEY]= 500;
   //GrafoCidades[LONDRES][SAO_PAULO]= 400;
   GrafoCidades[LONDRES][NOVA_YORK]= 120;
   GrafoCidades[FRANKFURT][TOKIO]= 500;
   GrafoCidades[LOS_ANGELES][TOKIO]= 400;
   //GrafoCidades[LOS_ANGELES][SYDNEY]= 450;
   GrafoCidades[TOKIO][SYDNEY]= 300;
   GrafoCidades[SYDNEY][TOKIO]= 500;
   
   //monta os nomes das cidades
   strcpy(NomeCidades[0],"Sao Paulo-GRU");
   strcpy(NomeCidades[1],"Nova York-JFK");
   strcpy(NomeCidades[2],"Los Angeles");
   strcpy(NomeCidades[3],"Londres-LHR");
   strcpy(NomeCidades[4],"Frankfurt");
   strcpy(NomeCidades[5],"Tokio");
   strcpy(NomeCidades[6],"Sydney");
   
   
   //imprimi todas as cidades na tela com o numero dela
   printf("Grafo gerado com as cidades :\n");
   for (i=0; i < MAX; i++)
   {
       printf("%i : %s\n", i, NomeCidades[i]);
   }

   printf("\n\nTodas as cidades possiveis apartir de : %s\n",NomeCidades[LONDRES]);
   //calcula o caminho no grafo
   CaminhoNoGrafo(LONDRES);
   
   
   
   getchar();
}

//--------------------------------------------------------------------------
void CaminhoNoGrafo(int cidadeInicio)
{

   int i,j;
   int cidadeBase,retFILA;

   //inicia todas as cidades com a cor branca (nao visitada)
   for (i=0; i< MAX; i++)
   {
        CorCidades[i]= 0;
   }



    cidadeBase= cidadeInicio; //cidade inicial vai para cidadebase para calcular as ligacoes
    
    while (cidadeBase != -1)
    {
       // Marcar cidadeBase com a cor preta (ja visitada)
       CorCidades[cidadeBase]= 2;


       for (j=0; j<MAX; j++)
       {
           //se tiver ligacao, coloca na fila
           if ( (GrafoCidades[cidadeBase][j] != -1) && (CorCidades[j]==0) )
           {
                  inserirFILA(j);
                  CorCidades[j]==2;//cor preta (ja visitada)
           }
       } //for

       
       // retira da fila uma cidade base (passa para a proxima cidade com ligacao)
       cidadeBase=removerFILA();

    } //while

       for (i=0; i< MAX; i++)
       {
              if (CorCidades[i]==2)
              {
                   printf("\n%s ",NomeCidades[i]);
              }
       }  // for


}  // RotaMaisBarata

//----------------------------------------------------------------------------
void inserirFILA(int x)
{
    
    
    if ( tamanho == MAX )     //se tamanho da fila for = ao MAXimo da fila ,  fila cheia
    {
        printf("\nFila esta cheia\n");
    }
    else
    {
        fila[ (inicio + tamanho) % MAX] = x;    //(inicio + tamanho) % MAX eh a posicao do proximo elemento
        tamanho++;         //incrementa o tamanho pq foi inserido mais um elemento
    }
    
    
}

//----------------------------------------------------------------------------
int removerFILA()
{
    int aux;

    
    if(tamanho!=0)        //tamanho !0 = a fila nao vazia
    {
        aux=fila[inicio]; //quarda em aux o valor antes de removerFILA ele da fila
        fila[inicio]=-1;  //zera o valor da fila
        
        inicio++;         //incrementa o inicio para localizar o proximo com o modulo
        inicio = inicio % MAX; //localiza o proximo elemento com o modulo
        tamanho--;        //decrementa o tamanho pq removeu o elemento da fila

        return(aux);      //retorna o valor removido
        
    }
    else
    {
        
        // tamanho da fila = 0 , fila vazia
        return(-1); 
        
    }    
 }

Boletim Escolar Com Manipulação de Arquivo

Lista encadeada em C

Um algoritmo genético para o TSP (Travel Salesman Problem)

Torres de Hanoi

Listas Encadeadas

Nenhum coment�rio foi encontrado.