Deep First Search
Publicado por Jose Maria Silveira Neto 31/03/2004
[ Hits: 11.478 ]
O algoritmo mais simples para solucionar problemas com grafos.
Ele percorre todo vertice adjacente que ainda não foi visitado (ou que já foi visitado com um custo mais alto).
Ele serve para resolver problemas como labirintos, distancia mais curta entre duas cidades, etc. Porém não é o algoritmos mais eficiênte.
Implementação recursiva.
/* Grafo+DeepFirstSearch * Preparacao para a OBI 2004 * Jose Maria Silveira Neto * */ #include<stdio.h> #define max 50 #define nulo 0 #define infinito max-1 enum booleano {false,true}; int grafo[max][max]; int distancia[max]; int vertices, arestas; int custo=0; // ********** GRAFO void limpa_grafo(){ int i,j; for (i=0;i<vertices;i++) for (j=0;j<vertices;j++) grafo[i][j]=nulo; } void mostra_grafo(){ int i,j; for (i=0;i<vertices;i++){ for (j=0;j<vertices;j++){ if (grafo[i][j]==nulo)printf(". "); else printf("* "); } printf("\n"); } } void ler_grafo(){ int i,j,a,b; scanf("%d %d",&vertices, &arestas); for (j=0;j<arestas;j++){ scanf("%d %d",&a,&b); grafo[a-1][b-1]=1; grafo[b-1][a-1]=1; // (1) } } int grau(int n){ int i,ocorrencias; for (i=0;i<vertices;i++) if (grafo[n][i]) ocorrencias++; return(ocorrencias); } // Visita DFS void visitaDFS(int n){ int i; distancia[n]=custo; for (i=0;i<vertices;i++) if ( (grafo[n][i]) && (custo<distancia[i]) ){ custo++; printf("visitando %d a partir de %d. custo= %d \n",i,n,custo); visitaDFS(i); custo--; } } // Deep First Search (Busca em profundidade) void DFS(int source){ int i; printf("Inicializando uma DFS em %d\n",source); for(i=0;i<vertices;i++){distancia[i]=infinito;} distancia[source]=0; custo=0; for(i=0;i<vertices;i++) if ( (grafo[source][i]) && (custo<distancia[i])){ printf("visitando %d a partir de %d . custo= %d \n",i,source,custo); custo++; visitaDFS(i); custo--; } } // ********** PRINCIPAL int main(){ int i; limpa_grafo(); ler_grafo(); mostra_grafo(); DFS(0); for (i=0;i<vertices;i++){printf("[%d]",distancia[i]);} printf("\n"); } // (1): Admite-se que o grafo eh bidirecional, nao ponderado e que os vertices // sao numerados a partir de 1. Este codigo pode ser facilmente alterado // para qualquer outro tipo de grafo.
Loop de Várias Váriáveis Em Um Único Laço "For" em C
Retorna o tempo ocioso em uma sessão do X
Nenhum comentário foi encontrado.
Compartilhando a tela do Computador no Celular via Deskreen
Como Configurar um Túnel SSH Reverso para Acessar Sua Máquina Local a Partir de uma Máquina Remota
Configuração para desligamento automatizado de Computadores em um Ambiente Comercial
Efeito "livro" em arquivos PDF
Como resolver o erro no CUPS: Unable to get list of printer drivers
Flatpak: remover runtimes não usados e pacotes
Mudar o gerenciador de login (GDM para SDDM e vice-versa) - parte 2
Estou com sede em aprender sobre o nosso querido Linux. (1)
big linux sem audio como resolver (2)
Como faz para dar um update-grub por shell script [RESOLVIDO] (3)
[Python] Automação de scan de vulnerabilidades
[Python] Script para analise de superficie de ataque
[Shell Script] Novo script para redimensionar, rotacionar, converter e espelhar arquivos de imagem
[Shell Script] Iniciador de DOOM (DSDA-DOOM, Doom Retro ou Woof!)
[Shell Script] Script para adicionar bordas às imagens de uma pasta