Grafo
Publicado por Fabio Curtis Volpe 10/12/2004
[ Hits: 11.618 ]
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
Teoria do Caos - (Equação Logística)
Nenhum comentário foi encontrado.
Passkeys: A Evolução da Autenticação Digital
Instalação de distro Linux em computadores, netbooks, etc, em rede com o Clonezilla
Título: Descobrindo o IP externo da VPN no Linux
Armazenando a senha de sua carteira Bitcoin de forma segura no Linux
Enviar mensagem ao usuário trabalhando com as opções do php.ini
Instalando Brave Browser no Linux Mint 22
vídeo pra quem quer saber como funciona Proteção de Memória:
Encontre seus arquivos facilmente com o Drill
Mouse Logitech MX Ergo Advanced Wireless Trackball no Linux
Compartilhamento de Rede com samba em modo Público/Anônimo de forma simples, rápido e fácil
Como abrir o pycharm no linux (2)
VMs e Interfaces de Rede desapareceram (12)