Trabalho 3 - Busca em Largura e Profundidade (BFS e DFS)

Trabalho 3


Contexto
Antes de introduzirmos os algoritmos de Busca em Largura e Profundidade (BFS e DFS), vistos em sala de aula, é preciso relembrar o funcionamento de uma busca dentro de um grafo.
Para realizar qualquer busca, é necessário trabalhar com um algoritmo que percorra todas as arestas e vértices de um dado grafo, realizando uma análise sistemática de todos os caminhos e nós encontrados. Após realizar a primeira inspeção, na ponta inicial, o algoritmo deve percorrer até encontrar a ponta final, examinando a cada passo, no máximo, uma vez cada aresta.
Uma busca pode ser realizada de diversas maneiras. Nesse tópico, será introduzida a Busca em Largura (BFS) e a Busca em Profundidade (DFS).

Algoritmo de Busca em Largura (BFS)
A BFS inicia-se num vértice inicial V0 de um grafo G não ponderado. Seu retorno deve ser uma árvore T (BFS-tree), a qual possui os menores caminhos de V0 aos demais vértices.
Através deste algoritmo, realiza-se a visita de V0 e seus demais vizinhos; depois, todos os vértices à distância 2 de V0, e assim por diante, sempre enumerando os vértices em que visita, na exata sequência de descoberta, até conquistarmos a árvore T, já mencionada. Vale ressaltar que neste algoritmo, visamos sempre o uso da estrutura "fila" para fazer acesso à vértices.
A ideia principal deste algoritmo é: a cada novo "nível" descoberto, torna necessário visitar todos os tais vértices antes de seguir para o próximo nível.

Algoritmo de Busca em Profundidade (DFS)
A DFS trata-se do problema de encontrar o "território" de um dado vértice de um grafo G não ponderado, do tipo dígrafo, também retornando uma árvore -- assim com o BFS --, agora chamada de DFS-tree. A ordem pela qual realiza-se os acessos à vértices é do tipo de estrutura "pilha", ou seja, o vértice que sai da lista é sempre o que foi inserido mais recentemente. Neste, levamos em consideração dois aspectos: a ordenação topológica e os vértices de corte.
A ideia principal deste algoritmo é: a cada novo vértice descoberto, deve-se explorar um de seus vizinhos ainda não visitados, se esta ação for possível. Ou seja: aprofunda-se sempre que possível.

Execução do Algoritmo de Busca em Largura (BFS)
Para o BFS, criamos dois vetores: um relacionado à distância entre vértices, e outro aos predecessores. Iniciamos selecionando um vértice inicial V0, listando os seus vértices seguintes, na cor "WHITE". O cálculo da distância é referente ao número de arestas "andadas" até então: como esses vértices seguintes são descendentes de V0, somo um à distância. Então, adiciono V0 ao fim da fila e prossigo neste algorimo, pegando sempre o primeiro da fila. Vale tomar alguns cuidados: se determinado vértice já foi processado -- ou seja, acessado em alguma iteração anterior --, ele não deve ser reprocessado! E, caso finalizado todos os vizinhos de um determinado vértice, ele assume a cor "BLACK". No final, com todas as relações de predecessores, devemos obter uma BFS-tree.

Foi utilizada a linguagem Python, bibliotecas NumPy e Networkx. Para a simulação do código, foi utilizado o grafo "Karate", como orientado pelo professor.

Segue código abaixo:

BFS-tree encontrada:

Execução do Algoritmo de Busca em Profundidade (DFS)
Para o DFS, também seguimos com o mesmo passo inicial do BFS: criamos dois vetores, relacionados à distância entre vértices e aos predecessores de um determinado vértice. Iniciamos nossa busca num determinado vértice inicial V0, no tempo zero. Sempre que um novo vértice for descoberto, através do uso da estrutura "pilha", por chamada recursiva, iremos incrementar o tempo, atualizar sua cor para "GRAY". Se ele ainda não foi visitado, podemos realizar o acesso a ele, lembrando sempre de atualizar seu predecessor. Seu tempo de saída será sempre que ele não tiver mais vizinhos disponíveis para vista, ou caso todas as opções de vértices se encerrem -- nesse caso, cada vértice será encerrado por vez. No final, com todas as relações de predecessores e tempo, devemos obter uma DFS-tree.

Foi utilizada a linguagem Python, bibliotecas NumPy e Networkx. Para a simulação do código, foi utilizado o grafo "Karate", como orientado pelo professor.

Segue código abaixo:

DFS-tree encontrada:

Para visualizar o código completo, acesso o GitHub do nosso Trabalho 3 - Busca em Largura e Profundidade (BFS e DFS).