PROFUNDIDADE DE GRAFOS ABNT
1694 palavras
7 páginas
FACULDADE Internacional da ParaíbaCURSO DE GESTÃO EM TECNOLOGIA DA INFORMAÇÃO
LARGURA E PROFUNDIDADE DE GRAFOS
FRANCE-KARLA GOMES ACCYOLE
JAMERSON PEREIRA NEVES
THIAGO DOS SANTOS GADELHA
WELLINGTON PESSOA DOS SANTOS
JOÃO PESSOA-PB
2014
FRANCE-KARLA GOMES ACCYOLE
JAMERSON PEREIRA NEVES
THIAGO DOS SANTOS GADELHA
WELLINGTON PESSOA DOS SANTOS
LARGURA E PROFUNDIDADE DE GRAFOS
Trabalho apresentado por France-Karla Gomes Accyole, Jamerson Pereira Neves, Thiago Dos Santos Gadelha e Wellington Pessoa dos Santos, na Faculdade Internacional da Paraíba, para a obtenção da segunda nota do 3º período – do Curso de Gestão em Tecnologia da Informação, da disciplina de Estrutura de Dados.
Orientador: Prof(o). (Mestre) Emmanuel Farias.
JOÃO PESSOA-PB
DEZEMBRO/ 2014
RESUMO
Vários problemas representados por um grafo podem ser resolvidos efetuando uma busca nesse grafo. Às vezes é preciso visitar todos os vértices de um grafos, as vezes o problema pode ser resolvido visitando somente um subconjunto dos vértices. Consideremos por exemplo o problema do caminho mais curto. Os algoritmos apresentados para resolver esse problema fazem um percurso exaustivo de todos os vértices. Não precisa ser assim se, por exemplo, queremos o caminho mais curto até um vértice em particular. Nesse caso, assim que ele se encontra no conjunto dos vértices já visitado, não é preciso continuar o algoritmo.
Basicamente, existem duas técnica de busca em grafos: a busca em profundidade (depthfirst search) e a busca em largura (breadth-first search).
Palavras chaves: Grafo, Vértices, Algoritmo, Profundidade, Largura.
ABSTRACT
Several problems represented by a graph can be solved by conducting a search on this graph. Sometimes you have to visit all the vertices of a graph, sometimes the problem can be solved only visiting a subset of vertices. Consider for