Grafo
Publicado por Fabio Curtis Volpe 10/12/2004
[ Hits: 11.643 ]
Esse script é de um grafo que usa fila.
#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); } }
Cálculo de Fatorial usando Loop
Divisores de um inteiro positivo em C++
Nenhum comentário foi encontrado.
Instalar e Configurar o Slackware Linux em 2025
Como configurar os repositórios do apt no Debian 12 em 2025
Passkeys: A Evolução da Autenticação Digital
Instalação de distro Linux em computadores, netbooks, etc, em rede com o Clonezilla
Configurando o Conky para iniciar corretamente no sistema
3 configurações básicas que podem melhorar muito a sua edição pelo editor nano
Como colorir os logs do terminal com ccze
Instalação Microsoft Edge no Linux Mint 22
Como configurar posicionamento e movimento de janelas no Lubuntu (Openbox) com atalhos de teclado
Jogando com Proton no LInux (0)
Ingress NGINX Controller CVSS base score of 9.8 (4)
Impossível corrigir problemas, você manteve (hold) pacotes quebrados. (2)