Teoria dos grafos

Disponível somente no TrabalhosFeitos
  • Páginas : 4 (770 palavras )
  • Download(s) : 0
  • Publicado : 4 de dezembro de 2011
Ler documento completo
Amostra do texto
Grafos de Busca – Largura e Profundidade

UMA VISÃO GERAL SOBRE GRAFOS

Um grafo é uma estrutura de dados essencial para aplicações de roteamento urbano e também em outras aplicações, tais comoresoluções de funções matemáticas, máquinas de estados finitos e outra.
Para construir um grafo, como mostrado na Figura abaixo, necessita-se de um grupo de nós (representado por círculos) ligadosou não entre si por linhas, conhecidas como arestas, estabelecendo um relacionamento (ou link) de um nó com o seu adjacente. Para cada aresta é necessário um par de nós e cada nó pode ter váriasarestas.
Exemplo de um grafos:
Aplicação de Grafos de Busca em Roteamento Urbano

Uma das aplicações de grafos é na implementação de técnicas para roteamento urbano.
Através do grafo consegue-sedeterminar características de uma rota e até mesmo o melhor caminho para se percorrer um determinado trajeto. A aplicação de grafos no contexto no qual este trabalho se insere diz respeito ao mapeamentode áreas urbanas.

Percursos em Grafos de Busca

Existem dois métodos fundamentais em percursos de Grafos:
DFS - depth-first search ( Percurso em profundidades);
BFS - breadth-firstsearch (Percurso em largura).

Grafo de Busca DFS

A idéia básica da DFS é buscar “mais a fundo” no grafo quando possível. Assim, a partir de um vértice v, as arestas ainda não exploradas o são e,ao final, a busca retorna ao vértice w, que levou ao descobrimento de v pela aresta (w; v) e explora suas arestas ainda não visitadas. Assim a busca continua até que todos os vértices sejamdescobertos. Os grafos DFS possuem grafos dirigidos e não dirigidos.

Como é realizada a busca DFS
-As arestas são exploradas a partir vértice v mais recentemente descoberto que ainda tenha arestas a sairdele.
- Quando todas as arestas de v forem exploradas, retorna para explorar arestas que saíram do vértice a partir do qual v foi descoberto.
- Se se mantiverem vértices por descobrir, um deles é...
tracking img