Grafos — representação e implementação
Para se representar um grafo temos que analisar quais de seus nós (vértices) que existem conexões, mas como ficaria esta representação nos computadores? Existem duas maneiras mais usuais de representa-los : Matriz de adjacência ou lista de adjacência.
Matriz de adjacência
Uma matriz de adjacência qualquer (M) terá a quantidade de vértices (n) de numero de linha e colunas, ou seja uma para cada vértice. Ocorrera diferenças para caso o grafo for ou não ponderado.
Grafo não ponderado
Em uma matriz M para o gráfico não ponderado, podemos completar suas linhas(i) e colunas(j) com apenas 0 e 1, pois só existe a opção de conter ou não ligações entre os vértices.
Então em uma matriz (M)de adjacência não ponderada, temos que:
M[i,j] = 1, se houver uma aresta saindo do vértice i e indo até o j
M[i,j] = 0, se não houver uma aresta saindo do vértice i e indo até o j
A imagem a seguir mostra um exemplo do caso:
Grafo ponderado
No caso de ponderado, usamos a mesma lógica, mas no lugar de bits (0 ou 1), usamos o valor do peso, seja eles em inteiro, reais ou outros valores.
Então em uma matriz (M)de adjacência ponderada, temos que:
M[i,j] = valor do peso, se houver uma aresta saindo do vértice i e indo até o j
M[i,j] = valor definido para representar não ligação*, se não houver uma aresta saindo do vértice i e indo até o j
*Note que o valor definido para representar não ligação é definido em código pelo programador, você pode usar zero como na matriz de bits, porém caso esteja trabalhando com distancia por exemplo, existe distancia zero, então talvez atrapalhe seu códio. Fique atendo na escolha!
A imagem a seguir mostra um exemplo do caso:
Lista de adjacência
Consiste em uma lista qual cada elemento é um nó do grafo, logo a lista possui de tamanho o numero de vértices do grafo. Ela possui n lista ligadas, estas contem as conexões de cada arestas do vértice. Apesar da definição confusa veremos na imagem a seguir como é fácil sua visualização:
Computacionalmente, vamos representar isto como uma lista que em cada elemento (representando um vértice do grafo) existe um ponteiro para todas as arestas ligada a ela. Vamos trabalhar com uma lista de tamanho pré definido, mas caso você não saiba o tamanho do seu grafo é só mudar para uma lista encadeada. Lembrando que se seu grafo for ponderado, basta adicionar um campo de peso.
Para acessar o código completo basta clicar neste link.
O códio e a imagem acima mostram como implementar o grafo com a lista de adjacência, repare que salvamos o numero de vértice e arestas, pois para saber esta informação, caso não estivesse salva, seria necessário percorrer todo o arquivo.
A partir disto temos um arranjo de vértices que apontara para estrutura vértice. Cada vértice (além dos dados da vértice, que podem ser implementados) aponta para a cabeça de suas adjacências, que são uma lista contendo todas as ligações que aquele vértice possui.
A struct adjacência guarda o vértice final que ela tem ligação, o peso associado a ligação e finalmente o próximo vértice que contem ligação (na imagem representado em rosa).
Quando usar cada representação?
Escolher cada representação vai depender do tipo de problema que você quer modelar, mas deixaremos algumas dicas para te auxiliar na escolha.
Gráficos densos: Com muitas arestas em relações ao numero de nós. Logo as listas de adjacências seriam muito grandes, tornando inviável a sua utilização. Utilizar matriz.
Gráficos esparsos: Com muitas nós em relações ao numero de arestas. Depende de sua preferência e das operações que vão ser usadas.
Buscas: Buscas são mais rápidos com lista de adjacência, pois já existe todas as opções que o nó se conecta. Na matriz, teria que percorrer a linha toda.
Testar existência entre arestas: Mais rápido com matriz, pois é só olhar na célula (i,j) e verificar se existe ou não a ligação.
Encontrar nós que vem antes: Mais rápido com matriz, pois é só olhar a linha do nó e verificar quais fazem ligação com ele. Em uma lista teria que percorrer toda a lista.
