Bem-vindos ao blog Preciso Estudar Sempre. Meu nome é João Paulo Maida e minha paixão é estudar.
Comecemos esta postagem com a seguinte pergunta: Em um grafo desconhecido, quais nós são possíveis de atingir a partir de um determinado nó ?
A resposta é simples. A partir de um nó inicial é possível atingir qualquer nó que esteja conectado à ele diretamente ou às suas adjacências por arestas. Esta regra é válida para qualquer nó. Contudo, o processo para chegar a essa conclusão não é tão trivial assim, pois os casos em que isto precisa ser determinado são aqueles que o único conhecimento disponível é sobre um nó inicial, ou seja, um ponto de partida.
Caso você tenha chegado a este ponto do texto não entendendo muito do que já foi explicado, recomendo fortemente que você leia nossa primeira postagem sobre a teoria dos grafos. Clique aqui para dar uma conferida.
A construção desse processo consiste em passos sistemáticos que possibilitam a movimentação de um vértice para outro, e assim de pouco em pouco espera se obter o conhecimento completo do grafo. Existem atualmente duas abordagens conhecidas para este tipo de processo: busca em profundidade (DFS - Depth First Search) e busca em largura (BFS - Breadth First Search). Ambas finalmente alcançarão todos os nós conectados. A primeira busca, alvo do nosso estudo, é implementada com uma pilha, ao passo que a segunda é implementada com uma fila. Esses mecanismos resultarão no grafo sendo percorrido de maneiras diferentes (LAFORE, ROBERT).
A pilha citada no parágrafo acima é uma estrutura que já foi abordada aqui no blog. Caso você a conheça pule este parágrafo, mas caso contrário, clique aqui e dê uma lida antes de continuar nesta postagem.
Descobrir a solução para a pergunta acima assombrou por muito tempo os estudiosos da teoria dos grafos, mas o matemático francês Charles Pierre Trémaux, no século XIX, propôs uma versão da busca em profundidade como estratégia para resolver labirintos.
 |
| Figura 1 - O labirinto |
 |
| Figura 2 - O labirinto do Minotauro |
Analisemos a Figura 3 para que possamos tomar conhecimento de como a busca em profundidade funciona.
 |
| Figura 3 - Grafo de exemplo |
Regra 1
Se possível, visite um nó adjacente não visitado, marque-o e coloque-o na pilha.
Executando esta regra, partimos de A em direção ao nó B. Em B executamos a regra 1 novamente e partimos em direção à F. O processo novamente se repete e vamos de F para H. O nó H não possui adjacências, e logo estamos parados. Então, o que fazer agora? Neste momento surge a regra 2.
Antes de abordarmos a regra 2 note que a denominação “profundidade” vem do efeito que a regra 1 causa no ato da movimentação do grafo. Note que exploramos toda uma ramificação de nós e arestas para assim depois decidir o que fazer. Essa característica será drasticamente modificada quando abordarmos as buscas por larguras.
OBSERVAÇÃO: O nó inicial também entra nesta regra mesmo não sendo adjacente.
Regra 2
Se você não puder seguir a Regra 1, então se possível, retire um nó da pilha.
Seguindo esta regra, desempilhamos H e voltamos para F, logo em seguida para B e finalmente para A. Executamos todo esse caminho de volta porque não foi possível executar a Regra 1, visto que todo este caminho já tinha sido explorado. Note que o uso da pilha tem imensa importância, pois ele age como se fosse o barbante de Teseu, ele mostra o caminho de volta. Quando chegamos em A, a Regra 1 se torna disponível mais uma vez pois este possui vários filhos. Então de A vamos para C e de C voltamos para A. A partir deste, o próximo destino é D.
O nó D por sua vez possui adjacências e a partir dele vamos para G e depois para I. Após chegar neste ponto, voltamos novamente para A, para finalmente ir para E e finalizar em A pela última vez.
Agora não temos mais o que fazer, já percorremos o grafo inteiro saindo de um ponto inicial e terminando o trajeto nele. Eis que surge a Regra 3.
Regra 3
Se você não puder seguir a Regra 1 ou a 2, então terminou.
A tabela abaixo mostra todas as operações realizadas na pilha enquanto o passo-a-passo, descrito acima, foi sendo feito.
Evento
|
Pilha
|
Vá para A
|
A
|
Vá para B
|
AB
|
Vá para F
|
ABF
|
Vá para H
|
ABFH
|
Volte para F
|
ABF
|
Volte para B
|
AB
|
Volte para A
|
A
|
Vá para C
|
AC
|
Volta para A
|
A
|
Vá para D
|
AD
|
Vá para G
|
ADG
|
Vá para I
|
ADGI
|
Volte para G
|
ADG
|
Volte para D
|
AD
|
Volte para A
|
A
|
Vá para E
|
AE
|
Volte para A
|
A
|
Desempilhe A
| |
Terminado
|
Visto que já conhecemos todos os passos necessários para executar a busca em profundidade, podemos agora ver sua implementação em Java. Repito novamente, que utilizo esta linguagem de programação por uma questão de afinidade, e nada impede que você implemente este mesmo algoritmo em uma outra linguagem de seu gosto.
A implementação se torna bem simples quando temos as regras em mente. O primeiro bloco, linhas 2 à 4, executam a regra 1 para o nó ponto de partida. Não necessariamente o seu nó de partida deve ser o primeiro item do array. Isto foi feito com a finalidade de facilitar a implementação do algoritmo.
O loop que segue da linha 7 até 16 perpetua a regra 1 e insere a regra 2 no programa. O próximo nó adjacente não visitado é obtido através de uma função específica que retorna a posição deste no array de nós. Caso o nó não exista, a regra 2 entra em ação. Caso contrário, o processo continua conforme descrito na regra 1. A implementação desta função não foi incorporada na função de busca porque havia o receio do código ficar muito extenso e isso atrapalhar a análise do algoritmo.
O último laço reseta a flag de visitação de todos os nós para que a busca possa ser executada posteriormente.
O método getAdjUnvisitedVertex(vertexIndex) é responsável para um determinado nó obter seus nós adjacentes não visitados, conforme citado acima. Sua implementação é simples e tem apoio da matriz de adjacência e da flag de visitação para a recuperação da informação desejada. Caso encontre, retorna a posição deste nó no array de nós.
Ambos os métodos fazem parte de uma classe que foi criada em postagens passadas. Logo, os detalhes que já foram incorporados não serão abordados aqui. Para que você tenha uma visão geral de tudo feito até agora, faça o download do projeto usando o link no fim do post.
A classe acima é somente utilitária. Sua única responsabilidade é criar e montar um grafo para depois executar a busca em profundidade nele. O resultado esperado de sua execução é o caminho percorrido pelo algoritmo de busca.
Nas referências é possível encontrar um excelente trabalho feito pela Universidade Federal da Paraíba, onde é proposto a criação de um labirinto aleatório através da aplicação de um algoritmo de busca em profundidade. Para fornecer as outras respostas do labirinto, como a saída e o menor caminho, outros algoritmos são utilizados. Vale a pena a leitura.
Até a próxima minha boa gente ! 😘
Leia nossa última postagem sobre grafos: Matrizes de adjacência e grafos
Download do trabalho da UFPB: https://drive.google.com/file/d/0BzDmhBY6luU6dktwUXhydTIxcms/view?usp=sharing
Download do código-fonte
Link do repositório GitHub: https://github.com/PrecisoEstudarSempre/Graphs.git
Dúvidas !? Sugestões ?! Críticas ou elogios ?!
Deixe aí nos comentários, envie um e-mail ou uma mensagem na nossa página do Facebook.
E-mail: precisoestudarsempre@gmail.com
Facebook: https://www.facebook.com/precisoestudarsempre/
Canal Preciso Estudar Sempre: https://www.youtube.com/channel/UCUoW8dS38rXr0a5jWU57etA
Referências
LAFORE, ROBERT; Estruturas de Dados e Algoritmos em Java; 2004
EVEN, SHIMON; Graph Algorithms; 2012
MENEZES, RÔMULO; MACHADO, LILIANE; MEDEIROS, ÁLVARO; Aplicação de Algoritmos de Grafos para Gerar e Percorrer Jogos de Labirintos Aleatórios; Universidade Federal da Paraíba
Nenhum comentário:
Postar um comentário