Deep First Search
Publicado por Jose Maria Silveira Neto 31/03/2004
[ Hits: 11.682 ]
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.
Lista simplesmente encadeada com busca auto-organizada
Passando uma matriz para funcao
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
Dica para encontrar diversos jogos Indies criativos
Instalando Discord no Debian 13
Instalar driver Nvidia no Debian 13
Redimensionando, espelhando, convertendo e rotacionando imagens com script
paginação dos favoritos não funciona no vivaolinux[BU... (4)
Driver da nvidia e desempenho em jogos (2)
A escola é altamente ineficiente e ineficaz! (13)
Sincronização Horario Estação de trabalho máquinas domínio com samba N... (2)