Como representar um grafo?

[dicas3d]

Olá pessoal.

Gostava que me dessem uma opinião sobre uma matéria sobre grafos que encontrei.

O link é este: http://algoritmos.tiagomadeira.net/representando-grafos-na-programacao.

Que tal é o artigo?

[HappyHippyHippo]

pessoalmente, não gosto do modelo matricial para representação de grafos. isto porque se tiveres 10 nós e 10 arestas tens 90 espaços na matriz desnecessários ..

eu, quando tive de programar um grafo , utilizei listas ligadas

- uma lista de nos

- em cada nó uma lista de arestas emergentes (desculpa, para mim serão sempre digrafos)

[Flinger]

Concordo com o Hippo, com uma pequena diferença. Normalmente prefiro usar àrvores binárias ou tabelas de hash para o armazenamento de todos os nós, tendo cada um uma lista ligada de adjacências (normalmente uso dados da ligação + apontador para o destino, embora dependa um pouco do problema). É um pouco mais confuso a princípio, mas para grafos grandes aumenta um pouco o desempenho.

[pedrosorio]

pessoalmente, não gosto do modelo matricial para representação de grafos. isto porque se tiveres 10 nós e 10 arestas tens 90 espaços na matriz desnecessários ..

eu, quando tive de programar um grafo , utilizei listas ligadas

- uma lista de nos

- em cada nó uma lista de arestas emergentes (desculpa, para mim serão sempre digrafos)

O modelo matricial é ideal quando o número de nós não é excessivamente grande e o grafo é denso. De qualquer forma, se houver memória suficiente o modelo matricial é sempre preferível porque para além de permitir todas as operações que o modelo da lista de adjacências permite, ainda consegues obter o peso (ou ausência) da aresta entre dois nós em O(1).

No caso do modelo de lista de adjacências não vejo qual é a lógica de usar uma lista ligada para os nós do grafo em vez de um array, fazendo com que o acesso a um nó arbitrário seja O(n).

Concordo com o Hippo, com uma pequena diferença. Normalmente prefiro usar àrvores binárias ou tabelas de hash para o armazenamento de todos os nós, tendo cada um uma lista ligada de adjacências (normalmente uso dados da ligação + apontador para o destino, embora dependa um pouco do problema). É um pouco mais confuso a princípio, mas para grafos grandes aumenta um pouco o desempenho.

Árvores binárias ou tabelas de hash? Porque não um simples array?

[HappyHippyHippo]

O modelo matricial é ideal quando o número de nós não é excessivamente grande e o grafo é denso. De qualquer forma, se houver memória suficiente o modelo matricial é sempre preferível porque para além de permitir todas as operações que o modelo da lista de adjacências permite, ainda consegues obter o peso (ou ausência) da aresta entre dois nós em O(1).

Eu disse que a minha preferência recaia fora da matricial por problemas de tamanho, não de rapidez de acesso. E como tudo, uma preferência não é uma lei mandatária para todos os casos. Nunca disse que o modelo matricial era mau ou nunca se deveria usar.

No caso do modelo de lista de adjacências não vejo qual é a lógica de usar uma lista ligada para os nós do grafo em vez de um array, fazendo com que o acesso a um nó arbitrário seja O(n).

Para casos em que os grafos requerem várias mutações em termos de nós (remover/adicionar) o modelo de lista é muito pior que lista ligada.

Novamente, não estou a dizer que está mal usar um modelo ou outro, porque claramente um caso é um caso, no entanto, pela minha experiência, o modelo que referi teve comportamentos médios mais aceitáveis nos diferentes problemas a que foi aplicado.

[Warrior]

Não consigo responder à pergunta inicial porque é demasiado genérica.. o que achamos do artigo é muito geral. Tens um tutorial sobre as mesmas coisas aqui no forum:

http://www.portugal-a-programar.pt/topic/16357-grafos/

Posso no entanto comentar em relação ao resto da discussão. Acho que não convém subestimar a importância de representações matriciais, até porque são cada vez mais importantes na investigação que se faz hoje em dia em grafos. Têm tido muito mais atenção nos últimos 10 anos.

Podem-se dividir os avanços nos algoritmos em grafos em 4 "etapas":

• Combinatória - Inicialmente, grafos eram objectos matemáticos e eram tratados como tal; quem lidava com grafos eram matemáticos.
  
• Estruturas de dados - Os algoritmos de grafos eram estudados como tal e a evolução dos mesmos passava pela criação de estruturas de dados que permitiam a criação de algoritmos mais eficientes para efectuar as operações necessárias. Na década de 60 e 70 surgiu a maior parte dos algoritmos de grafos que se aprendem hoje.
  
• Aproximação - Certos problemas não-polinomiais foram abordados como problemas de aproximação em que o que se procura é um resultado não-óptimo mas com uma certa garantia em relação ao resultado optimal.
  
• Teoria espectral de Grafos - Estuda as propriedades dos grafos com base na sua representação matricial e nos seus espectros.
  

Algumas representação matriciais, como a matrix laplaciana de um grafo são extremamente importantes para analisar um grafo. Para quem não sabe, a matrix laplaciana é muito semelhante à matriz de adjacência, com a diferença de que cada aresta é representada por -1 e na diagonal do grafo surge o grau do vértice (isto garante coisas importantes como o somatório das linhas ser igual a 0).

Só para dar alguns exemplos, a matriz laplaciana está ligada a propriedades muito importantes:

• O número de 0s nos valores próprios é equivalente ao número de componentes conexas num grafo.
  
• O determinante da matriz é o número de árvores de extensão mínima existentes no grafo. (Teorema de Kirchhoff)
  
• Os valores próprios estão relacionados com o diâmetro do grafo.
  
• Os valores próprios também estão relacionados com o número de passeios diferentes de um determinado tamanho num grafo.
  

---

Acho que este post pode ser demasiado complicado para a pergunta/conhecimentos do autor do post, mas nunca vi muitos destes assuntos discutidos neste forum.

Há muita informação mais detalhada sobre "Spectral Graph Theory" na internet, por exemplo aqui.

Agora, definitivamente que a decisão matriz de adjacência vs listas de adjacências não é assim tão simples..

Edited September 24, 2012 at 11:11 PM by Warrior