Deep First Search
Publicado por Jose Maria Silveira Neto 31/03/2004
[ Hits: 11.331 ]
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.
Embutir texto em arquivos de imagem
Desenhando uma curva Dragão ou o Fractal Jurassic Park
Nenhum comentário foi encontrado.
Atenção a quem posta conteúdo de dicas, scripts e tal (1)
Manutenção de sistemas Linux Debian e derivados com apt-get, apt, aptitude e dpkg
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
Como Atualizar Fedora 39 para 40
Instalar Google Chrome no Debian e derivados
Consertando o erro do Sushi e Wayland no Opensuse Leap 15
Instalar a última versão do PostgreSQL no Lunix mantendo atualizado
Flathub na sua distribuição Linux e comandos básicos de gerenciamento
iso de sistema 32 bit em atividade (6)
erro ao clonar repo github (9)
ASRock H310CM-HG4 vs Linux (14)