Grafo
Publicado por Fabio Curtis Volpe 10/12/2004
[ Hits: 11.444 ]
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); } }
SIMULADOR DE DADOS DE RPG VAMPIRO A MÁSCARA - Corrigido
Nenhum comentário foi encontrado.
Melhorando o tempo de boot do Fedora e outras distribuições
Como instalar as extensões Dash To Dock e Hide Top Bar no Gnome 45/46
E a guerra contra bots continua
Tradução do artigo do filósofo Gottfried Wilhelm Leibniz sobre o sistema binário
Conheça o firewall OpenGFW, uma implementação do (Great Firewall of China).
Instalando o FreeOffice no LMDE 6
Anki: Remover Tags de Estilo HTML de Todas as Cartas
Colocando uma opção de redimensionamento de imagem no menu de contexto do KDE
Criar um script para testar pen drive (5)
Não consigo acessar os modos de desempenho (0)
Problema com alias usando locate (4)
[Shell Script] Script para desinstalar pacotes desnecessários no OpenSuse
[Shell Script] Script para criar certificados de forma automatizada no OpenVpn
[Shell Script] Conversor de vídeo com opção de legenda
[C/C++] BRT - Bulk Renaming Tool
[Shell Script] Criação de Usuarios , Grupo e instalação do servidor de arquivos samba