Grafo
Publicado por Fabio Curtis Volpe 10/12/2004
[ Hits: 11.756 ]
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); } }
Divisores de um inteiro positivo em C++
Nenhum coment�rio foi encontrado.
Servidor de Backup com Ubuntu Server 24.04 LTS, RAID e Duplicati (Dell PowerEdge T420)
Visualizar câmeras IP ONVIF no Linux sem necessidade de instalar aplicativos
Atualizar Debian Online de uma Versão para outra
Instalar driver Nvidia no Debian 13
Redimensionando, espelhando, convertendo e rotacionando imagens com script
Debian 13 Trixie para Iniciantes
Convertendo pacotes DEB que usam ZSTD (Padrão Novo) para XZ (Padrão Antigo)