Algoritmos de Pesquisa em Grafos: DFS e BFS

Algoritmos de Pesquisa em Grafos

O acesso (e atualização, inserção e/ou eliminação) às ligações não é tão fácil. Contudo, o desenho do algoritmo que não necessita deste acesso é fácil, sendo normalmente utilizado para visitar todos os vértices (e respetivas utilizações) e proceder, eventualmente, às alterações necessárias.

Grafos (Pesquisa)

Um algoritmo de pesquisa de um grafo tem de assegurar que todos os seus vértices são visitados. Como o grafo é uma estrutura bidimensional, temos duas possibilidades de pesquisa: Depth First Search (DFS) - pesquisa por profundidade e Breadth First Search (BFS) - pesquisa em largura.

Depth First Search (DFS)

1. Tenta sempre ir mais fundo.
2. Explora todas as ligações dos vértices do grafo, constituída a partir das ligações de um vértice v.
3. Se permanecerem vértices por visitar, recomeça a processar utilizando um desses vértices.

Pior caso (com listas de adjacência): O(|E| + |V|), uma vez que todos os vértices e ligações serão utilizados no pior dos cenários.

Pior caso (com matrizes de adjacência): O(|V|²), uma vez que se torna necessário percorrer toda a matriz.

Uma alternativa à implementação recursiva, a pesquisa pode ser executada de forma repetitiva usando uma pilha. A pesquisa DepthFirstSearchStack invoca a pesquisa respetiva com pilha para todos os vértices que ainda não foram visitados e tem como parâmetro de saída a sequência de vértices criada durante a travessia em profundidade repetitiva.

Breadth First Search (BFS)

1. Explora uniformemente a partir de um vértice de partida.
2. Visita todos os vértices adjacentes ao vértice de partida, estabelecendo deste modo um conjunto de vértices.
3. Utiliza cada elemento deste conjunto como ponto de partida.

Pior caso (listas de adjacência): O(|E| + |V|)

Grafos: Caminho Mais Curto (com BFS)

A árvore de pesquisa, resultado do método de pesquisa na amplitude (Breadth First Search - BFS), pode ser utilizada na determinação de caminhos mais curtos:

• Caminho mais curto de um vértice V para um vértice N: o procedimento de pesquisa é interrompido quando se visita N.
• Caminho mais curto a partir de um vértice V: a árvore resultado do procedimento de pesquisa contém os caminhos mais curtos.
• Caminhos mais curtos de todos os pares de vértices: pede-se o método para todos os vértices do grafo.