Grafos ponderados - Grafos

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

A partir de agora, reserve sua mente para um novo conceito. Pegue tudo o que você já aprendeu e guarde, pois será necessário. Você está prestes a conhecer um novo tipo de grafo, com novas características e ferramentas. Conheça os Grafos Ponderados.

Resumidamente, grafos ponderados são grafos com pesos em suas arestas (Figura 1). Entenda pesos como valores e não como quilos. São utilizados para determinar qual o melhor trajeto adotar dado o problema. Pense na seguinte situação: você quer sair do centro da cidade do Rio de Janeiro e chegar no Cristo Redentor. Como chegar lá ? Existem vários caminhos. Qual deles é o melhor ? Isso depende de você. Se está com pressa por causa de tempo, talvez aquele caminho mais curto porém mais perigoso seja melhor do que aquele mais seguro e longo, ou talvez se um trajeto com mais paisagens for mais importante do que rapidez, um outro caminho pode ser o ideal. Visto que podem existir diversas possibilidades de caminhos a serem feitos, um critério de escolha deve ser escolhido e em cima dele as diversas arestas que conectam o ponto A ao ponto B ganharão seus respectivos pesos.

Figura 1 - Diferenças entre um grafo ponderado e não ponderado

Um grafo ponderado pode ser tanto orientado quanto não orientado (Figura 2) e essa orientação é a mesma já vista anteriormente, logo os problemas que essa característica traz também são os mesmos e obviamente acabam se acumulando com os novos desafios oriundos das arestas ponderadas. Estruturas como matrizes ou listas de adjacências também aparecem aqui, logo nenhuma surpresa quanto a isso. O que realmente vai diferenciar este tipo de grafo são seus pesos em suas arestas e os algoritmos originados a partir da análise dos mesmos. Tais diferenciais tornam a implementação um pouco diferente do que já estávamos acostumado.

Figura 2 - Diferenças entre um grafo ponderado orientado e um não orientado

WeightedGraph.java
Como dito antes, alguns métodos não são lá uma surpresa, contudo alguns destaques podem ser feitos. Note que não existe inicialização com 0’s da matriz de adjacência aqui, pois ela não é mais uma matriz de inteiros e sim de objetos do tipo Edge. Como é de conhecimento de todos, variáveis de instância em Java tem seu valor default como null, logo automaticamente a matriz tem valores nulos em todas as suas posições e isso é o bastante para saber se existe uma aresta ali ou não.

O método de adição de aresta deixa claro através de seu nome que são arestas não orientadas que são adicionadas e ele recebe como parâmetro o peso da aresta. Realizei a mudança no nome com a finalidade de deixar o código mais intuitivo. Lembre-se que pelo fato das arestas não serem orientadas é preciso marcar a matriz duas vezes e que agora será inserido um objeto do tipo Edge ao invés de um inteiro. O resto da classe é mais do mesmo que já estamos acostumados.

Edge.java

Esta classe representa uma aresta, podendo ser orientada ou não, de um grafo ponderado. Lembre-se que a orientação é ditada na matriz. Dentro dela estão todas as informações necessárias de uma aresta, como: vértice de origem, destino e seu peso.

WeightedGraphApp.java

Classe cliente, tendo como responsabilidades a criação e exibição de um grafo ponderado.

Com isso, chegamos ao fim de mais uma postagem.

Estamos chegando ao fim da série Grafos. Faltam somente mais alguns assuntos para encerramento total desta série, não perca nenhum deles. Após esta série de assuntos começaremos uma nova com um novo formato que ainda é surpresa para tornar a nossa experiência a mais dinâmica possível.

Até a próxima minha boa gente ! 😘

Leia nossa postagem anterior: Indicações de livros - Estruturas de dados e Algoritmos em Java

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

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 ››