Aprendendo a escolher bem o que por em ordem - O algoritmo Selection Sort

Olá ! Meu nome é João Paulo Maida e bem-vindos ao blog Preciso Estudar Sempre.

Ordenar é de fato uma tarefa que às vezes nos deixa de cabelos em pé. Na literatura existem vários algoritmos que podem nos ajudar, cada um com suas características. As opções são tantas que o problema muda de achar uma solução para qual solução escolher.

Como já vimos aqui em várias situações, o que vai determinar a solução necessária para um certo problema é, de fato, o problema. Logo, se velocidade é o seu problema vá para o Quick Sort, mas se o problema for lidar com partes já ordenadas, use o Insertion Sort (clique aqui para dar uma lida), e assim segue.

Um dos algoritmos primordiais ensinados, seja na faculdade ou no cursinho técnico, é o Bubble Sort (clique aqui). Ele, junto com Insertion Sort e Selection Sort, compõem uma categoria conhecida como “Algoritmos de ordenação simples”. Não vá achando que simples signifique inútil. Ao contrário, esses algoritmos servem como base para algoritmos mais complexos como Quick Sort, Merge Sort e Shell Sort. O que difere a categoria dos básicos para dos complexos são as técnicas e estruturas de programação utilizadas.

Nosso foco hoje será exclusivamente o Selection Sort para assim fechar a categoria dos simples. Abordaremos seu conceito, sua implementação e características.

Imagine que exista uma fileira de lápis que possuem vários tamanhos e você quer por eles em ordem porque, assim como eu, tem TOC.

Figura 1 - Lápis desordenados

Para ordenar esses lápis utilizando a técnica do Selection Sort marcamos o primeiro lápis (à esquerda) com um marcador indicando que aquele é o menor lápis encontrado no momento. Após isso, verificamos um após o outro até o fim, a fim de encontrar algum lápis menor. Quando encontrado, é marcado como o menor lápis encontrado até o momento, mas a busca continua até o fim do conjunto. Caso algum lápis menor ainda seja encontrado, o marcador é movido para este. Caso contrário, a troca já pode ser feita e, o ciclo de ordenação do primeiro lápis está concluído. O marcador vai para o segundo lápis do conjunto. 

No exemplo acima, o menor lápis encontrado em uma primeira instância seria o quarto, porém finalmente o sétimo seria revelado como o menor de todos. Os marcadores iriam ser movidos do primeiro para o quarto e posteriormente para o sétimo. Após finalizado o ciclo, o marcador voltaria para o segundo lápis para assim iniciar um novo ciclo, e este processo se repete até o conjunto todo estar ordenado.

A Figura 2 é um GIF animado que mostra todo o processo sendo feito.

Figura 2 - Funcionamento do algoritmo SelectionSort

Visto que já cobrimos toda a parte teórica do assunto, podemos partir para a prática.

Quem acompanha o blog sabe que eu sempre escolho a linguagem Java como alvo das minhas implementações, mas como o grande Mário Sérgio Cortela já diz:

Mudar é complicado mas acomodar é perecer (Cortella, Mário Sérgio).

Vamos implementar o nosso algoritmo em Javascript, afinal de contas é uma linguagem que funciona em todos os navegadores de todos os dispositivos, sejam eles computadores, notebooks, celulares ou tablets; e não é necessário um ambiente tão complexo de execução igual ao do Java.

1 2 3 4 5 6 7 8 9

for(out=0; out<qtd-1; out++){ marcador = out; //primeiro elemento marcado for(ins=out+1; ins<qtd; ins++){ //varro os itens a direita procurando o menor de todos if(valores[ins] < valores[marcador]){ //encontrado item menor ? marcador = ins; //move o marcador } } _trocar(out, marcador); //acabaram os dois laços então posso fazer a troca }

(LAFORE, ROBERT)

Note que o algoritmo é bem simples, não há nada extremamente complexo. Os dois laços for orquestram o processo descrito nos parágrafos acima. O primeiro começando do início e o segundo iniciando a partir do ponto de partida do primeiro, ou seja, se o primeiro laço começa em 0, o segundo começará em 1. Contudo, note que o primeiro laço só vai até qtd-1, porque ? Porque não ir até qtd ?

A resposta é simples se pararmos para analisar a situação como um todo. Com as consecutivas trocas dos valores, os maiores (no caso de ordenação crescente) são sempre jogados para o fim e o maior valor terá seu lugar trocado com alguém menor que ele, ocupando assim o último lugar. Por tais motivos não é necessário que o laço mais externo percorra todas posições do array.

Os nomes das variáveis controladoras de laço foram escolhidas devido ao fato de existirem um laço externo e um interno, logo respectivamente out e ins. O resto do código está bem claro e dispensa maiores explicações.

A ordenação por seleção executa o mesmo número de comparações que a ordenação pelo método bolha: N*(N-1)/2. Para grandes valores de N, os tempos de comparação predominarão, portanto a ordenação por seleção executa em tempo de O(n²), exatamente como a ordenação em bolha. Contudo, ela tende a ser bem mais rápida porque há poucas trocas. Para valores menos de N, a ordenação por seleção pode ser de fato mais rápida, especialmente se os tempos de troca forem muitos maiores que os tempos de comparação (LAFORE, ROBERT).

Chegamos ao fim de mais um post meus amigos. Espero que tenham gostado. Caso tenham sentido falta de algum detalhe, deixe nos comentários.

Até a próxima minha boa gente ! 😘

Leia nossa postagem anterior: Cuidado com os comentários, eles são perigosos !!!

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.

Download no GoogleDrive: clique aqui
Download no Dropbox: clique aqui

E-mail: precisoestudarsempre@gmail.com
Facebook: https://www.facebook.com/precisoestudarsempre/
Canal Preciso Estudar Sempre: https://www.youtube.com/channel/UCUoW8dS38rXr0a5jWU57etA

Referências

Cortella, Mário Sérgio; Mudar é complicado? Acomodar é perecer.; https://www.youtube.com/watch?v=Ry3_5Pl8qmk

LAFORE, ROBERT; Estruturas de Dados e Algoritmos em Java; 2004

Leia Mais ››

O algoritmo de Dijkstra - Grafos

Olá ! Meu nome é João Paulo Maida e bem-vindos ao blog Preciso Estudar Sempre.

Você já pensou em alguma vez fazer uma daquelas viagens como mochileiro que você sai sem rumo de casa, só com mochila e dinheiro para a passagem do ônibus ? Seu destino final você decide a cada parada. Hoje você pode estar saindo do Rio de Janeiro e amanhã estar amanhecendo em alguma cidade do interior de Minas Gerais. A partir de lá você pode decidir ir para São Paulo, e de lá para o Mato Grosso. Em cada cidade que você pára, avalia quais podem ser seus destinos e quais são os mais baratos. Até porque para este tipo de viagem a grana é sempre curta.

Devo admitir que este tipo de aventura sempre foi um sonho para mim, mas acho que dificilmente um dia irei realizá-lo. Se você um dia já se aventurou de tal forma ou pensa em se aventurar, sabe que seria interessante ter uma relação das conexões das cidades baseadas em seus custos de transporte onde esses são baseados em suas distâncias, exemplo: ir do RJ para SP custa R$ 80, do RJ para MG custa R$60, de MG para MT custa R$30 e por aí vai. Com essa relação em mãos fica fácil decidir qual caminho tomar gastando pouco com passagem. Seria um sonho, não ?

Para nossa alegria e felicidade, este sonho sim é possível atingir. Mais uma vez a teoria dos grafos chega para salvar o dia com um algoritmo que nos dá exatamente a resposta que estamos procurando. Apresento o algoritmo de Dijkstra. A criação de Edsger Dijkstra é baseada na representação da matriz de adjacência de um grafo e não somente encontra o caminho mais curto a partir de um nó especificado até outro, como também os caminhos mais curtos do mesmo nó especificado até os outros (LAFORE, ROBERT).

Imaginemos a nossa viagem aventureira representada pela Figura 1 e não se prenda a detalhes de geografia.

Figura 1 - Mapa das cidades

Você está partindo do Rio de Janeiro e quer saber quais são os caminhos mais baratos para as próximas cidades, para assim chegar ao seu destino final pelo melhor caminho. Você sabe que em cada cidade que pára existe um agente da empresa de ônibus e que ele pode te informar os trajetos e tarifas. Então, você pega seu bloquinho (todo bom viajante deve ter um) e faz uma tabelinha com essa relação para que no final você tenha todas as informações “mastigadas”.

Tabela 1 - Tabela das viagens mais baratas

Então, assim como eu, você é um amante da teoria dos grafos e pensa: as cidades podem ser os vértices de um grafo e os trajetos entre elas as arestas. Eu sei que cada trajeto tem uma direção e um preço de passagem, então isso pode ser respectivamente a direção e o peso das arestas. No fim das contas, eu tenho um grafo ponderado orientado. Isso é ótimo !

É aí que entra o algoritmo de Dijkstra. Ele pega o seu grafo, analisa, e como resultado gera uma árvore. Esta árvore segue os conceitos básicos de uma árvore mas não é como uma árvore geradora mínima, a qual já vimos (clique aqui). Ela é diferente porque é montada levando em conta o somatório dos pesos a partir do nó inicial.

Abaixo estão relacionadas as etapas do algoritmo. Os detalhes de cada uma serão vistos mais à frente. Com o entendimento dessas etapas, entender o algoritmo em Java fica muito mais fácil.

Etapas do algoritmo:

1. Lembra da tabelinha da relação dos caminhos mais baratos ? Aqui ela toma a forma de um array, onde seu tamanho reflete a quantidade de vértices do grafo, cada posição representa um vértice e inicialmente é preenchido por completo com um valor muito grande (veremos o motivo disso mais à frente) que chamaremos de INFINITY. Chamaremos este array de array de menor caminho.
2. Após montado, o nó inicial, ou seja, nosso ponto de partida é analisado. São adicionados no array de menor caminho somente os vértices que são adjacentes ao nó inicial. Essa adição tem a forma de um objeto com informações sobre o vértice antecessor ao vértice analisado e o custo para chegar até ele. É necessário ter informações sobre o antecessor pois precisamos saber como chegamos ali (entenderemos esse ponto melhor a frente). Porque é assumido que estes vértices representam os melhores caminhos a partir do vértice inicial e podem ser inseridos no array de menor caminho ? A resposta é óbvia. Se os nós que são inseridos no array são aqueles adjacentes ao nó inicial, logo não existe nada que separe-os e assim se tornam os melhores custos neste trajeto. É importante citar que essas adições são feitas por cima dos valores que já existem em uma determinada posição do array.
3. Lembra que o resultado do algoritmo de Dijkstra é uma árvore ? Então, já podemos adicionar o primeiro nó (início) na árvore.
4. A partir dos nós restantes, verificamos 1 por 1 para averiguar qual tem o menor custo a partir do início.
5. Caso não haja nenhum é porque o nó inicial não tem conexões, ou seja, é inatingível ou todos já estão na árvore. Caso contrário, o nó com menor custo (adjacente ao inicial neste caso) é selecionado.
6. Uma vez selecionado, é adicionado na árvore e o array de menores caminhos é atualizado.
7. A atualização tem forma parecida com a adição citada no passo 2, ou seja, a mesma estrutura de objeto é citado. Consiste em analisar se o somatório de valores do início até o nó selecionado é menor que o valor já registrado. Isto deve ser feito por causa do passo 2.
8. Após esses passos terminados, o array de menor caminho está finalizado.

Após a aplicação do algoritmo, nossa tabela deverá ficar assim:

Tabela 2 -Tabela de viagens mais baratas preenchida

Através da Tabela 2 fica claro porque precisamos da informação do antecessor ? Com ela em mãos conseguimos refazer todo o caminho feito desde do nó inicial, ou seja, agora eu sei que o melhor caminho para a cidade de Bonito no estado do Mato Grosso do Sul é através de Ribeirão Preto em São Paulo e que o melhor caminho para este é via São Paulo capital, e para este o melhor é caminho é vir diretamente de Rio de Janeiro capital. Tudo mais claro agora não !?

Agora veremos a implementação desse algoritmo em Java e como já é de costume, é necessário dizer que é possível implementar este algoritmo em qualquer linguagem de programação. A linguagem Java foi escolhida somente por uma questão de afinidade.

O código abaixo é um dos mais difíceis já mostrados aqui no blog, mas não se espante que com calma tudo fica fácil. Não mostrarei o código inteiro aqui porque tal tornará a leitura complicada, visto que o que realmente importa são as três funções chave as quais compõem o algoritmo de Dijkstra.

findAllShortestPaths()

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34

public void findAllShortestPaths(){ int startTree = 0; vertexList[startTree].setIsInTree(true); //adiciono o primeiro vértice do grafo na árvore nTree = 1; //mudo o contador porque acabei de adicionar um nó na árvore for (int i=0; i<nVerts; i++) { //inicializo o array de menores caminhos com as distâncias int distance = adjMat[startTree][i]; //das adjacências do primeiro vértice shortestPathArray[i] = new ShortestPathObject(startTree, distance); } while (nTree < nVerts) { //até todos os nós estarem na árvore int shortestVertex = getMin(); //seleciona o vértice que tem o valor mínimo, essa função provê int shortestDistance = shortestPathArray[shortestVertex].getDistance(); //a direção que o algoritmo vai seguir if(shortestDistance == INFINITY){ //se todos forem infinito ou todos na árvore System.out.println("There are unreachable vertices"); break; } else { currentVert = shortestVertex; startToCurrent = shortestDistance; } vertexList[currentVert].setIsInTree(true); //coloca o vértice atual na árvore nTree++; //mais um nó entrou na árvore updateShortestPathArray(); //atualizo os valores mínimos } displayPaths(); //exibo todos os nós nTree = 0; //limpa a ávore for (int i=0; i<nVerts; i++) { vertexList[i].setIsInTree(false); } }

Aqui é onde acontece toda a mágica. Como existem muitos detalhes que devem ser vistos, esta função divide essa responsabilidade com duas outras funções: getMin() e updateShortestPathArray(). Tentei deixar o código o mais explicado possível através de comentários, nomes de variáveis e métodos. Por causa disso não me estenderei em explicações aqui.

getMin() e updateShortestPathArray()

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

private int getMin(){ int shortestDistance = INFINITY; int shortestVertex = 0; for (int i=1; i<nVerts; i++) { //passo por todos os nós if (!vertexList[i].isInTree() && shortestPathArray[i].getDistance() < shortestDistance) { //analiso se o nó já está na árvore e se a distância dele shortestDistance = shortestPathArray[i].getDistance(); //é a menor. Se for, atualizo as variáveis shortestVertex = i; } } return shortestVertex; } private void updateShortestPathArray(){ int column = 1; while (column < nVerts) { //percorre todas as colunas da "tabelinha" if (vertexList[column].isInTree()) { //se a coluna da "tabelinha" já estiver na árvore não há column++; //de atualizar sua entrada no array de valores mínimos continue; } int currentToTarget = adjMat[currentVert][column]; //variável que guarda o valor da distância do nó atual(RJ) até um nó de destino que não está na árvore, nem sempre esse vértice de destino tem uma conexão de fato int startToTarget = startToCurrent + currentToTarget; //variável que guarda a distância total do início até o destino int shortestDistance = shortestPathArray[column].getDistance(); //recupera o valor do array de valores mínimos if (startToTarget < shortestDistance) { //essa comparação é essencial pois se não há uma conexão de fato entre dois vértices, a soma total será INFINITY + algum valor de aresta e este é menor que somente INFINITY, logo não há necessidade de atualização nesse caso. shortestPathArray[column].setParentVert(currentVert); //caso a soma seja de valores que realmente possuem conexão (RJ-SP-RP-BN) ela será menor que INFINITY e logo há porque atualizar shortestPathArray[column].setDistance(startToTarget); } column++; } }

Entender o que essas funções fazem é essencial para um entendimento total da implementação do algoritmo. Elas possuem tanta importância quanto a função findAllShortestPaths(). Basicamente, a função getMin() decide a direção de exploração no grafo escolhendo o nó com o melhor (menor no nosso caso) custo possível que ainda não está na árvore. Outro detalhe importante é que a ação de adicionar um vértice do grafo em uma árvore apartada é o fator determinante para que aquele vértice não seja mais analisado pelo algoritmo.

A função updateShortestPathArray() atua na atualização do array de menores caminhos e avalia se o custo de um trajeto inteiro vale a pena ou não de ser computado como ou não como um melhor caminho. Sem essa função não teríamos os resultados que tanto desejamos. No fim das contas, o que esperamos é a Tabela 2, já mostrada acima, e a Figura 3 que representa a árvore gerada pelo algoritmo.

Figura 3 - Árvore montada pelo algoritmo de Dijkstra

 Com isso fechamos a série Grafos do blog. Se olharmos para trás veremos que falamos e aprendemos muito. Começamos de forma humilde para que no fim pudéssemos fechar de forma triunfal. E a idéia sempre foi essa, discutir e aprender cada vez mais. Se você chegou até esse ponto da leitura fico feliz, espero ter feito a diferença e agradado.

Até a próxima minha boa gente ! 😘

Leia nossa postagem anterior: Você já parou para pensar sobre controle transacional ?

Download do código-fonte
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

Leia Mais ››

Indicações de livros - Estruturas de dados e Algoritmos em Java

Bem-vindos ao blog Preciso Estudar Sempre. Meu nome é João Paulo Maida e minha paixão é estudar.

Para dar aquela quebrada na rotina, neste mês trago a indicação de um excelente livro através de um vídeo do nosso canal do YouTube (links lá embaixo). Não perca, ficou muito bom. :D

Livro: Estruturas De Dados E Algoritmos em Java
Autor: Robert Lafore
Editora: CIENCIA MODERNA
Sumário:

• Capítulo 1 - Visão geral
• Capítulo 2 - Vetores (se você já sabe, pode pular)
• Capítulo 3 - Ordenação simples (recomendo muito)
• Capítulo 4 - Pilhas e filas (importante para qualquer desenvolvedor)
• Capítulo 5 - Listas encadeadas (importante para qualquer desenvolvedor)
• Capítulo 6 - Recursão (diferencia homens de meninos)
• Capítulo 7 - Ordenação avançada (recomendo muito)
• Capítulo 8 - Árvores binárias (importante para qualquer desenvolvedor)
• Capítulo 9 - Árvores rubro-negras (inside the matrix)
• Capítulo 10 - Árvores 2-3-4 e armazenamento externo (inside the matrix)
• Capítulo 11 - Tabelas Hash (importante para qualquer desenvolvedor)
• Capítulo 12 - Heaps (inside the matrix)
• Capítulo 13 - Grafos (se você gosta de assuntos mais complicados, aqui é o lugar)
• Capítulo 14 - Grafos ponderados (se você gosta de assuntos mais complicados, aqui é o lugar)
• Capítulo 15 - Quando usar o que ? (um dos melhores capítulos)

Até a próxima minha boa gente ! 😘

Leia nossa postagem anterior: O algoritmo Warshall - Grafos

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

Leia Mais ››

O algoritmo Warshall - Grafos

Bem-vindos ao blog Preciso Estudar Sempre. Meu nome é João Paulo Maida e minha paixão é estudar.

Até este momento já vimos bastante coisa sobre grafos. Estudamos seus conceitos mais fundamentais, tipos de buscas, árvores geradoras mínimas e por último, orientação. A orientação se torna um grande divisor de águas quando o assunto é grafos. Isto acontece pelo simples fato de que a adição de direção nas arestas muda completamente as regras do jogo. Se antes era possível iniciar um trajeto em um determinado ponto e terminar em outro, agora não é mais, e tal fato se torna uma pergunta. Como determinar todos os caminhos possíveis de um grafo ? Quais são as aplicações disso no mundo real ?

Bem, a segunda pergunta é fácil de responder. Basta pensar em um aeroporto, como o aeroporto do Galeão no Rio de Janeiro, e tentar determinar quais viagens são possíveis de fazer a partir dele. Cada aeroporto representaria um nó e cada trajeto direto (sem escalas) possível uma aresta. Logo, se existe uma viagem que parte do Galeão e vai para Frankfurt na Alemanha, teremos dois nós G e F (representados pelas primeiras letras dos aeroportos) ligados por uma seta iniciando em G e indo para F. Em seguida, se somente a partir de Frankfurt é possível ir para Varsóvia, na Polônia, então será necessário realizar o trajeto Galeão -> Frankfurt -> Varsóvia. Não existe outro caminho possível.

Para o nossa primeira pergunta o que era problema se torna trivial, pois estamos analisando um exemplo muito pequeno mas imagine um cenário real, onde você pode ir para qualquer lugar do mundo e muitas vezes só existem caminhos de ida e não de volta. Acredito que as coisas se compliquem um pouco. Então determinar um procedimento capaz de realizar esse mapeamento completo se torna crucial.

Figura 1 - Grafo orientado G com sua tabela de conectividade

Para o grafo da Figura 1 é fácil determinar quais caminhos podem ser feitos, pois ele é pequeno e junto à ele é apresentado sua tabela de conectividade. Esta tabela tem como função mostrar quais nós são alcançáveis a partir de um determinado nó, representado pela primeira letra da sequência. Logo, a partir de A é possível ir até B, C e E. Isto já representa um avanço, visto que possuímos um catálogo completo sobre quais caminhos podemos fazer. Contudo, o foco deve ser em fornecer uma forma direta de saber se um caminho é possível ou não, exemplo: é possível a partir de A chegar à D ?

Analisando rapidamente a tabela é possível concluir que isto é uma inverdade, e somente é possível chegar a essa conclusão pois vimos letra após letra da sequência que começa com A. Tal processo é custoso visto que leva tempo O(N), onde N é o número médio de nós alcançados a partir de um determinado nó. Mas, conforme citado acima, procuramos uma forma direta de obter essa informação, procuramos uma forma que leve tempo O(1) (LAFORE, ROBERT).

Tal almejada forma é o algoritmo de Warshall e sua ideia é extremamente simples. Ele utiliza uma estrutura já conhecida, a matriz de adjacência, e insere novas informações nela, a fim de torná-la mais rápida. A matriz melhorada gera um grafo chamado de fechamento transitivo do grafo original (LAFORE, ROBERT).

Para entendermos como funciona o algoritmo, antes precisamos tomar conhecimento da matriz de adjacência do grafo atual.

Figura 2 - Matriz de adjacência do grafo G

----------------------------------------------------------------------------------------------------------------
LEMBRETE: As linhas representam as origens de uma aresta e as colunas os fins, ou seja, se na célula AB existe o número 1 logo existe uma aresta de A para B.
----------------------------------------------------------------------------------------------------------------

O algoritmo deve percorrer todas as células da matriz. Caso encontre 1 em alguma célula, ele saberá que ali existe uma aresta. Para cada aresta encontrada ele deve percorrer todas as células da coluna correspondente à sua linha, ou seja, se foi encontrado 1 na célula AB, a coluna A deverá ser percorrida completamente. Caso nesta coluna exista algum 1, ele saberá que existe uma aresta chegando naquele nó, onde a origem será a linha dessa célula. Neste exato momento é concluído que existem dois caminhos que partilham um mesmo nó. Então, se existe tal caminho ele pode ser “encurtado” em um caminho só, logo um 1 é adicionado na célula correspondente a esse caminho. Confuso ? Nem um pouco. A Figura 3 mostra como o processo funciona.

Figura 3 - Funcionamento do algoritmo de Warshall

Acredito que com a imagem a explicação do parágrafo acima ficou mais fácil de ser entendida. Em uma primeira instância o algoritmo encontra a aresta A -> B, mas verificando a coluna A conclui que não existem arestas chegando nele logo a partir deste nó só partem arestas. A verificação da linha A foi terminada, a linha B vem em seguida.

A verificação começa e a aresta B -> C é descoberta. A coluna B é verificada e a aresta A -> B é encontrada, logo o nó B é comum as duas arestas e através dele é possível conectar A à C. Por fim, a célula AC é marcada com 1 para representar que existe uma aresta que liga esses dois nós. Este procedimento é repetido para todos os nós das linhas da matriz. Quando não houver mais linhas para serem processadas, o algoritmo chegou ao fim.

Abaixo apresento uma implementação feita em Java para este algoritmo. Como já é de costume é importante deixar bem claro que escolhi Java por uma questão de afinidade e nada impede que você escolha uma linguagem de seu gosto. Nosso foco aqui não é realizar as melhores práticas da linguagem, mas sim aprender como o algoritmo funciona.

Graph.java
O algoritmo é bem simples visto que são três laços de repetição com algumas condicionais. O primeiro laço consiste na varredura das linhas da matriz, o segundo das colunas. Caso haja uma aresta, a procura na coluna correspondente é feita no terceiro laço. Se todas as correspondências forem encontradas o novo caminho é gravado na matriz. Todo este procedimento é repetido para todas as linhas da matriz fazendo com que o algoritmo chegue ao fim e torne o acesso à caminhos de um grafo O(1).

WarshallAlgorithm.java
Esta classe é apenas uma classe cliente, sua única responsabilidade é criar grafos, adicionar arestas e vértices, e executar o algoritmo de Warshall. Exibir o fechamento transitivo do grafo original e checar possíveis caminhos também são operações realizadas aqui.

A partir dessa postagem entraremos em uma outra classe de grafos, os grafos ponderados. Aqui veremos que é possível atribuir pesos para as arestas e ver qual é o melhor caminho a ser feito, assim como os programas de GPS fazem. Mais um passo no longo caminho do entendimento desta extraordinária teoria foi dado.

Até a próxima minha boa gente ! 😘

Leia nossa postagem anterior: A orientação em grafos - Grafos

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

Leia Mais ››

A orientação em grafos - Grafos

Bem-vindos ao blog Preciso Estudar Sempre. Meu nome é João Paulo Maida e minha paixão é estudar.

Já estudamos anteriormente que é possível mapear diversas situações do mundo real em grafos (clique aqui para ler a nossa primeira postagem sobre grafos). Trajetos, labirintos, linhas de transmissão de energia, linhas férreas, jogos e até uma viagem em família são grandes exemplos da presença desse ramo da matemática no nosso dia-a-dia. Contudo, em todos esses exemplos uma característica ainda não foi analisada, a direção. Até agora não nos preocupamos com este ponto especificamente porque todos os nossos exemplos cabiam em grafos não orientados.

Porque a direção seria importante em um grafo ? A resposta é simples. Imagine que você está mapeando em um grafo o trajeto de carro que parte de um ponto A e vai para um ponto B. Como você sabe as ruas têm direções e muitas vezes quando se está dirigindo só é permitido seguir um tipo de sentido. Logo, tal característica também deve ser refletida em um grafo, pois a orientação mostra quais os trajetos são possíveis de um ponto origem para um ponto destino.

Quando estávamos estudando grafos não orientados podíamos simples sair de um nó A passar em vários outros até chegar ao nó Z, por exemplo. Bastava somente que existisse arestas que fizessem essa conexão, direta ou indiretamente. Contudo, com grafos orientados a história é outra. Se existir um único caminho que leve de A à Z, é esse que deve ser seguido e não há a possibilidade de fazer esse trajeto sem ser por esse caminho. Se houver mais de um caminho, sem problemas, os dois podem ser percorridos. Mas, se não houver caminho que ligue A à Z, ele se torna inalcançável a partir de sua origem.

A Figura 1 mostra dois grafos com a mesma disposição de nós e arestas, só que o grafo acima é orientado e o abaixo é não orientado.

Figura 1 - Um grafo orientado e um grafo não orientado

Conforme já comentado anteriormente, em um grafo orientado pode ser que só exista um caminho que liga um nó a outro. Na Figura 1 tal situação acontece e é representada pelo seguinte trajeto: A-B-E-F-J-H-Z.

Um outro ponto que também deve ser analisado é como a orientação de um grafo se reflete em sua matriz ou lista de adjacências, quais são os impactos disso. Antes tínhamos de nos preocupar em representar de forma bidirecional a conexão entre dois nós, ou seja, se A fosse conectado à B tínhamos que fazer uma marcação nas células AB e BA da matriz, onde a primeira letra representa a linha e a segunda a coluna. Agora isso não é mais necessário pois a direção da aresta dita qual célula deve ser preenchida, característica a qual não existia antes em grafos não orientados. Se em A houver uma aresta que parte para B, então somente a célula AB receberá a marcação. Caso contrário, somente a célula BA recebe. No caso de uma lista de adjacências o comportamento descrito acima se repete, logo o que mudaria é que uma das posições da lista não teria a conexão oposta pois o sentido é único. Caso o assunto seja estranho para você, recomendo a leitura do nosso segundo post sobre grafos.

Figura 2 - Grafos orientado e não orientado com suas respectivas matrizes de adjacência

Com a Figura 2 a diferença entre as matrizes de adjacência se torna muito óbvia, pois o fenômeno descrito no parágrafo acima é representado. Para um grafo não orientado, metade da matriz de adjacência espelha a outra metade, portanto, a metade das células se tornam redundantes. Porém, para um grafo orientado, toda célula da matriz transmite uma informação única (LAFORE, ROBERT). Não utilizei o grafo da Figura 1 porque ele possui muitos nós e arestas, e isso concluiria em uma matriz muito extensa, atrapalhando assim o nosso exemplo.
Levar toda essa teoria para a prática resulta na criação de um simples método que faz a marcação explicada na matriz de adjacência. Como sempre, é possível obter todo o código desenvolvido até essa postagem no repositório GitHub (link no fim do post) do projeto. Faça o download, dê uma olhada e deixe aí sua opinião. A frente, estudaremos algoritmos específicos para este tipo de grafo, não perca.

Com isso chegamos ao fim de mais uma postagem. Se você gostou compartilhe com seus amigos, se inscreva no blog e curta a página no Facebook.

Até a próxima minha boa gente ! 😘

Leia nossa postagem anterior: Árvores geradoras mínimas - Grafos 

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

Leia Mais ››

Árvores geradoras mínimas - Grafos

Bem-vindos ao blog Preciso Estudar Sempre. Meu nome é João Paulo Maida e minha paixão é estudar.

Esta é a quarta publicação da série Grafos, onde abordaremos mais um assunto desta incrível teoria. Caso você seja novo por aqui e não leu nenhuma postagem ainda, recomendo que você clique aqui e comece pela primeira publicação desta série, onde entendemos o que é um grafo e do que ele é composto. Mas, se você já é um leitor assíduo do blog e leu a penúltima postagem, se delicie agora com mais um conteúdo voltado para você, amante do estudo.

Na teoria dos grafos, as árvores geradoras mínimas servem para gerar representações onde, o foco é eliminar o excesso de arestas. Entenda por excesso o fato de existirem mais arestas que o necessário para conectar o grafo inteiramente. A Figura 1 mostra um grafo com oito vértices e um número excessivo de arestas, ao passo que a Figura 2 mostra um grafo com os mesmos oito vértices, mas com um número mínimo de arestas necessárias para conectá-lo de forma completa.

Figura 1 - Grafo com arestas em demasiado

Figura 2 - Árvore geradora mínima do grafo acima

Diferentes árvores podem ser geradas a partir do momento que escolhemos pontos de partidas diferentes. No nosso caso, o ponto de partida escolhido foi o nó A, logo o resultado só pode ser este, mas caso escolhêssemos o nó B, o resultado seria outro completamente diferente.

Lembre-se que nossa preocupação aqui não é o comprimento das arestas, não estamos tentando encontrar o menor caminho, e sim reduzir a quantidade de arestas (LAFORE, ROBERT).

Outro ponto a ser notado é a possibilidade de se calcular o número de arestas de uma árvore geradora mínima através da expressão abaixo, onde E é a quantidade de arestas e V é a quantidade de vértices.

E = V - 1

Quais seriam as aplicações possíveis para uma árvore mínima geradora ? Muitas, basta somente um pouco de reflexão sobre os problemas do cotidiano. Imagine uma imensa rede de transmissões de linhas telefônicas que conecte todas as cidades de um país. Uma cidade pode se conectar diretamente ou indiretamente a outra cidade, por exemplo Rio de Janeiro - Belo Horizonte ou Rio de Janeiro - São Paulo - Belo Horizonte. Em um determinado momento é decretada uma ordem de redução de custos de cabeamento pelo presidente da empresa, e todas as conexões redundantes precisam ser eliminadas, logo a conexão direta Rio de Janeiro - Belo Horizonte teria seu fim decretado, visto que a conexão alternativa (RJ - SP - BH) atinge o mesmo propósito e ainda traz outra cidade para o novo grafo de conexões.

Este exemplo pode parecer um pouco incomum visto que este presidente estaria jogando o dinheiro da companhia fora quando manda remover os cabos e que talvez as distâncias entre as cidades não compensariam tal trabalho. Porém, isto é somente um exemplo imaginário de um problema real.

O algoritmo usado para criar a árvore geradora mínima é quase idêntico ao usado para buscar. Ele pode ser tanto baseado na busca em profundidade quanto na busca em largura. Neste post, abordaremos uma implementação baseada na busca em profundidade (LAFORE, ROBERT), pois o caminho armazenado na pilha desse tipo de busca é automaticamente a árvore geradora mínima. A única diferença entre a busca e o algoritmo da árvore geradora mínima é que o segundo deve registrar de alguma forma as arestas pelas quais passa.

Um outro motivo da árvore geradora mínima ser facilmente derivada da busca em profundidade é porque essa busca visita todos os nós, mas apenas uma vez. Ele nunca vai para um nó que já tenha sido visitado. Quando ele ver uma aresta que tenha um nó visitado no final, não irá segui-la. Ele nunca viaja por uma aresta que não seja necessária. Assim, o caminho percorrido pela busca tem que ser uma árvore geradora mínima (LAFORE, ROBERT).

Escolhi Java como a linguagem de programação para estes algoritmos por uma questão de afinidade, mas nada impede que você utilize uma versão do Java diferente da minha ou até outra linguagem.

Este é o método responsável pela geração da árvore geradora mínima. Como dito antes, este algoritmo se assemelha muito com o algoritmo de busca em profundidade, e isto é visível no trecho de código acima. A única diferença que deve ser ressaltada é a exibição dos nó atual e o adjacente à ele juntamente com o espaço em branco, o qual facilita a visualização do resultado final.

Caso você não tenha conhecimento sobre as buscas em profundidade, já abordamos esse assunto aqui no blog. Clique aqui e tire suas dúvidas. Recomendo a leitura.
A classe acima tem como propósito final criar e montar um grafo para depois executar a geração da árvore mínima geradora nele. O resultado esperado, como já visto na Figura 2, é um grafo com o mínimo de arestas possíveis que conectem todos os seus vértices.

Chegamos ao fim de mais uma postagem da série Grafos. Ainda temos muito conteúdo para discutir e muitas coisas novas para aprender, estamos somente no início de uma longa jornada. Então se prepare para as novidades que vem por aí.

Até a próxima minha boa gente ! 😘

Leia nossa postagem anterior: Busca em largura - Grafos

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

Leia Mais ››

Busca em largura - Grafos

Bem-vindos ao blog Preciso Estudar Sempre. Meu nome é João Paulo Maida e minha paixão é estudar.

Na nossa última postagem abordamos uma das formas de se realizar uma busca em um grafo, a busca em profundidade. Caso você não tenha lido, clique aqui. Mas, se você for um total iniciante no assunto, recomendo que você comece lendo a primeira postagem dessa nova série, clicando aqui.

Já informo de antemão que utilizarei a linguagem de programação Java para a construção das implementações dos algoritmos e que nada impede que você utilize uma outra versão do Java diferente da minha ou, até uma outra linguagem. Agora, sem mais delongas, vamos ao assunto.

A necessidade e as restrições que envolvem este assunto são as mesmas que envolviam o assunto da postagem anterior. Dado um grafo G desconhecido, quais nós são possíveis de atingir a partir de um determinado nó N ? Esta pergunta, obviamente, já foi respondida, mas aqui veremos uma outra forma de respondê-la.

Analisemos o grafo mostrado na Figura 1.

Figura 1 - Grafo de exemplo

Assim como já foi discutido previamente, é necessário que um ponto de partida seja escolhido, pois o grafo analisado é desconhecido de primeira mão, estamos às cegas. Só teremos o conhecimento de um ponto inicial, o nó A no nosso caso. Tal condição não somente viabiliza a pergunta feita acima, mas como nos deixa à frente de grandes problemas, como: O que fazer ? Qual nó adjacente visitar primeiro ?

Ao contrário de sua irmã, a busca em largura não visita a fundo todo um caminho de arestas até chegar em um ponto que não consiga ir mais adiante, ela se comporta de uma forma completamente diferente. Ela visita todos os nós adjacentes ao nó inicial e apenas então vai mais adiante. A estrutura que serve como alicerce para tudo isso é uma fila do tipo FIFO, pois é ela que vai registrar qual é o caminho atual percorrido. Caso você não seja conhecedor de tal estrutura, recomendo fortemente o estudo dela antes de continuar a leitura deste post e peço desculpas por não deixar uma referência de post do próprio blog sobre o assunto. Não faço isso, pois ainda não abordei esse tema.😞

Imagine o seguinte: uma pedra cai na água de uma calma lagoa (LAFORE, ROBERT). Quando a pedra entra em contato com a água, ela cria ondas que se espalham de forma igual por toda a superfície criando assim um fenômeno homogêneo. Tal característica se repete nas buscas em largura, ou seja, os nós são percorridos de uma forma igual em relação às suas adjacências. Isto significa que todos os nós que estão a uma aresta de distância do ponto inicial são encontrados primeiro, então todos os nós que estão a duas arestas de distância são encontrados em seguida, e etc. Tal característica será útil se você estiver tentando encontrar o caminho mais curto do nó inicial até um determinado nó (LAFORE, ROBERT).

Para uma execução organizada e procedural, três regras foram criadas. São elas:

Regra 1
Visite o próximo nó não visitado, se existir, que seja adjacente ao nó atual, marque-o e insira-o na fila (LAFORE, ROBERT).

Lembre que nosso ponto de partida é o nó A, já temos conhecimento sobre ele, logo nenhum processamento a mais é necessário. Tal fato nos permite a executar a regra 1, o que nos leva ao nó B. Após isso, devemos verificar se A não possui nenhum outro nó adjacente não visitado ainda, e então descobrimos C, D e E. Para estes três últimos nós, a regra 1 deve ser aplicada. Agora na fila temos: B C D E.

Após executar a regra 1 para todos os nós adjacentes à A, não teremos mais nós adjacentes não visitados. Então, o que fazer ? Para esta necessidade surge a regra 2.

Regra 2
Se você não puder executar a Regra 1 porque não há mais nó não visitado, remova um nó da fila e torne-o o nó atual (LAFORE, ROBERT).

Removendo um nó da fila teremos B, mas porque não E ? Isto acontece devido ao tipo de fila que estamos utilizando. A sigla FIFO significa first-in-first-out, ou seja, o primeiro que entra é o primeiro que sai, assim como na fila de um banco. Logo, filas que usem esse tipo de esquema de organização de itens terão este comportamento, e este é o nosso caso.

Voltando à nossa linha de raciocínio, remover um nó da fila resultará no nó B, e este é o nosso nó atual. Uma nova execução da regra 2 se faz necessária, mas agora é possível executar a regra 1 pois o nó atual possui nós adjacentes não visitados. Isto fará com que F entre na fila.

C sai da fila, não possui adjacências. Devemos remover o próximo pois a regra 1 não consegue ser satisfeita, logo removemos D da fila. A partir deste, enfileiramos G e concluímos que assim como C, o nó E sai da fila e não possui adjacências.

A interação entre a regra 1 e a regra 2 recria o fenômeno de onda citado anteriormente, pois as adjacências de F e G só serão exploradas totalmente quando todos os nós que estão no mesmo “nível” de seus pais forem exploradas primeiro.

A regra 2 é executada em F, menos um na fila e em seguida H é enfileirado pela regra 1. O mesmo acontece para I quando G é desenfileirado. Execuções contínuas da regra 2 em conjunto da 1 resultarão em uma fila vazia, o que nos leva à regra 3.

Regra 3
Se não puder executar a Regra 2 é porque a fila está vazia, terminou (LAFORE, ROBERT).

Visto que houveram muitas movimentações na fila durante a execução das regras, a Tabela 1 mostra de forma detalhada o passo a passo de todas as operações realizadas.

Evento	Fila
Vá para A
Vá para B	B
Vá para C	BC
Vá para D	BCD
Vá para E	BCDE
Remova B	CDE
Vá para F	CDEF
Remova C	DEF
Remova D	EF
Vá para G	EFG
Remova E	FG
Remova F	G
Vá para H	GH
Remova G	H
Vá para I	HI
Remova H	I
Remova I
Terminado

Se você leu o post anterior sobre busca em profundidade notará que as diferenças são grandes. Compare como as duas abordagens funcionam e deixe sua opinião nos comentários.👍

Visto que já conhecemos toda a teoria necessária para entender e executar uma busca em largura, podemos a partir daí transcrever este algoritmo para um programa Java.

Este método executa as três regras descritas acima de uma forma bem simples. Ele inicia adicionando o primeiro nó do grafo, o ponto de partida, na fila, e partir daí verifica repetidamente se a fila não está vazia. Caso negativo a busca chegou ao fim pois não existem mais nós para analisar, mas caso contrário, ainda existem nós não explorados e os processos descritos nas regra 1 e 2 são executados.

É possível notar que um método auxiliar é utilizado para verificar as adjacências de um determinado nó. Por tal motivo, o segundo laço de repetição se faz necessário pois um nó pode ter N adjacências.

O último laço de repetição utilizado tem a finalidade de somente resetar a flag de visitação dos nós para que buscas futuras possam ser executadas sem problemas.

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, caso contrário, retorna -1 simbolizando que não encontrou nada.

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 do repositório no fim do post.

A classe acima é somente utilitária. Sua única responsabilidade é criar e montar um grafo para depois executar a busca em largura nele. O resultado esperado de sua execução é o caminho percorrido pelo algoritmo de busca.

Esta postagem é somente mais uma que compõe a grande série de assuntos envolvendo a teoria dos grafos. Em publicações futuras veremos árvores geradoras mínimas, o algoritmo de Warshall e etc.

Até a próxima minha boa gente ! 😘

Leia nossa última postagem sobre grafos: Busca em profundidade - Grafos

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

Leia Mais ››

Busca em profundidade - Grafos

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

Pode parecer complicado comparar labirintos com grafos, mas com um pouco de abstração é possível notar que um pode ser sim representado no outro. Para a entrada do labirinto temos o nó inicial de um grafo, para o término de um caminho ou ramificação temos mais nós, e para os caminhos que interligam todos esses três elementos temos as arestas. Um dos segredos para sair de um labirinto é lembrar o caminho feito e geralmente isso é feito usando um barbante. O herói grego Teseu utilizou desta mesma técnica quando enfrentou o terrível Minotauro em seu imenso labirinto. A busca em profundidade utiliza a mesma idéia, mas ao invés do barbante utilizaremos a pilha, já citada anteriormente.

Figura 2 - O labirinto do Minotauro

O algoritmo que procuramos nos dará certeza que o grafo será complemente escaneado sem que percamos tempo com escolhas erradas, e que após todo o procedimento ter sido feito ele terminará sua execução. Contudo, para realizar tal façanha nenhum pré-planejamento pode ser feito, visto que não temos conhecimento sobre sua estrutura. Então, decisões de direção devem ser tomadas uma após a outra ao longo do trajeto feito (EVEN, SHIMON). Por tais motivos a dúvida apresentada no início da postagem é justificada.

Analisemos a Figura 3 para que possamos tomar conhecimento de como a busca em profundidade funciona.

Figura 3 - Grafo de exemplo

A determinação de um ponto de partida é necessária e já foi citado acima, logo para o grafo da Figura 3 temos o nó A representando esse papel. Neste momento a única informação que temos é que apenas este nó compõe o grafo. Então, precisamos executar três passos essenciais: visitar o nó, colocá-lo na pilha para que possamos lembrar no futuro que já passamos por ali, e marcá-lo como visitado. Tudo isto dá vida à Regra 1.

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

Leia Mais ››