Á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