Please enable JavaScript.
Coggle requires JavaScript to display documents.
122–128 Busca em profundidade e Busca em Largura - Coggle Diagram
122–128 Busca em profundidade e Busca em Largura
Buscas exaustivas aplicadas para processar todas as arestas e vertices de um grafo, uteis para eficientes investigações de propriedades fundamentas de grafos como conectividade e presença de clico
Busca em Profundidade (Depth-First Search DFS)
Travessia
Começa num vertice arbitrario marcando-o como visitado
A cada iteração o algoritmo prossegue para um vertice não visitado adjacente ao vertice atual
Esse proceso continua até um final morto, um vertice sem adjacentes não visitados, ser encontrado
No final morto o algoritmo volta uma aresta para o vertice de onde veio e continua a visitar os vertices adjacentes não visitados a partir daí
o algoritmo eventuamente pára quando volta ao vertice inicial com o ultimo sendo um final morto, aí então todos os vertices terão sido visitados
Se ainda existirem vertices não visitados a busca em profundidade deve ser recomeçado por um desses
Implementação
É conveniente usar uma pilha para marcar a operação de busca em profundidade.
Empurra-se um vertice para a pilha quando o vertice é alcançado pela primeira vez e remove-se um vertice da pilha quando ele se torna um final morto
É util acompanhar a travessia da busca em profundidade construindo uma floresta de busca em profundidade
o vertice inicial da travessiaserve como a raiz para a primeira arvore da floresta
toda vez que um vertice não visitado é alcançado ele é colocado como filho do verticie pelo qual esse vertice foi alcançado
essa aresta é chamada de arestad e arvore e o seu conjunto forma a floresta
Pode ainda ser encontrado uma aresta levando a um vertice já visitado que não é seu pai imediato , essa aresta que liga o vertice a um ancestral que não é seu pai é chamada de aresta de volta
Eficiencia
Eficiente pois precisa de um tempo proporcional ao tamanho da estrutura de dados usada para representar o grafo em questão
Busca em Largura(Breadth-Frist Search BFS)
Travessia
Procede de uma maneira concentrica visitando-se primeiro todos os vertices adjacentes ao vertice inicial
Em seguida visita-se todos os vertices duas arestas de distancia do inicial e assim por diante até todos os vertices no mesmo componente conectado que o vertice incial forem visitados
Se ainda existirem vertices não visitados o algoritmo reinicia por um vertice arbitrario de outro componente conectado do grafo
Implementação
É conveniente usar uma fila para marcar a operação da busca em largura
A fila é inicializada com o vertice inicial da travecia que é maracado como visitado
À cada iteração o algoritmo identifica todos os vertices não visitados adjacentes ao vertice da frente da fil marca eles como visitados e adiona eles à lista
Depois disso o vertice da frente é removido da lista
Similarmente à travessia DFS é util utilizar uma floresta de busca em largura para acompalhar a BFS
O vertice inicial da travecia serve como a raiz da primeira arvore na floresta
quando um novo vertice não visitado é alcançado o vertice é colocado como filho do vertice pelo qual ele foi alacançado chamado de aresta da arvore
Se uma aresta leva a um vertice anteriormente visitado que não é seu pai é chamada de aresta cruzada
Eficiencia
mesma eficiencai que a busca em profundidada
diferentemente da DFS usa-se um singular vertice de ordenação devido à fila
Pode ter dois tipos de arestas arestas de arvore e arestas cruzadas