Teoria dos grafos

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 como resoluçõ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) ligados ou 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árias arestas.
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-se determinar 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 mapeamento de á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-first search (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 sejam descobertos. 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 sair dele.
- 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 é