Matrizes de adjacência e grafos

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

Na nossa penúltima postagem tivemos uma introdução sobre a teoria dos grafos, onde vimos sua história, áreas de aplicação, definições e exemplos. Você pode dar uma conferida nele clicando aqui. Hoje entenderemos como podemos representar as conexões de um grafo, ou seja, suas arestas.

Adiante veremos que é possível realizar buscas em grafos e que para executar essas tarefas precisaremos de um tipo de registro das conexões do grafo. Esse registro consiste em uma forma de mapear todas as adjacências de um grafo. Um nó é qualificado como adjacente a outro nó quando a distância entre eles é de apenas 1 aresta. Esse mapeamento pode ser representado através de duas estruturas de dados: matrizes e listas encadeadas. Abordaremos aqui as duas formas, suas implementações, vantagens e desvantagens.

Já vimos aqui no blog o que é uma lista encadeada e como ela funciona. Caso você não se lembre, clique aqui e dê uma relembrada. Uma matriz é uma estrutura baseada em linhas e colunas, igual a uma tabela. Enquanto os vetores ou arrays são estruturas unidimensionais, as matrizes podem ser multidimensionais. No nosso caso, nossas matrizes terão apenas duas dimensões onde ambas serão os vértices do grafo. Logo, se um grafo G possuir N vértices, sua matriz de adjacência terá N x N células. Mas o que significa N x N células? Isso significa que um determinado vértice pode estabelecer conexões com todos os outros vértices do grafo, incluindo ele mesmo.

Figura 1 - Grafo de exemplo

Para o grafo da Figura 1, sua matriz de adjacência é mostrada pela Tabela 1.

Tabela 1 - Matriz de adjacência

Note que para todas as células que possuem o número 1 existe uma aresta conectando os vértices mostrados pela linha e coluna. Então, através da matriz é possível concluir que existe uma aresta que parte de A e vai para B. Por convenção, é determinado que a origem de uma aresta é ditada pela linha da matriz, e o destino a coluna. Isto terá mais sentido para grafos orientados. Como o grafo acima não é orientado, precisamos representar suas arestas de forma bidirecional, ou seja, se existe uma ligação de A para B, então existe uma ligação de B para A. Para todas as células da matriz que possuem o número 0 significa que ali não existe uma aresta conectando dois vértices. Como dito acima, a matriz somente mapeia as conexões adjacentes entre vértices.

Ao contrário de uma matriz, uma lista de adjacência não possui zeros e uns para representar as conexões dos vértices de um grafo, eles formam uma versão mais compacta através do uso de uma lista encadeada, onde em cada posição desta lista existe uma outra lista encadeada. Cada lista individual mostra a quais nós um dado nó é adjacente. Lembre-se disso pois frequentemente essa estrutura causa confusão. Ela dá a impressão que a lista individual inteira forma um caminho, sendo que isso não é verdade. A lista de adjacências mostra quais nós são adjacentes, não caminho de nó a nó (LAFORE, ROBERT). Esta situação ficará mais clara com o exemplo da Figura 2.

Figura 2 - Lista de adjacências

Viu como é fácil se confundir ? Em uma olhada rápida é possível afirmar que existe um caminho que começa no vértice B, passa por A e C, e termina em D embora não seja essa a verdade.

As amostras de código abaixo mostram a implementação dessas duas estruturas em Java, mas como eu sempre digo, nada impede que você construa sua implementação em uma outra linguagem de seu gosto.     

Matriz de adjacência
Lista de adjacência

Caso você execute algum desses programas, terá como resultado as conexões do grafo, conforme citado anteriormente. Mas, das duas implementações apresentadas qual utilizar ?

Independentemente dos motivos que irei apresentar aqui, tenha algo sempre em mente. A lista de adjacência é uma versão resumida da matriz de adjacência. Logo, em aplicações que necessitamos mais agilidade para avaliar a adjacência entre vértices, inserindo ou removendo conexões, a lista é mais indicada, mas caso você precise de algo mais completo, a matriz é uma boa escolha pois ela mostra quais nós são adjacentes e quais não são. Como sempre digo, e se você acompanha o blog vai saber, não existem balas de prata na computação. Não existem soluções perfeitas.

Um bom exemplo de como a matriz é superior a lista é em uma busca por profundidade. Através dela o algoritmo de busca é capaz de encontrar os nós que não foram visitados e adjacentes a um nó especificado (LAFORE, ROBERT). Contudo, na eliminação de nós o uso da lista é superior, pois para cada eliminação é necessário o translado de todas as linhas e colunas para cima e para a esquerda, ou para baixo e direita. Este processo é custoso, logo uma abordagem baseada em lista encadeada seria melhor pois somente as referências corretas precisariam ser removidas.

É isso amigos, chegamos ao fim de mais uma postagem sobre a teoria dos grafos. Espero que você tenha gostado. Em postagens futuras abordaremos assuntos mais elaborados como buscas, grafos orientados, ponderados e algoritmos da área.

Até a próxima ! 😘

Leia nossa próxima postagem sobre grafos: Busca em profundidade - Grafos
Leia nossa última postagem sobre grafos: Grafos - O início

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, deixa 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